Yo-yo (algorithm)

Yo-Yo is a distributed algorithm aimed at minimum finding and leader election in generic connected undirected graph.[1][2] Unlike Mega-Merger it has a trivial termination and cost analysis.

Introduction

Yo-yo was introduced by Nicola Santoro.[3] It proceeds by consecutive elimination and a graph-reduction technique called pruning. The algorithm is divided in a pre-processing phase followed by a cyclic repetition of a forward phase, called "Yo-" and a backward one, called "-Yo".

Pre-requisites

Yo-Yo builds elects a minimum leader under the following premises:

• Total reliability: No message is lost in transmission.
• Initial Distinct Values (ID): Each node has a unique identifier.
• Bi-directional communications channels: Each edge is bi-directional, communications can travel in both directions.

No further restrictions are necessary.

Algorithm

Preprocessing

The preprocessing phase is started with a broadcast. At awake state, each node sends its id to all of its neighbors and orients the edge towards the higher-degree node. Note as this is just a logical step, the bi-directional channel is not lost in the procedure. By convergecast the initiator is notified of the preprocessing termination. This process creates three categories of nodes:

• Sources: nodes with outgoing nodes, but no incoming nodes. These are the least nodes in each neighborhood.
• Intermediate nodes: nodes with both outgoing and incoming edges. These are neither the least nor the greatest nodes in each neighborhood.
• Sinks: nodes with incoming edges, but no outgoing edges. These are the greatest nodes in each neighborhood.

Yo-

Yo- phase, the sources' values are pushed down towards the sink(s).

The "Yo-" phase is initiated by the sources. A source sends its id through its incoming edges, and waits. The intermediate nodes wait to receive the respective ids from each of their incoming edges. Once all of expected values are collected, a minimum computation is performed and the minimum id is forwarded through the outgoing edges. Sinks are passive in this phase.

The messages are sent through the oriented edges and reach the sinks, which trigger the "-Yo" phase.

-Yo

The -Yo phase pulls up positive/negative answers.

Sinks initiate the "-Yo" phase by computing the minimum id received and sending a positive YES or negative NO through their incoming edges. A YES is sent through the edges carrying the minimum computed id, a NO through the remaining edges. The messages walk up the structure to the sources: the sources with at least one incoming NO become dead and lose their candidate status.

The "-Yo" phase also comprises a re-structuring phase where the sources-intermediates-sinks is accommodated for the non-candidate sources. The edges carrying a NO are reversed and the losers candidates of the current stage become either sinks or intermediate nodes.

Pruning

Pruning is an optimization technique applied in the "-Yo" phase, and its message is usually incorporated with the positive/negative response. It deletes useless edges and nodes. The former are edges that receive the same value from ${\displaystyle u>1}$ incoming edges: trivially ${\displaystyle u}$ are useless and trimmed by the node. Such edges become dead and are ignored in the following iterations. The latter instead reduces the number of nodes by deleting unary sinks, that is sinks with ${\displaystyle v=1}$ incoming edge. These edges will be forced to send back the (only) received minimum with a YES reply, hence they do not perform any computation useful to the minimum finding.

Structure before and after pruning. First the top right-most node becomes a sink from receiving a NO. Being a sink with only one incoming edge, it is trimmed. Same goes for its parent and the central branch.

Cost

The pre-processing phase is composed of an exchange through each edge of the two nodes incident on the edge. Thus we have a cost of ${\displaystyle \sum _{v\in V}deg(v)=2m}$. The Yo-Yo phases consist of a forward and backward scan of the structure, hence ${\displaystyle 2m_{i}}$ messages, where ${\displaystyle m_{i}}$ is the number of current active edges. The number of iterations is given by the number of iterations useful in order to delete each initial source. By hypothesis, each source is linked to at least another one by an intermediate node: if this was not the case then a disconnected component of the graph, but by definition the graph is connected. In the worst-case scenario intermediate ${\displaystyle n_{i}}$ nodes are connected in pairs and at each iteration at most half of the sources are eliminated. By restructuring each of the surviving ${\displaystyle n_{i+1}}$ sources will now be connected in pairs. As in the previous case, at most half will survive. Clearly the termination is met when only one source remains. The halving imposes a ${\displaystyle log_{2}n}$ number of iterations over the latest computation, i.e. the one between the two farthest away surviving sources, placed at ${\displaystyle diam(G)}$. The total cost amounts to ${\displaystyle 2m\log {n}}$.

Termination

Termination is guaranteed by the switch in directions performed in the YES/NO pull. The sources reduction in the "-Yo" phase is monotonic: by the previous observation each source is compared to at least one other source, and by uniqueness of the sources, one of them prevails while the others become dead. Since the number of initial sources is finite, the monotonic reduction will lead to a single source remaining.

References

1. Gallager, Robert (1983). "A distributed algorithm for minimum spanning tree" (PDF). Massachusetts Institute of Technology.
2. Awerbuch, Baruch (1987). "Optimal Distributed Algorithm for Minimum Weight Spanning Tree, Counting, Leader Election and Other Problems" (PDF). SIAM Journal on Computing.
3. Santoro, Nicola. "Design and Analysis of Distributed Algorithms". people.scs.carleton.ca. p. 213. Retrieved 2017-03-13.