Namespace AS2.Subroutines.PASC
Classes
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).
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>).