Election

Fundamentals

• Any process can call for an election and call for at most one election at a time

• Multiple processes are allowed to call an election simultaneously
• All of them together must yield only a single leader

• The result of an election does not depend on which process calls for it

• Processes have unique identifiers (UID)

• Leader is the one with Largest identifier, which is unique

• At any point in time, a process is
• A participant, meaning that it is engaged in some run of the election algorithm
• A non-participant, meaning that it is not currently engaged in any election

• Each process has a variable
• Contains the identifier of the elected process
• Sets to the special value ⊥ (not yet defined) when process first becomes a participant in an election

Properties

• E1 (safety)
• A participant process has = ⊥ or = for some noncrashed process that will be chosen at the end of the run with the largest identifier

• E2 (liveness)
• All non-crashed processes participate and will eventually set elected i ≠⊥

Performance

• Bandwidth utilisation
• Proportional to total number of messages sent

• Turnaround
• the number of serialised message transmission time between initiation and termination of a single run
 

Comparisons and Details of 2 Election Algorithms

FYI: Hover on an algorithm then click "OPEN", you could see the details of the algorithm