Class SubETT

Implements the Euler Tour Technique (ETT). See https://doi.org/10.1145/3662158.3662776.
Given a tree in the amoebot structure, we replace every edge with two directed edges in opposing directions. The resulting directed graph has an Euler cycle that traverses each original edge exactly twice. For example, from each amoebot, we can visit its neighbors in counter-clockwise order to create such a cycle. By splitting this cycle at one position, we obtain an Euler tour that starts and ends at the split position. The Euler Tour Technique allows the computation of various tree functions, which we can realize with circuits. In particular, we establish a PASC circuit along the Euler tour and treat each visit of an amoebot as one participant. Each amoebot can mark one of its edges/participants as active.

The subroutine is setup as follows:

• There is a list of neighbor directions with 1-6 elements. Each element identifies an outgoing and an incoming edge. The order of the directions is counter-clockwise, i.e., the incoming edge of direction i is connected to the same PASC instance as the outgoing edge of direction (i + 1) mod m, where m is the number of neighbor directions.
• One outgoing edge can be marked, making its PASC instance initially active. The edge's direction is identified by its index in the neighbor list.
• The instance connecting the outgoing edge of the first neighbor and the incoming edge of the last neighbor can be split to turn the Euler cycle into an Euler tour. This should usually be done for one amoebot on the cycle.
• Each pair of incoming and outgoing edges has a primary and a secondary partition set. If d is the direction of the outoing edge, then the primary partition set has ID 2*d and the secondary partition set has ID 2*d + 1. This means the IDs 0,...,11 are reserved for the PASC partition sets of outgoing edges. In the special case that the first outgoing and the last incoming edge are split, the IDs 12 and 13 are used for the last incoming edge's partition sets.
• The PASC execution uses one round to send the main beep and a second round to send a termination beep. The second beep is sent on both circuits by all instances that became passive due to the first beep. Once no beep is received in the termination round, the procedure is finished.

This is how the subroutine should be used:

• Call Init(Direction[], int, bool) to setup the subroutine object for the given directions.
• Call SetupPinConfig(PinConfiguration) to construct all required partition sets for the next beep. The constructed partition sets should not be changed, otherwise ActivateSend() might not work correctly.
• Call ActivateSend() after setting up the pin configuration to send the next beep. In a termination round, this should be called by every participant. Otherwise, it should only be called by the splitting amoebots that should beep (usually the root). You can check the type of the current round using IsTerminationRound().
• In the activation immediately after ActivateSend() has been called, ActivateReceive() must be called. This will make the new bits and comparison results available or terminate the procedure.
• The procedure is finished as soon as IsFinished() returns true. This method can be called immediately after ActivateReceive().
• The received bits and comparison results can be obtained from the various inspection methods, e.g., GetComparisonResult(Direction), GetDiffBit(Direction, bool).

Inheritance

object

Subroutine

SubETT

Namespace: AS2.Subroutines.ETT

Assembly: .dll

Syntax

public class SubETT : Subroutine

Constructors

SubETT(Particle)

Declaration

public SubETT(Particle p)

Parameters

Type	Name	Description
Particle	p

Fields

active

Declaration

private ParticleAttribute<bool> active

Field Value

Type	Description
ParticleAttribute<bool>

becamePassive

Declaration

private ParticleAttribute<bool> becamePassive

Field Value

Type	Description
ParticleAttribute<bool>

bits

Declaration

private ParticleAttribute<string> bits

Field Value

Type	Description
ParticleAttribute<string>

comparisons

Declaration

private ParticleAttribute<Comparison>[] comparisons

Field Value

Type	Description
ParticleAttribute<Comparison>[]

finished

Declaration

private ParticleAttribute<bool> finished

Field Value

Type	Description
ParticleAttribute<bool>

markedEdge

Declaration

private ParticleAttribute<int> markedEdge

Field Value

Type	Description
ParticleAttribute<int>

neighbors

Declaration

private ParticleAttribute<Direction>[] neighbors

Field Value

Type	Description
ParticleAttribute<Direction>[]

numNeighbors

Declaration

private ParticleAttribute<int> numNeighbors

Field Value

Type	Description
ParticleAttribute<int>

split

Declaration

private ParticleAttribute<bool> split

Field Value

Type	Description
ParticleAttribute<bool>

terminationRound

Declaration

private ParticleAttribute<bool> terminationRound

Field Value

Type	Description
ParticleAttribute<bool>

Methods

ActivateReceive()

Receives the beeps from the last ActivateSend() call and updates the comparison results as well as the type of round. After this call, the next bits and comparison results are available.

Declaration

public void ActivateReceive()

ActivateSend()

Sends either a PASC or a termination beep, depending on what kind of round this is. If called in a termination round, all participants that became passive in the last iteration will send a beep to prevent termination. In a PASC round, all participants that split the Euler tour send a beep on their primary partition set. Special case: If the first outgoing edge of a splitting participant is marked, it will send a beep on its secondary partition set to count this edge.

Declaration

public void ActivateSend()

GetComparisonResult(Direction)

Returns the difference comparison result belonging to the given direction's edge. Note that this result is always up to date with the latest received bits.

Declaration

public Comparison GetComparisonResult(Direction d)

Parameters

Type	Name	Description
Direction	d	The direction of the edge.

Returns

Type	Description
Comparison	The result of comparing OUT - IN to 0 on the edge in direction d. Note that to get the result of IN - OUT, the comparison result just has to be flipped.

GetDiffBit(Direction, bool)

Returns the last received bit of the given edge's difference.

Declaration

public int GetDiffBit(Direction d, bool outgoing = true)

Parameters

Type	Name	Description
Direction	d	The direction of the edge.
bool	outgoing	If true, return the bit of the OUT - IN difference, otherwise return the bit of the IN - OUT difference (which might not be valid if the number turns out to be negative).

Returns

Type	Description
int

GetNeighborDirections()

Returns the neighbor directions with which the procedure was initialized. This is a convenience method so that the directions don't have to be stored in separate attributes again.

Declaration

public Direction[] GetNeighborDirections()

Returns

Type	Description
Direction[]	An array containing exactly the directions given to Init(Direction[], int, bool).

GetSumBit()

Returns the last received bit of the incoming edge belonging to the last neighbor direction in case this participant splits the cycle. This is exactly the number of marked edges on the Euler tour and is usually used to determine |Q|, in the notation of the paper.

Declaration

public int GetSumBit()

Returns

Type	Description
int	The last bit of the PASC result computing the number of marked edges on the Euler tour. If this participant does not split the tour, this will always return -1.

GetSumComparisonResult()

Returns the result of comparing the sum of all marked edges to 0. This result is always up to date with the latest received bits.

Declaration

public Comparison GetSumComparisonResult()

Returns

Type	Description
Comparison	The result of comparing the PASC sum to 0. Will never be LESS.

Init(Direction[], int, bool)

Initializes the subroutine for the given directions.

Declaration

public void Init(Direction[] nbrDirections, int markedEdge = -1, bool split = false)

Parameters

Type	Name	Description
Direction[]	nbrDirections	The directions of all neighboring edges, in counter-clockwise order. Each edge will be split into an outgoing and an incoming edge.
int	markedEdge	The index of the marked edge in the array of edges. If this is -1, no edge will be marked.
bool	split	If true, do not connect the outgoing edge of the first neighbor to the incoming edge of the last neighbor. This splits the Euler cycle into an Euler tour if done by exactly one participant.

IsFinished()

Checks whether the ETT procedure has finished.

Declaration

public bool IsFinished()

Returns

Type	Description
bool	true if and only if no termination beep was received in the last termination round.

IsTerminationRound()

Checks whether this round is a termination round. If true, the next beep will be sent by all participants that became passive to continue the procedure with another iteration.

Declaration

public bool IsTerminationRound()

Returns

Type	Description
bool	true if and only this round is a termination round.

SetupPinConfig(PinConfiguration)

Sets up the required partition sets for the next beep in the given pin configuration.

Declaration

public void SetupPinConfig(PinConfiguration pc)

Parameters

Type	Name	Description
PinConfiguration	pc	The pin configuration to be modified. It has to be set as the next configuration before ActivateSend() is called.