State Machine and Synchronization

This is the second of two notes for Lamport’s Time-Clock paper. The first one is here.

The problem

We will be focusing on how to use Logical Clock to solve an actual problem. The problem is to grant the resource to a process, that

  1. different requests for the resource must be granted in the other in which they are made **
  2. if every process which is granted the resource eventually releases it, then every request is eventually granted

A centralized solution

The requirement(2) is non-trivial to satisfy. The most naive solution would be having a centralized master that assigns the resource to processes upon receiving the request. But it doesn’t actually satisfy (2). Let’s say P0 made two requests, R0 to the master and R1 to P1. P1 after receiving R1, made R2 to the master requesting for the resource. R2 can be received before R0. If the master naively assigns the resource upon receiving a request, (2) will be violated.

  • sending heartbeats can take a significant portion of the network bandwidth comparing to the actual request and release commands

A distributed solution

  1. Upon receiving the request, each process stores the request and sends an ACK (timestamped) to the sender.
  2. The resource is granted to a process Pi, when (i) req:Pi:Ti is in the local store and Ti is the smallest timestamp for a resource request locally (ii) Pi has received messages from all other processes with T > Ti
  3. To release the resource, Pi sends release resource (timestamped) to everyone, and removes any req:Pi locally stored.
  4. Upon receiving the release, each process also removes any req:Pi from the local store.

State Machine

If we generalize the solution above a little bit, it’s not hard to see that it’s actually a generic method for achieving synchronization in distributed system (without failures).

Software Engineer at Facebook working on cache infrastructure

Software Engineer at Facebook working on cache infrastructure