Distributed Algorithms
- Reference: SGG7, 18.6-18.7
- Communication
in networks is implemented in a process on one machine communicating with
a process on another machine
- See CS430 for details
- A distributed algorithm is an algorithm, run on a distributed system, that does not assume the previous existence of a central coordinator.
- A distributed system is a collection of processors that do not share memory or a clock. Each processor has its own memory, and the processors communicate via communication networks.
- We will consider two problems requiring distributed algorithms, the coordinator election problem and the value agreement problem (Byzantine generals problem)
Election Algorithms
Election Algorithms
- The coordinator election problem is to choose a process from among a group of processes on different processors in a distributed system to act as the central coordinator.
- An election algorithm is an algorithm for solving the coordinator election problem. By the nature of the coordinator election problem, any election algorithm must be a distributed algorithm.
-a group of processes on different machines need to choose a
coordinator
-peer
to peer communication: every process can send messages to every other process.
-Assume
that processes have unique IDs, such that one is highest
-Assume
that the priority of process Pi
is i
(a) Bully Algorithm
Background: any process Pi
sends a message to the current coordinator; if no response in T time units, Pi tries to elect itself as leader. Details follow:
Algorithm for process Pi
that detected the lack of coordinator
- Process Pi sends an “Election” message to every
process with higher priority.
- If no other process responds, process Pi starts the
coordinator code running and sends a message to all processes with lower
priorities saying “Elected Pi”
- Else, Pi waits for T’
time units to hear from the new coordinator, and if there is no response à
start from step (1) again.
Algorithm for other processes (also called Pi)
If
Pi is not the coordinator
then Pi may receive either
of these messages from Pj
if
Pi sends “Elected Pj”;
[this message is only received if i < j]
Pi
updates its records to say that Pj
is the coordinator.
Else
if Pj sends
“election” message (i > j)
Pi
sends a response to Pj
saying it is alive
Pi
starts an election.
(b) Election In A Ring => Ring Algorithm.
-assume that processes form a ring: each process only sends
messages to the next process in the ring
- Active list: its info on all active processes, including itself
- assumption: message continues around the ring even if a
process along the way has crashed.
Background: any process Pi
sends a message to the current coordinator; if no response in T time units, Pi initiates an election
- initialize active list to empty.
- Send an “Elect(i)” message
to the right and add i to active list.
If a process receives an “Elect(j)” message
(a)
this is the first message sent or seen
initialize
its active list to [i,j]; send “Elect(i)” + send
“Elect(j)”
(b)
if (i != j), add i to active list + forward “Elect(j)” message to
the next process
(c)
otherwise (i = j), so process i has complete set of active processes in its
active list.
=>
choose highest process ID + send “Elected (x)” message to neighbor
If a process receives “Elected(x)” message,
set
coordinator to x
Example:
Suppose that we have four processes arranged in a ring: P1 à P2 à
P3 à
P4 à
P1 …
P4 is coordinator
Suppose P1 + P4 crash
Suppose P2 detects that coordinator P4 is not responding
P2 sets its active list to [ ]
P2 sends “Elect(2)” message to P3; P2 sets
active list to [2]
P3 receives “Elect(2)”
This message is the first message seen, so P3 sets its
active list to [2,3]
P3 sends “Elect(3)” towards P4 and then sends
“Elect(2)” towards P4
The messages pass P4 +
P1 and then reach P2
P2 adds 3 to its active list [2,3]
P2 forwards “Elect(3)” to P3
P2 receives the “Elect(2) message
P2
chooses P3 as the highest process in its list [2, 3] and sends an
“Elected(P3)” message
P3 receives the “Elect(3)” message
P3
chooses P3 as the highest process in its list [2, 3] and then sends an
“Elected(P3)” message
Note: The last two messages can be processed in either order and the result will be the same.
Byzantine Generals Problem
Intuition: Only want to proceed with the plan of attack if
they are sure everyone else agrees
Can't trust other generals.
-If generals can't trust one another they can never be sure
if they should attack.