Coordination and Agreement in Distributed Systems

For the rest of the post we assume the following:

  • Processes connected by reliable channels
  • Only possible file is a crash
  • Systems Asynchronous

Distributed Mutual Exclusion

If server involved allowing access to one process at a time

Algorithms evaluated following:

  • Bandwidth consumed
  • Client delay
  • Throughput of the system

Central Server Algorithm:

  • A process sends a request to the server
  • Server gives Token
  • When queue is empty next one is chosen
  • Entering costs two messages (request then grant)
  • Exiting one message
  • The server may become a bottleneck

A ring-based algorithm:

  • Server-less approach
  • Connection between one process and the following
  • One a process leaves the critical section sends the token away to the next one
  • Continuously consumes bandwidth
  • Entering Delay between 0 to N
  • Leaving 0 messages

Ricart and Agrawala’s Algorithm:

  • Mutual exclusion between N peer processes using multicast
  • Entering: send multicast message and enters when replied by all other processes
  • Communication between processes and each one has Lamport clock
  • Entering messages <T, pi> T timestamp and pi process’ id.
  • Process’ state: RELEASED, WANTED, HELD
  • If all process are in RELEASED reply¬†immediately, if any is in HELD waits
  • Concurrent requests ordered by T and then by pi
  • Entering 2(N – 1) or 1 when hardware support for muticast
  • Synchronization delay only 1 message

Maekawa’s Voting Algorithm:

  • Subsets of all processess
  • Subsets share at least one process
  • Entering: send message to your subset and wait for all to reply
  • A process reply only if has not HELD state and has not replied to other process already
  • Leaving: Process send exiting message and others pop next one from the queue
  • Dead-lock prone
  • Bandwidth: Enterying 2*sqrt(N), Leaving sqrt(N)

Process Election:

Measurement

  • Bandwidth utilization
  • Turnaround Time

Ring-based Algorithm:

  • Initially all non-participants, anyone can begin one
  • Process marks itself as participant and sends election message to its neighbour
  • Receiver compares identifier. If greater, forwards msg, if not and it is not a participant, substitutes the identifier and forwardit. But do not forward any message if it is already a participant
  • If the received message is the same identifier, becomes coordinator and sends elected to neighbour
  • When elected process marks itself as non-participant

Bully Algorithm:

  • Allows process to crash during election, but message delivery reliable
  • Assumes synchronous system
  • Each process knows which processes have higher identifiers
  • Process begins election when, through timeouts, finds coordinator has died
  • If the process has the highest id elects itself as coordinator, sending coordinator message
  • Other processes begin election sending an election message to those with higher identifiers and waits answer, if timeout elects itself as coordinator and announces to lower ids
  • Receiver of election begins another election
  • Two processes may announce being coordinators at the same time
  • O(N^2) in the worst case or N – 2 in the best