Namespace AS2.Subroutines.ETT

Classes

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

Enums

Comparison

Set of possible comparison results.