Class 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.

Inheritance

object

Subroutine

SubLeaderElectionSync

Namespace: AS2.Subroutines.LeaderElectionSync

Assembly: .dll

Syntax

public class SubLeaderElectionSync : Subroutine

Constructors

SubLeaderElectionSync(Particle)

Declaration

public SubLeaderElectionSync(Particle p)

Parameters

Type	Name	Description
Particle	p

Fields

activeColor

Color for particles that are no leader candidate but still an active candidate in phase 2.

Declaration

public static readonly Color activeColor

Field Value

Type	Description
Color

beepFromHeads

Declaration

private ParticleAttribute<bool> beepFromHeads

Field Value

Type	Description
ParticleAttribute<bool>

beepFromTails

Declaration

private ParticleAttribute<bool> beepFromTails

Field Value

Type	Description
ParticleAttribute<bool>

candidateColor

Color for particles that are still active leader candidates.

Declaration

public static readonly Color candidateColor

Field Value

Type	Description
Color

controlColor

Declaration

private ParticleAttribute<bool> controlColor

Field Value

Type	Description
ParticleAttribute<bool>

finished

Declaration

private ParticleAttribute<bool> finished

Field Value

Type	Description
ParticleAttribute<bool>

firstPhase

Declaration

private ParticleAttribute<bool> firstPhase

Field Value

Type	Description
ParticleAttribute<bool>

heads

Declaration

private ParticleAttribute<bool> heads

Field Value

Type	Description
ParticleAttribute<bool>

isLeaderCandidate

Declaration

private ParticleAttribute<bool> isLeaderCandidate

Field Value

Type	Description
ParticleAttribute<bool>

isPhase2Candidate

Declaration

private ParticleAttribute<bool> isPhase2Candidate

Field Value

Type	Description
ParticleAttribute<bool>

kappa

Declaration

private ParticleAttribute<int> kappa

Field Value

Type	Description
ParticleAttribute<int>

partitionSetElect

Declaration

private ParticleAttribute<int> partitionSetElect

Field Value

Type	Description
ParticleAttribute<int>

partitionSetSync

Declaration

private ParticleAttribute<int> partitionSetSync

Field Value

Type	Description
ParticleAttribute<int>

passiveColor

Color for particles that are no candidates but still not finished.

Declaration

public static readonly Color passiveColor

Field Value

Type	Description
Color

repetitions

Declaration

private ParticleAttribute<int> repetitions

Field Value

Type	Description
ParticleAttribute<int>

retiredColor

Color for particles that are finished and no leader candidate.

Declaration

public static readonly Color retiredColor

Field Value

Type	Description
Color

round

Declaration

private ParticleAttribute<int> round

Field Value

Type	Description
ParticleAttribute<int>

Methods

ActivateReceive()

The first half of the beep activation. Must be called while the beeps of the previous ActivateSend() call can still be read on the current pin configuration (i.e., the pin configuration must not be changed before this method is called). It may however be changed after this call, as long as the correct pin configuration is planned again before the next ActivateSend() call. Check NeedSyncCircuit() whether the correct pin configuration is the synchronization circuit.

Declaration

public void ActivateReceive()

ActivateSend()

The second half of the beep activation. Must be called only when the correct pin configuration has been established. Call NeedSyncCircuit() to check which pin configuration is required. The beeps sent by this method must be received by the next call of ActivateReceive().

Declaration

public void ActivateSend()

GetRound()

Gets the current round counter of the participant. See the class documentation for an overview of what happens during each round.

Declaration

public int GetRound()

Returns

Type	Description
int	The current value of the round counter.

Init(int, int, bool, int, bool)

Initializes the subroutine for a new leader election.

Declaration

public void Init(int partitionSetElection, int partitionSetSynchronization, bool controlColor = false, int kappa = 3, bool startAsCandidate = true)

Parameters

Type	Name	Description
int	partitionSetElection	The index of the partition set used to run the leader election. This should always identify the same circuit throughout the procedure. There may be multiple different election circuits used in parallel by different sets of participants.
int	partitionSetSynchronization	The index of the partition set used to run the synchronization and secondary competition. This should always identify the same circuit throughout the procedure. Multiple sets of participants can share the same synchronization circuit to benefit from a higher success probability. You can increase the number of participants by letting non-candidate particles participate using the startAsCandidate parameter.
bool	controlColor	Whether the subroutine should set the particle color according to the leader election.
int	kappa	The number of repetitions of the second phase. The more repetitions are made, the lower the chances of electing multiple leaders become.
bool	startAsCandidate	Whether this participant should start the leader election as a candidate. Useful for restricting the set of candidates beforehand. Note that it is possible that no leader is elected in case there are no candidates to start with.

IsCandidate()

Checks whether the LE participant represented by this subroutine is still a leader candidate.

Declaration

public bool IsCandidate()

Returns

Type	Description
bool	true if and only if this participant still has a chance of becoming the leader.

IsFinished()

Checks whether the leader election procedure has finished. Once this returns true, no activation method calls will change the state of this subroutine.

Declaration

public bool IsFinished()

Returns

Type	Description
bool	true if and only if the leader election procedure has terminated.

IsLeader()

Checks whether this LE participant has been elected as a leader. Note that for small sets of particles and a low value of kappa, it is possible that multiple participants are elected as leaders.

Declaration

public bool IsLeader()

Returns

Type	Description
bool	true if and only if the leader election procedure has terminated and this participant is still marked as a leader candidate.

IsPhase2Candidate()

Checks whether the LE participant represented by this subroutine is currently a phase 2 candidate. Phase 2 candidate are independent of leader candidates and are reinstated in each iteration of the second phase.

Declaration

public bool IsPhase2Candidate()

Returns

Type	Description
bool	true if and only if this participant is currently a phase 2 candidate and is not still running phase 1.

NeedSyncCircuit()

Declaration

public bool NeedSyncCircuit()

Returns

Type	Description
bool

TossCoin()

Tosses a fair coin and returns the result. Also stores the result in the heads attribute.

Declaration

private bool TossCoin()

Returns

Type	Description
bool	true if the result was HEADS (probability of 1/2), false otherwise.

UpdateColor()

Updates the particle's color based on the current leader election state.

Declaration

private void UpdateColor()