Home | | Distributed Systems | | Distributed Systems | Elections in Distributed Systems

Chapter: Distributed Systems - Synchronization and Replication

Study Material, Lecturing Notes, Assignment, Reference, Wiki description explanation, brief detail

Elections in Distributed Systems

– Election: choosing a unique process for a particular role – All the processes agree on the unique choice

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

 

Study Material, Lecturing Notes, Assignment, Reference, Wiki description explanation, brief detail


Copyright © 2018-2020 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.