Namespace AS2.Subroutines.LeaderElection

Classes

SubLeaderElection

Implements the leader election algorithm from https://arxiv.org/abs/2105.05071v1.

Elects a leader among the particles connected by a circuit. The partition set identifying this circuit must be given as a parameter (i.e., the circuit must be created before the leader election can start). The same circuit must be used for the entire procedure.

The sequence of calls should be as follows:
Init(int, bool, int, bool) to initialize the subroutine.
Then, in the beep activation: ActivateReceive() with the current pin configuration so that beeps can be received, followed by ActivateSend() with a pin configuration that allows sending beeps on the LE circuit.
This separation allows you to change the pin configuration or pause the leader election procedure.
The algorithm is already finished after the last ActivateReceive() call.

Phase 1 (2 Rounds):
Round 0: Leader candidates toss a coin and send a beep if the result is HEADS.
Round 1: Store received beep and send beep if the result was TAILS.
Next round 0: If both HEADS and TAILS occurred, all candidates with TAILS withdraw their candidacy. Otherwise, we move on to phase 2.

Phase 2 (4 Rounds):
Rounds 0 and 1: Same as in phase 1 but we don't do anything if only one coin toss result occurred.
Rounds 2 and 3: Same as rounds 0 and 1 but with separate candidacies and coin tosses. This step is just used to increase the duration for which the competition is executed. When only one coin toss result occurs, we either repeat phase 2 by restoring all candidacies or terminate. The number of repetitions is given as the parameter kappa.

Note that this algorithm only determines a unique leader with high probability. It is possible that more than one particle remains a candidate when the algorithm terminates, especially for a small number of particles and small value for kappa.