Elections in Distributed Systems

Elections

–       Election: choosing a unique process for a particular role

^–    All the processes agree on the unique choice

^–    For example, server in dist. Mutex assumptions

^–    Each process can call only one election at a time multiple concurrent elections can be called by different processes

^–    Participant: engages in an election each process pi has variable electedi = ? (don't know) initially process with the largest identifier wins.

^–    The (unique) identifier could be any useful value Properties

^–    [E1] electedi of a ―participant‖ process must be P (elected process=largestid) or ⊥

–       (undefined)

o   [E2] liveness: all processes participate and eventually set electedi != ⊥ (or crash) Performance

^–    overhead (bandwidth consumption): # of messages

^–    turnaround time: # of messages to complete an election

–       ring-based election algorithm

^o     Arrange processes in a logical ring

–       pi sends messages to p(i+1) mod N

o It could be unrelated to the physical configuration

o Elect the coordinator with the largest id

o Assume no failures

^–    Initially, every process is a non-participant. Any process can call an election

o Marks itself as participant

o Places its id in an election message

o Sends the message to its neighbor

o Receiving an election message

^–    if id > myid, forward the msg, mark participant

^–    if id < myid

o non-participant: replace id with myid: forward the msg, mark participant

o participant: stop forwarding (why? Later, multiple elections)

^–    if id = myid, coordinator found, mark non-participant, electedi := id, send elected

o message with myid

o Receiving an elected message

^–    id != myid, mark non-participant, electedi := id forward the msg

^–    if id = myid, stop forwarding

^–    Receiving an election message:

^–    if id > myid, forward the msg, mark participant

^–    if id < myid

^–    non-participant: replace id with myid: forward the msg, mark participant

^–    participant: stop forwarding (why? Later, multiple elections)

^–    if id = myid, coordinator found, mark non-participant, electedi := id, send elected message with

^–    myid

^–    Receiving an elected message: – id != myid, mark non-participant,

^–    electedi := id forward the msg

^–    if id = myid, stop forwarding

–       ring-based election algorithm: discussion

^o     •Properties

^o     safety: only the process with the largest id can send an elected message

^o     liveness: every process in the ring eventually participates in the election; extra elections are stopped

^o     Performance

^o     one election, best case, when?

^o     N election messages

^o     N elected messages

^o     turnaround: 2N messages

^o     one election, worst case, when?

^o     2N - 1 election messages

^o     N elected messages

^o     turnaround: 3N - 1 messages

^o     can't tolerate failures, not very practical

–       The bully election algorithm

–       •Assumption

o   Each process knows which processes have higher identifiers, and that it can communicate with all such processes

–       •Compare with ring-based election

o   Processes can crash and be detected by timeouts

–       synchronous

–       timeout T = 2Ttransmitting (max transmission delay) + Tprocessing (max processing delay)

–       •Three types of messages

o   Election: announce an election

o   Answer: in response to Election

o   Coordinator: announce the identity of the elected process

–       The bully election algorithm: howto

§  Start an election when detect the coordinator has failed or begin to replace the coordinator, which has lower identifier

o   Send an election message to all processes with higher id's and waits for answers (except the failed coordinator/process)

§  If no answers in time T

o   Considers it is the coordinator

o   sends coordinator message (with its id) to all processes with lower id's

§  else

o   waits for a coordinator message and starts an election if T‘ timeout

o   To be a coordinator, it has to start an election

§  A higher id process can replace the current coordinator (hence ―bully‖)

o   The highest one directly sends a coordinator message to all process with lower identifiers

§  Receiving an election message

o   sends an answer message back

o   starts an election if it hasn't started one—send election messages to all higher-id processes (including the ―failed‖ coordinator—the coordinator might be up by now)

§  Receiving a coordinator message

o   set electedi to the new coordinator

–       The bully election algorithm: discussion

–       Properties

–       safety:

–       a lower-id process always yields to a higher-id process

–       However, it‘s guaranteed

^–         if processes that have crashed are replaced by processes with the same identifier since message delivery order might not be guaranteed and

^–         failure detection might be unreliable

^–         liveness: all processes participate and know the coordinator at the end

^–         Performance

^–         best case: when?

^–         overhead: N-2 coordinator messages

^–         turnaround delay: no election/answer messages