Class SubPASC

Implements the PASC (Primary-And-Secondary-Circuit) algorithm (https://drops.dagstuhl.de/opus/volltexte/2022/16793/).

For a sequence of particles p0,p1,...,pm with pp being the leader, iteratively deactivates every second active particle in the sequence. Takes O(log(m)) iterations to deactivate all particles. In the process, each particle pi receives the distance to p0 (= i) in binary, with bits arriving in increasing order.

Disclaimer: Only works if the number of pins per edge is at most 5.

Setup:
Call Init(bool, Direction, Direction, int, int, int, int, int, int, bool) and tell each particle in the sequence whether it is p0, the directions to its predecessor and successor particles (NONE for the predecessor/successor of the first/last particle, resp.), which pins and partition set IDs to use for the two circuits, and whether it should start active (it is possible to start the procedure with some particles already passive).
Every particle will use 2 partition sets and use 2 pins for its predecessor and 2 (other!) pins for its successor. Make sure that for neighboring particles p(i), p(i+1), the primary successor pin of p(i) is connected to the primary predecessor pin of p(i+1) and the same holds for the secondary pins.

Usage:
After initializing the sequence of particles, call SetupPC(PinConfiguration) to make each particle establish its partition sets. This does not plan the pin configuration yet, in the case that other changes are required. You can then call ActivateSend() (after planning the pin configuration if necessary) to send the beeps. This is only necessary for the leader particle.
In the next round, you have to call ActivateReceive() before changing the pin configuration so that the received beeps can be processed. After this call, you can read the received bit and check if the particle became passive in this round. Then you can repeat the process.
The subroutine does not include a termination check. You need to terminate manually when no particle of the sequence has become passive. It is no problem to keep the algorithm running after the last particle became passive. This allows you to run multiple instances of PASC and keep them running until each instance has finished.

Early termination:
If you use PASC to compare the distance bits to another sequence of bits which may be shorter than the PASC result (i.e., the compared sequence has a lower most significant bit than the number of PASC iterations), you can perform a cutoff to save a few rounds as follows:
Instead of calling SetupPC(PinConfiguration), call SetupCutoffCircuit(PinConfiguration) and plan the resulting pin configuration. This will setup a circuit where all active non-leader particles disconnect their predecessor and successor. After planning the pin configuration, call SendCutoffBeep() instead of ActivateSend() (but call it on all particles, not just the leader). This will make the active non-leader particles send a beep to their successor on both circuits, causing all particles after the first active non-leader particle to receive a beep. These are exactly the particles that will receive at least one 1-bit in the future PASC iterations, i.e., the particles whose PASC value will definitely be greater than the compared bit sequence. All particles that do not receive a beep (the leader and all connected passive particles) will only receive 0-bits, i.e., their comparison result is already finished since the compared sequence also has only 0-bits left. To read the result of this cutoff, call ReceiveCutoffBeep() instead of ActivateReceive(). The result of GetReceivedBit() will be 1 if the particle has received the cutoff bit, and 0 otherwise.
Afterwards, it is still possible to continue the PASC procedure where it was interrupted, starting with SetupPC(PinConfiguration).

Inheritance

object

Subroutine

SubPASC

Namespace: AS2.Subroutines.PASC

Assembly: .dll

Syntax

public class SubPASC : Subroutine

Constructors

SubPASC(Particle)

Declaration

public SubPASC(Particle p)

Parameters

Type	Name	Description
Particle	p

Fields

becamePassive

Declaration

private BinAttributeBool becamePassive

Field Value

Type	Description
BinAttributeBool

invalidPin

Declaration

private static readonly int invalidPin

Field Value

Type	Description
int

isActive

Declaration

private BinAttributeBool isActive

Field Value

Type	Description
BinAttributeBool

lastBitIs1

Declaration

private BinAttributeBool lastBitIs1

Field Value

Type	Description
BinAttributeBool

predPrimaryPin

Declaration

private BinAttributeInt predPrimaryPin

Field Value

Type	Description
BinAttributeInt

predSecondaryPin

Declaration

private BinAttributeInt predSecondaryPin

Field Value

Type	Description
BinAttributeInt

primaryPSetID

Declaration

private BinAttributeInt primaryPSetID

Field Value

Type	Description
BinAttributeInt

secondaryPSetID

Declaration

private BinAttributeInt secondaryPSetID

Field Value

Type	Description
BinAttributeInt

state

Declaration

private ParticleAttribute<int> state

Field Value

Type	Description
ParticleAttribute<int>

succPrimaryPin

Declaration

private BinAttributeInt succPrimaryPin

Field Value

Type	Description
BinAttributeInt

succSecondaryPin

Declaration

private BinAttributeInt succSecondaryPin

Field Value

Type	Description
BinAttributeInt

Methods

ActivateReceive()

Processes the received beep that was sent in the last round. Must be called in the next round after sending the beep and before the current pin configuration changes.

Declaration

public void ActivateReceive()

ActivateSend()

Causes the leader of the particle sequence to send the beep that deactivates half of the active particles. Must only be called after the final pin configuration has been planned.

Declaration

public void ActivateSend()

BecamePassive()

Whether this particle became passive in the last iteration.

Declaration

public bool BecamePassive()

Returns

Type	Description
bool	true if and only if the last call of ActivateReceive() has made this particle passive.

GetReceivedBit()

The bit received in the last iteration. Bits are received in ascending order and represent the number of preceding active particles including the leader.

Declaration

public int GetReceivedBit()

Returns

Type	Description
int	1 if and only if in the last call of ActivateReceive(), a beep was received on the secondary circuit, otherwise 0.

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

Initializes the PASC subroutine.

Declaration

public void Init(bool isLeader, Direction predDir, Direction succDir, int predPrimaryPin, int predSecondaryPin, int succPrimaryPin, int succSecondaryPin, int primaryPSet, int secondaryPSet, bool active = true)

Parameters

Type	Name	Description
bool	isLeader	Whether this particle is the first one in the sequence.
Direction	predDir	The direction of the predecessor in the sequence.
Direction	succDir	The direction of the successor in the sequence.
int	predPrimaryPin	The primary pin's offset in predecessor direction.
int	predSecondaryPin	The secondary pin's offset in predecessor direction.
int	succPrimaryPin	The primary pin's offset in successor direction.
int	succSecondaryPin	The secondary pin's offset in successor direction.
int	primaryPSet	The partition set ID to use for the primary circuit. Must be at most 15.
int	secondaryPSet	The partition set ID to use for the secondary circuit. Must be at most 15.
bool	active	Whether this particle should start active.

IsActive()

Whether this particle is active. The leader is always active.

Declaration

public bool IsActive()

Returns

Type	Description
bool	true if and only if this particle is active.

IsLeader()

Whether this particle is the sequence's leader.

Declaration

public bool IsLeader()

Returns

Type	Description
bool	true if and only if this particle has no predecessor.

ReceiveCutoffBeep()

Processes the received cutoff beep that was sent in the last round. Must be called in the next round after sending the cutoff beep and before the current pin configuration changes. Afterwards, GetReceivedBit() will be 1 if and only if we received the cutoff beep.

Declaration

public void ReceiveCutoffBeep()

SendCutoffBeep()

Causes the active non-leader particles to send the cutoff beep that is received by all particles that will receive at least one 1-bit in a future PASC iteration. Must only be called after the final pin configuration setup by SetupCutoffCircuit(PinConfiguration) has been planned.

Declaration

public void SendCutoffBeep()

SetupCutoffCircuit(PinConfiguration)

Sets up the cutoff circuit for early termination. The pin configuration is not planned by this method.

Declaration

public void SetupCutoffCircuit(PinConfiguration pc)

Parameters

Type	Name	Description
PinConfiguration	pc	The pin configuration to be modified. This will only modify the pins and partition sets specified for this subroutine.

SetupPC(PinConfiguration)

Sets up the primary and secondary partition sets for this particle. The next pin configuration is not set to another object by this method.

Declaration

public void SetupPC(PinConfiguration pc)

Parameters

Type	Name	Description
PinConfiguration	pc	The pin configuration to be modified. This will only modify the pins and partition sets specified for this subroutine.

SetupPascConfig(PinConfiguration, Direction, Direction, int, int, int, int, int, int, bool, bool)

Declaration

public static void SetupPascConfig(PinConfiguration pc, Direction predDir, Direction succDir, int predPinPrimary, int predPinSecondary, int succPinPrimary, int succPinSecondary, int pSetPrimary, int pSetSecondary, bool active, bool placePsets = true)

Parameters

Type	Name	Description
PinConfiguration	pc
Direction	predDir
Direction	succDir
int	predPinPrimary
int	predPinSecondary
int	succPinPrimary
int	succPinSecondary
int	pSetPrimary
int	pSetSecondary
bool	active
bool	placePsets

SetupPinConfig(PinConfiguration, bool)

Declaration

private void SetupPinConfig(PinConfiguration pc, bool cutoff = false)

Parameters

Type	Name	Description
PinConfiguration	pc
bool	cutoff