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.

[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".

Yo-Yo builds elects a minimum leader under the following premises: No further restrictions are necessary.

Note as this is just a logical step, the bi-directional channel is not lost in the procedure.

This process creates three categories of nodes: 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.

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

Sinks initiate the "-Yo" phase by computing the minimum id received and sending a positive YES or negative NO through their incoming edges.

The edges carrying a NO are reversed and the losers candidates of the current stage become either sinks or intermediate nodes.

Pruning is an optimization technique applied in the "-Yo" phase, and its message is usually incorporated with the positive/negative response.

The Yo-Yo phases consist of a forward and backward scan of the structure, hence

nodes are connected in pairs and at each iteration at most half of the sources are eliminated.

number of iterations over the latest computation, i.e. the one between the two farthest away surviving sources, placed at

Termination is guaranteed by the switch in directions performed in the YES/NO pull.