Namespace AS2.Subroutines.LeaderElectionSync

Classes

SubLeaderElectionSync

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

Elects a leader among the particles connected by a circuit, using a second circuit for synchronization. The partition sets identifying both circuits must be given as parameters and the circuits must be established before the corresponding rounds. The same two circuits must be used for the entire procedure. It is possible to run multiple synchronized instances of this procedure by establishing multiple different election circuits but using the same synchronization circuit. The more particles participate in the synchronization and the second phase of the algorithm, the lower the chances of electing multiple leaders will be (but at the cost of a slightly longer runtime).

The sequence of calls should be as follows:
Init(int, int, bool, int, bool) to initialize the subroutine.
In the beep activation: Call ActivateReceive(), then call NeedSyncCircuit() to check whether the synchronization circuit has to be established, then call ActivateSend() with the correct circuit.
You do not have to call NeedSyncCircuit() and ActivateSend() in the same activation as ActivateReceive(), allowing you to pause the leader election as long as necessary to do anything else inbetween. The procedure will work as long as the correct circuits are established before the ActivateSend() calls and the corresponding beeps are received in the very next round by calling ActivateReceive().
Generally, the synchronization circuit must be established before calling ActivateSend() in the last one or two rounds of each phase, i.e., in round 1 of phase 1 and rounds 1 and 2 of phase 2.
Checking whether the algorithm is finished is best done after the ActivateReceive() call.

Phase 1 (2 Rounds):
Round 0: Listen for continuation beep on synchronization circuit, move on to next phase if no beep is received.
Leader candidates toss a coin and send a beep on the election circuit if the result is HEADS.
Round 1: Receive the HEADS beep and withdraw candidacy if coin toss result was TAILS.
Send a beep on the synchronization circuit if this was the case.

Phase 2 (3 Rounds):
Round 0: Listen for continuation beep on synchronization circuit, start next iteration or terminate if no beep is received.
Leader candidates toss a coin and send a beep on the election circuit if the result is HEADS.
Round 1: Receive the HEADS beep and withdraw candidacy if coin toss result was TAILS.
Phase 2 candidates toss coin and send beep on the synchronization circuit if the result is HEADS.
Round 2: Phase 2 candidates receive the HEADS beep and withdraw candidacy if the coin toss result was TAILS.
Send a beep on the synchronization circuit if this was the case.
This phase is just used to increase the duration for which the competition is executed. 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. However, if the synchronization circuit is large, this version of the leader election algorithm has better chances of success than the basic version, for the price of taking a little more time.