• Server keeps track of a token - Permission to enter critical region
• Process requests token from server and awaiys reply
• Server grants token if it has it, otherwise queues request
• A process can enter critical region if it gets the token, otherwise it waits
• On exiting critical section, process sends release message to server

• Correctness
• Achieves safety - if no processes crash
• Achieves liveness - assuming server has enough storage to queue N processes
• Does not guarantee Happened-before ordering:
1. Process A sends a request for entry, then sends message m to B
2. On recipt of m, B sends request for entry.
3. To satisfy happened-before order, should be granted before
4. However dues to message propagation delay, arrives at server before, and they are serviced in opposite order

• Enter overhead: Two messages ( request and grant)
• Enter delay: Time between request and grant
• Exit overhead: One message (release)
• Exit delay: none
• Synchronization delay: Between release and grant
• Centralized server is the bottleneck

• Processes are arranged in logical ring, this could be unrelated to physical configuration
• p_i sends message to p_{(i + 1)mod n}
• When process holds the token, it can enter, otherwise waits
• When process releases token (exit) it sends to its neighbour

• Acheives safety - assumed reliable communication/ no crashes
• Achieves liveness - finite processes and finite time in critical region
• Ordering is not ensured, as order of access to critical region is based purely on the arrangement of the nodes

• Bandwidth: High consumption as token continually circulating
• Exit overhead: 0 to N messages
• Enter delay: duration of 0 to N messages
• Exit overhead: 1 message
• Exit delay: none
• Synchronization delay: time for transmission of 0 to N messages

• Processes multicas their request messages
• A process can only enter critical region if all processses reply
• Globally ordered timestamps are included in all request messages
• Each process has a state
• RELEASED - They reply
• HELD - They wait until they exit, then reply
• WANTED - They compare the timestamp to the one on its own request, and reply  if theirs is higher

On initialization

    state := RELEASED;

To enter the section

    state := Wanted;

    Multicast Request to all processes;

    T := request's timestamp;

    Wait until (number of replies received = (N - 1));

    state := HELD;

On receipt of a request < T_i, p_i > at p_j (i != j)

    if (state=HELD or (state=WANTED and (T, p_j) < (T_i, p_i)

    then  

        queue request from p_i without replying;

    else

        reply immediately to p_i;

To exit the critical section

    state := RELEASED;

    reply to any queued requests;

• Safety is ensured - asuming reliable communication and no crashes
• Liveness is ensured thanks to finite processes and finite time in critical region
• Ordering is also maintained due to the totally ordered timestamps

• Bandwidth: No unnecessary circulating tokens
• Entry overhead: 2(N - 1)
• Entry delay: Delay of multicast request + reply from each process
• Exit overhead: 0 to N - 1 messages (However many requests you got while in critical region)
• Exit delay: none
• Synchronization delay: 1 message

Consists of 'Voting', where instead of receiving messages from all peers, only replies from a subset of peers are needed. Each peer vote for one another to enter critical section

• We don't need all N-1 replies, but only a subset of peers
• Consider processes A, B, X:
• A needs the replies from A and X
• B needs the replies from B and X
• If X can only reply to (vote for) one process at a time, then
• A and B cannot have a reply from X at the same time
• Mutex between A and B hinges on X
• Place processes in overlapping groups
• Members in overlap groups control mutex

• A group of processes V_i for each proces p_i
• The groups for any given pair of processes overlap
• To enter the critical region
• p_i sends REQUESTs to all processes in V_i
• Waits for REPLYs (VOTEs) from processes in V_i
• To exit the critical region p_i
• Sends RELEASEs to all processes in V_i

• Entry overhead: K requests + K replies
• Exit overhead: K releases
• Entry delay: delay between request and getting all replies
• Exit delay: none
• Synchronisation delay: 2 messages