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

Inheritance

object

Subroutine

SubLeaderElection

Namespace: AS2.Subroutines.LeaderElection

Assembly: .dll

Syntax

public class SubLeaderElection : Subroutine

Constructors

SubLeaderElection(Particle)

Declaration

public SubLeaderElection(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>

partitionSetId

Declaration

private ParticleAttribute<int> partitionSetId

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

ActivateBeep()

Shorthand for calling ActivateReceive() and then ActivateSend() for when the pin configuration should not be changed inbetween.

Declaration

public override void ActivateBeep()

Overrides

Subroutine.ActivateBeep()

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.

Declaration

public void ActivateReceive()

ActivateSend()

The second half of the beep activation. Must be called when the correct pin configuration has been established. 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, bool, int, bool)

Initializes the subroutine for a new leader election.

Declaration

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

Parameters

Type	Name	Description
int	partitionSet	The index of the partition set used to run the leader election. This should always identify the same circuit throughout the procedure.
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.

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()