12 - Election

Question 1

Describe the election problem

Answer 1

A single process should get the privilage to take some action, this process has to be elected/agreed upon by all processes.

Question 2

What is a big assumption in the election problem?

Answer 2

In order for a deterministic algorithm, each process must have an unique ID. Otherwise nodes are not able to identify/vote themselves.

Question 3

Explain the non-comparison-based solution to the election problem in rings.

Answer 3

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.

Question 4

On what type of topology does the Hirschber and Sinclair algorithm work?

Answer 4

Bidirectional ring

Question 5

What is the main idea of does the Hirschber and Sinclair algorithm?

Answer 5

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.

Question 6

Explain how the election probe propegates in Hirschberg and Sinclair.

Answer 6

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.

Question 7

When does a node stop sending probes in the Hirschberg and Sinclair algorithm?

Answer 7

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.

Question 8

Explain the optimization imposed for the Hirschberg and Sinclair algorithm.

Answer 8

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.

Question 9

What kind of topology is required for Chang-Roberts algortihm?

Answer 9

unidirectional ring

Question 10

Explain Chang-Roberts election algorithm.

Answer 10

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.

Question 11

What is chang-roberts average message complexity?

Answer 11

n log(n)

Question 12

What is chang roberts worst case message complexity, and when does it occur?

Answer 12

n^2, when the order of the ids is decreasing

Question 13

What topology was the peterson’s election algorithm designed for/

Answer 13

unidirectional ring topology

Question 14

Wh

From what other algorithm is Peterson’s an adaptation?

Answer 14

Optimised Hirschberg and Sinclair, but then in unidirectional rings

Question 15

Explain how a single round of Peterson’s election algorithm works.

Answer 15

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.

Question 16

In peterson’s election algorithm, when is election concluded?

Answer 16

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.

Question 17

In peterson’s election algorithm, what is the message complexity?

Answer 17

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)

Question 18

In peterson’s algorithm, why does the second node send the maximum computation, instead of the upstreams neighbours id?

Answer 18

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.

Question 19

What is the major problem with Peterson’s election algorithm?

Answer 19

All other nodes are passive, so no other process ever concludes which node has been elected.

Question 20

What topology is assumed for Afek and Gafni’s election algorithm?

Answer 20

Complete network (=fully connected)

Question 21

Explain what the basic idea is behind synchronous Afek and Gafni’s election algorithm.

Answer 21

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.

Question 22

In the synchronous Afek and Gafni’s election algorithm, explain what the OP and CP are, and what its function is.

Answer 22

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.

Question 23

What happens in a OP when it receives an CP-message.

Answer 23

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.

Question 24

In synchronous Afek and Gafni’s election algorithm, how are CP’s and OP’s initiated?

Answer 24

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.

Question 25

What is the message complexity of synchronous Afek and Gafni’s election algorithm?

Answer 25

In every cycle (2 rounds), there has been a reduction of log(n) links being used, by sending 2 messages. In the worst case, n nodes start election simultaneously:

2n log(n)

Question 26

For Afek and Gafni’s synchronous algorithm, explain what happens in each level.

Answer 26

At each even level, the CP sends it CP-message with its level and ID. At odd levels, a CP is ready to receive ACKS.
If a level ends before all ACKS have been received, it concludes defeat and terminates.

Question 27

What is the disadvantage of not using levels in Afek and Gafni’s?

Answer 27

This has to do with the Lexicographical ordering:
Every process will prefer an older process over an higher ID. It means that a winner is guaranteed to be chosen in 2log(n) levels, and thus does not have to wait until the eventual champion wakes up. This reduces computations and number of messages in the system.

Question 28

How is a winner elected in Afek and Gafni’s sync alg?

Answer 28

A process will first compare its level, if that is equal, then it will compare ID. so (2, 5) > (1, 3000)
A winner knows it has been elected, if it has received a ACK from every process.

Question 29

in Afek and Gafni’s sync alg., why does a recaptured process not need to notify its original caputurer that the previous ACK is no longer valid?

Answer 29

The orignial capturer will eventuall have to communicate with the recapturer of that node. During that communcation, the original capturer cannot receive an ACK, otherwise the node would not have been recaptured. Thus the original capturer can never be the winner.

Question 30

Explain the basic idea of Afek and Gafni’s async alg.

Answer 30

Any Process P can start an election at any time. It will then try to capture each other process one by one. A capture of Q is confirmed with an ACK/OK and the level of P is increased by one. An unsuccesful capture of Q yields no response, and leads to P eventually being captured itself.

Question 31

Explain what happens in Afek and Gafni’s async alg. when process Q is being recaptured and why.

Answer 31

When Q was captured by R, but is recaptured by P, it must then try to kill process R. The reason for this is that R currently still assumes it has a chance to win (as it once possesed Q), but Q has learned this can never be. Furthermore, keeping R alive can then only

Question 32

In Afek and Gafni’s async alg. explain when the father variable is overwritten, and when the node adapts its new values.

Answer 32

In the simple case that Q had not been captured before, then Q adapts the value of P and assigns it its father

Otherwise, Q will adapt better values whenever it receives them, but only will update its father whenever the father confirms the kill (executed by Q).

Question 33

Give four reasons for how a (re)capture can fail in Afek and Gafni’s async alg..

Answer 33

1. P is not strong enough to capture Q in the first place. (Q rejects)
2. The kill message from Q is rejected by R, as R has grown stronger meanwhile
3. The Kill confirmation (OK) from R is ignored by Q as Q was recaptured by an even stronger process (S)
4. P may reject the OK from Q, as P was captured in the meantime.

Question 34

what is the message complexity of Afek and Gafni’s async alg.

Answer 34

n log(n)

no explanation provided