Leader Elections Flashcards
What are the use cases for Leader Elections?
1.When each progress is roughly the same and there is no clear for a permanent assigned leader.
2.When the cluster is performing a complex task that requires close collaboration. The division of work where assigning work to specific processes and combining the results from all the processes.
3.When the system executes may distributed writes to a disk and requires good consistency.
What are some advantages of Leader Elections?
-Makes systems easier for humans to design and manage because all concurrency is in a single place, reduces partial failure modes, and single place to look for logs and metrics.
-Can work more efficiently because it informs other systems about changes, which can be used every time.
-Can be easier to write software compared with other approaches like quorum, where it would need to consider that other systems may be working on the same state at the same time.
What are the stages of Leader Election?
1.Before a Distributed task has Begun, all network processes unaware which process will serve as the coordinator of the task.
2. During the election, the processes communicate among themselves in order to decide which of them will get into the “leader” state.
3.After a successful leader election:
-States of processes are divided into elected and not-elected states.
-Once elected, it remains as elected until next election.
-Exactly one process becomes elected.
-The rest determine that they are not elected.
What are the condition for the Leader Election?
-Termination: The leader election algorithm should finish within a finite time once the leader is selected.
-Uniqueness: There is exactly one process that considers itself as leader.
-Agreement: All other processes know who the leader is.
Leader Election Setups:
-Communication mechanism: the processes are either: synchronous, or asynchronous.
-Identifiers: whether messages are not reliably sent within a timeframe or in any order, cannot guarantee both safety and liveness.
-Network topology: how the physical and logical arrangement of processes and connections are organised in a network.
-Size of the network: the algorithm may use knowledge of the number of processes in the system.
What are the Performance Properties of the Ring Leader Algorithm?
Best case: election initiator has highest identifier
-N election messages followed by N elected messages
-Total messages: 2N messages
-Turnaround time: 2N -1
Worst case: anti-clockwise neighbor has highest identifier
-N-1 election messages followed by N election messages with the highest identifier,
-Total Messages: 3N-1
-Turnaround time: 3N -1
What happens when multiple processes initiate elections concurrently?
-The participant flag triggers a process to stop election messages with lower identifiers but election messages with higher identifiers will still pass.
-In the worst case all processes start an election at the same time and the identifiers in the ring are ordered.
-This result in N-1 additional elections, which causes N-1 + N-2 ..+ 2+1 additional messages to be sent.
-In total N(N-1)/2 , additional messages would be sent in the worst case scenario.
What is the Bully Election Algorithm and what does the algorithm assume?
The Bully algorithm dynamically elects a coordinator or leader from a group of distributed computer processes.
It elects the process with the highest process ID number as the coordinator, from amongst the non-failed processes.
The algorithm assumes that:
-The system is synchronous-guaranteed is reliable
-Message delivery between processes is reliable
-Processes may fail at any time, including during execution of the algorithm
-A process fails by stopping and returns from failure by restarting
-There is a failure detector which detects failed processes (safety)
-Each process knows its own process id and address, and that of every other process
What’s the Bully Election Performances?
Best case, One election:
-The coordinator failure was detected by the process with the second highest identifier, and it immediately elects itself as it has the highest identifier now.
-Total messages: N -2 coordinator messages
-Turnaround time : 1 message
Worst case, One election:
-The coordinator failure was detected by the process with the lowest identifier
-Total messages: N-1 + N-2 +… 1 election message +
N-2 + N-3 + …1 answer messages +
N-1 coordinator messages =
N(N-1) messages, O(N2)
-Turnaround time : O(N) (two messages plus a timeout)
FAILURE:
-If a failed process detector is unreliable
-If the failed process is the one w the highest id and if crashed processes are replaced by processes with the same identifiers: New process sends coordinator message just at the same time as the next highest processor also sends one.
Multiple Elections:
-The outcome would be the same, the process with the highest ID would claim victory.
-
What are the Safety and Liveness Properties of Bully Election:
Safety:
-A lower id process always yields to a higher id one
-Failure of a process might lead to two coordinators
Liveness:
-Every process which participates in the elections knows the coordinator at the end.
-Multi concurrent elections do not change the outcome of the election.
