LeaderElection

Question 1

What are distributed algorithms used for?

Answer 1

Leader election, consensus, mutual exclusion, and global predicate evaluation.

Question 2

What is the purpose of a leader in distributed systems?

Answer 2

To coordinate access to resources, execute specific tasks, or act as an observer for global predicate evaluation.

Question 3

What are the two main scenarios in leader election?

Answer 3

1) All processes/agents are equally suitable. 2) Some processes/agents are better suited than others.

Question 4

When are elections needed in distributed systems?

Answer 4

1) System initialization without a leader. 2) Current coordinator crashes or retires. 3) A specific task requires a leader.

Question 5

What must happen when an election algorithm terminates?

Answer 5

A single process is selected as the leader, and all processes agree on its identity.

Question 6

What is the main assumption in traditional leader election algorithms?

Answer 6

Every process has a unique ID and knows the IDs of all other processes.

Question 7

How does the Bully Algorithm work?

Answer 7

Higher-numbered processes “bully” lower-numbered processes out of the election until only one process remains.

Question 8

What is the complexity of the Bully Algorithm if the highest ID process starts the election?

Answer 8

n-1 messages.

Question 9

What is the complexity of the Bully Algorithm if the lowest ID process starts the election?

Answer 9

n(n-1) messages.

Question 10

How does the Ring Algorithm work?

Answer 10

Processes are arranged in a logical ring, and an ELECTION message circulates until it returns to the initiator, who then declares the leader.

Question 11

What is the complexity of the Ring Algorithm?

Answer 11

2n messages (two full laps around the ring).

Question 12

Why are traditional leader election algorithms unsuitable for wireless and dynamic systems?

Answer 12

They assume nodes know each other a priori, which excludes dynamic scenarios where processes come and go.

Question 13

How do wireless election algorithms work?

Answer 13

Any node can initiate an election by sending an ELECTION message to its neighbors, building a spanning tree to elect the most eligible node.

Question 14

What is distributed aggregation?

Answer 14

Computing an aggregation function (e.g., max, min, average) from the local states of processes.

Question 15

What is gossiping in distributed aggregation?

Answer 15

Processes share and update their knowledge of the aggregation function by periodically exchanging values with neighbors.

Question 16

How does Max/Min aggregation work?

Answer 16

The maximum or minimum value is spread from process to process, eventually reaching all nodes in the network.

Question 17

How does average aggregation work?

Answer 17

Each process continuously computes the average with its neighbors, contributing to the convergence of the algorithm.

Question 18

What are some challenges in handling dynamic values in distributed aggregation?

Answer 18

Values may change over time, and solutions include dividing time into epochs or letting aggregate values “evaporate” to recompute them.