Class SubPASC2

Implements the PASC (Primary-And-Secondary-Circuit) algorithm (https://drops.dagstuhl.de/opus/volltexte/2022/16793/) with a focus on simple stripe and tree structures. See SubPASC for a detailed description of the original algorithm.

In this version, every amoebot defines each direction as successor, predecessor, neighbor or nothing. Neighbors are handled such that the primary and secondary partition sets are always connected directly, allowing stripes to share partition sets. Only two pin offsets are required, which will be used for outgoing edges (successors and neighbors in neighbor direction). For other connections (predecessors and neighbors in opposite neighbor direction), the pin offsets are inverted. The remaining functionality of the algorithm is exactly the same.

Disclaimer: The cutoff functionality might not work correctly if the leader has active predecessors.

Setup:
Call Init(List<Direction>, List<Direction>, int, int, int, int, bool, bool, Direction, bool, bool) and tell each amoebot the directions of its predecessors and successors, the pin offsets for outgoing connections, the partition set IDs, the leader and active state info, the direction of the stripe axis, and the flags for the two stripe neighbor connections. No direction should appear as predecessor and successor and no direction parallel to the stripe axis should be a successor or predecessor.

Usage:
After initializing the subroutine, call SetupPC(PinConfiguration, List<Direction>) to make each amoebot establish its partition sets. This does not change the next pin configuration object. You can then call ActivateSend() to send the beeps. This is only necessary for the leader amoebots (but it is no problem to call it on all amoebots).
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 amoebot 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 amoebot in the structure has become passive. It is no problem to keep the algorithm running after the last amoebot became passive. This allows you to run multiple instances of PASC and keep them running until each instance has finished.

Early termination:
WIP: This will not work properly on stripe structures where the leader stripe has active predecessors.
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, List<Direction>), call SetupCutoffCircuit(PinConfiguration, List<Direction>). This will setup a circuit where all active non-leader amoebots disconnect their predecessors. Then, call SendCutoffBeep() instead of ActivateSend() (but call it on all amoebots, not just the leader). This will make the active non-leader amoebots send a beep to their successor on both circuits, causing all amoebots after the first active non-leader amoebot to receive a beep. These are exactly the amoebots that will receive at least one 1-bit in the future PASC iterations, i.e., the amoebots whose PASC value will definitely be greater than the compared bit sequence. All amoebots that do not receive a beep (the leader and all connected passive amoebots) 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 amoebot 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, List<Direction>).

Inheritance

object

Subroutine

SubPASC2

Namespace: AS2.Subroutines.PASC

Assembly: .dll

Syntax

public class SubPASC2 : Subroutine

Constructors

SubPASC2(Particle)

Declaration

public SubPASC2(Particle p)

Parameters

Type	Name	Description
Particle	p

Fields

bit_Active

Declaration

private const int bit_Active = 13

Field Value

Type	Description
int

bit_Leader

Declaration

private const int bit_Leader = 12

Field Value

Type	Description
int

bit_PSet1

Declaration

private const int bit_PSet1 = 22

Field Value

Type	Description
int

bit_PSet2

Declaration

private const int bit_PSet2 = 27

Field Value

Type	Description
int

bit_Passive

Declaration

private const int bit_Passive = 14

Field Value

Type	Description
int

bit_Pin1

Declaration

private const int bit_Pin1 = 16

Field Value

Type	Description
int

bit_Pin2

Declaration

private const int bit_Pin2 = 19

Field Value

Type	Description
int

bit_ReceivedBit

Declaration

private const int bit_ReceivedBit = 15

Field Value

Type	Description
int

nbrBitWidth

Declaration

private const int nbrBitWidth = 2

Field Value

Type	Description
int

state

Declaration

private ParticleAttribute<int> state

Field Value

Type	Description
ParticleAttribute<int>

Properties

Active

Whether we are currently active.

Declaration

private bool Active { get; set; }

Property Value

Type	Description
bool

Leader

Whether we are the leader.

Declaration

private bool Leader { get; set; }

Property Value

Type	Description
bool

PSet1

The primary partition set ID.

Declaration

private int PSet1 { get; set; }

Property Value

Type	Description
int

PSet2

The secondary partition set ID.

Declaration

private int PSet2 { get; set; }

Property Value

Type	Description
int

Passive

Whether we became passive in the last iteration.

Declaration

private bool Passive { get; set; }

Property Value

Type	Description
bool

Pin1

The first pin offset.

Declaration

private int Pin1 { get; set; }

Property Value

Type	Description
int

Pin2

The second pin offset.

Declaration

private int Pin2 { get; set; }

Property Value

Type	Description
int

ReceivedBit

The bit received in the last iteration.

Declaration

private bool ReceivedBit { get; set; }

Property Value

Type	Description
bool

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 PASC structure to send the beep that deactivates half of the active participants. Must be called after the pin configuration has been set up.

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.

GetStateBool(int)

Helper for reading a single bit from the state int.

Declaration

private bool GetStateBool(int bit)

Parameters

Type	Name	Description
int	bit	The position of the bit.

Returns

Type	Description
bool	The value of the state bit at position bit.

GetStateInt3(int)

Helper for reading a 3-bit integer from the state int.

Declaration

private int GetStateInt3(int bit)

Parameters

Type	Name	Description
int	bit	Lowest bit of the integer to read.

Returns

Type	Description
int	The 3-bit integer stored at the given location.

GetStateInt5(int)

Helper for reading a 5-bit integer from the state int.

Declaration

private int GetStateInt5(int bit)

Parameters

Type	Name	Description
int	bit	Lowest bit of the integer to read.

Returns

Type	Description
int	The 5-bit integer stored at the given location.

GetStateNbrType(Direction)

Helper for reading neighbor types from the state int.

Declaration

private SubPASC2.NbrType GetStateNbrType(Direction dir)

Parameters

Type	Name	Description
Direction	dir	The direction of the neighbor.

Returns

Type	Description
SubPASC2.NbrType	The assigned type of the neighbor.

Init(List<Direction>, List<Direction>, int, int, int, int, bool, bool, Direction, bool, bool)

Initializes the PASC2 subroutine. Successors, predecessors and neighbors must not overlap (the last encountered one will be taken).

Declaration

public void Init(List<Direction> predecessors, List<Direction> successors, int pin1, int pin2, int pSet1, int pSet2, bool isLeader, bool isActive = true, Direction neighborDir = Direction.NONE, bool connectNbr1 = true, bool connectNbr2 = true)

Parameters

Type	Name	Description
List<Direction>	predecessors	The directions where predecessors should be connected.
List<Direction>	successors	The directions where successors should be connected.
int	pin1	The primary pin offset for outgoing connections. Must be at most 7.
int	pin2	The secondary pin offset for outgoing connections. Must be at most 7.
int	pSet1	The primary partition set ID. Must be at most 31.
int	pSet2	The secondary partition set ID. Must be at most 31.
bool	isLeader	Whether this amoebot is the leader. All leaders should be on the same stripe.
bool	isActive	Whether this amoebot is initially active.
Direction	neighborDir	The direction of the neighbor axis.
bool	connectNbr1	Whether the neighbor in direction neighborDir should be connected.
bool	connectNbr2	Whether the neighbor in the direction opposite opposite of neighborDir should be connected.

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. Afterwards, GetReceivedBit() will be 1 if and only if we received the cutoff beep.

Declaration

public void ReceiveCutoffBeep()

SendCutoffBeep()

Causes the active non-leader amoebots to send the cutoff beep that is received by all amoebots 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, List<Direction>) has been done.

Declaration

public void SendCutoffBeep()

SetStateBool(int, bool)

Helper for setting a single bit from the state int.

Declaration

private void SetStateBool(int bit, bool value)

Parameters

Type	Name	Description
int	bit	The position of the bit.
bool	value	The new value of the bit.

SetStateInt3(int, int)

Helper for writing a 3-bit integer to the state int.

Declaration

private void SetStateInt3(int bit, int value)

Parameters

Type	Name	Description
int	bit	Lowest bit position to write to.
int	value	The new 3-bit integer value.

SetStateInt5(int, int)

Helper for writing a 5-bit integer to the state int.

Declaration

private void SetStateInt5(int bit, int value)

Parameters

Type	Name	Description
int	bit	Lowest bit position to write to.
int	value	The new 5-bit integer value.

SetStateNbrType(Direction, NbrType)

Helper for setting neighbor types in the state int.

Declaration

private void SetStateNbrType(Direction dir, SubPASC2.NbrType type)

Parameters

Type	Name	Description
Direction	dir	The direction of the neighbor.
SubPASC2.NbrType	type	The new type of the neighbor.

SetupCutoffCircuit(PinConfiguration, List<Direction>)

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

Declaration

public void SetupCutoffCircuit(PinConfiguration pc, List<Direction> invertedDirections = null)

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.
List<Direction>	invertedDirections	Directions in which the pin offsets should be inverted. This can be used to adjust the "side" on which the beeps are sent if the specified default pins are used for something else in some directions.

SetupPC(PinConfiguration, List<Direction>)

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

Declaration

public void SetupPC(PinConfiguration pc, List<Direction> invertedDirections = null)

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.
List<Direction>	invertedDirections	Directions in which the pin offsets should be inverted. This can be used to adjust the "side" on which the beeps are sent if the specified default pins are used for something else in some directions.

SetupPinConfig(PinConfiguration, bool, List<Direction>)

Declaration

private void SetupPinConfig(PinConfiguration pc, bool cutoff = false, List<Direction> invertedDirections = null)

Parameters

Type	Name	Description
PinConfiguration	pc
bool	cutoff
List<Direction>	invertedDirections