12 - Election Flashcards
Describe the election problem
A single process should get the privilage to take some action, this process has to be elected/agreed upon by all processes.
What is a big assumption in the election problem?
In order for a deterministic algorithm, each process must have an unique ID. Otherwise nodes are not able to identify/vote themselves.
Explain the non-comparison-based solution to the election problem in rings.
Asuming we want to elect the node with the mininum ID. Then we assume that 1 is the lowest possible ID a process could have obtained. After n rounds, any node can conclude that ID=1 does not exist, otherwise it would have started broadcasting. So now they assume ID=2 is the lowest. This continues untill a process can safely assume itself is the lowest ranking process and broadcasts this.
On what type of topology does the Hirschber and Sinclair algorithm work?
Bidirectional ring
What is the main idea of does the Hirschber and Sinclair algorithm?
Each node tries to find a neighbour with an higher ID. The size of whats concidered neighbours is increased each round. Once a process receives its own messages, it can conclude it has been elected.
Explain how the election probe propegates in Hirschberg and Sinclair.
It concideres 2^{k-1} neighbours in each direction in each round, starting with round 1. This equals a neighbour set size of 2^{k}+1 per round.
Every round, the original node sends out a probe that is forwarded for 2^{k-1} times. The last node to receive the hop will respond with an OK.
When does a node stop sending probes in the Hirschberg and Sinclair algorithm?
Whenever a node receives a probe itself, containing a lower ID than its own, it will not forward/reply to the message. Thus the original probe will not receive two OK’s, and hence is forced to stop.
Explain the optimization imposed for the Hirschberg and Sinclair algorithm.
Instead of sending your ID to exponentially more neighbours; only send your ID to the next two active neighbours. When neighbours receive an ID that is larger than its own, it becomes passive and only relays the messages.
What kind of topology is required for Chang-Roberts algortihm?
unidirectional ring
Explain Chang-Roberts election algorithm.
Any node can spontaneously start to send its own ID to the next node. When a node receives an nid:
if nid > id: forward nid
if id > nid: send id (if not already done)
if id == nid: you are elected.
What is chang-roberts average message complexity?
n log(n)
What is chang roberts worst case message complexity, and when does it occur?
n^2, when the order of the ids is decreasing
What topology was the peterson’s election algorithm designed for/
unidirectional ring topology
Wh
From what other algorithm is Peterson’s an adaptation?
Optimised Hirschberg and Sinclair, but then in unidirectional rings
Explain how a single round of Peterson’s election algorithm works.
Node 1 sends its ID to its downstream neighbour node 2. Node 2 evaluates the max of its own ID and ID1, and send this value downstream towards node 3. This node now virtually has all information as if it were node 2. Therefor it makes the comparisson wether the ID of node 2 is larger than node’s 3. If this is the case, it means node 2 would have been active. If node, node 2 would have become passive.
Finally, node 3 adapts itself to become node 2.
In peterson’s election algorithm, when is election concluded?
When an node sends out a probe containing its ID, and all the other nodes are passive, such that it is relayed back to the only active node. Then that node is elected.
In peterson’s election algorithm, what is the message complexity?
The maximum number of rounds is log(n). In each round, 2 messages are send across each link (there are e=n links in a ring).
2n log(n)
In peterson’s algorithm, why does the second node send the maximum computation, instead of the upstreams neighbours id?
In order for the last node to compute the election, it would need to compute the maximum three times. (either max(max(n1,n2), max(n2,n3)))
Anyways, the second and third node therefor share a computation. If this computation were to be shared, it reduces the computations required on all nodes.
What is the major problem with Peterson’s election algorithm?
All other nodes are passive, so no other process ever concludes which node has been elected.
What topology is assumed for Afek and Gafni’s election algorithm?
Complete network (=fully connected)
Explain what the basic idea is behind synchronous Afek and Gafni’s election algorithm.
Any node (P) can sponaneously start an election. It will send it’s ID to a subset of F, called G. After process P has received an ACK from every process in G, it doubles G in size (and excludes any nodes from previous rounds). it does this untill F == G, and thus that node is elected.
In the synchronous Afek and Gafni’s election algorithm, explain what the OP and CP are, and what its function is.
CP: Candidate Process, is responsible for sending its process’ ID each round to a subset of other nodes.
OP: Ordinary Process, this (sub)process within a processor is responsible for handling incomming candidate messages and replying ACKs.
What happens in a OP when it receives an CP-message.
If the (level,ID) is higher than its own, an OP will adapt these values as its own and return a ACK.
This adaption speeds up the election, as other processes will encounter their competitors faster.
In synchronous Afek and Gafni’s election algorithm, how are CP’s and OP’s initiated?
Any (and multiple) nodes may start the algorithm spontaneously. This will spawn a CP as well as a OP on the same processor. Whenever a process receives a CP-message, it wakes up and only spawns an OP.
