Yo-yo (algorithm)
Yo-Yo is a distributed algorithm aimed at minimum finding and leader election in generic connected undirected graph. Unlike Mega-Merger it has a trivial termination and cost analysis. Introduction. Yo-yo was introduced by Nicola Santoro. 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: 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: Yo-. 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. Section::::-Yo. 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 formula_1 incoming edges: trivially formula_2 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 formula_3 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. 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 formula_4. The Yo-Yo phases consist of a forward  and backward scan of the structure, hence formula_5 messages, where formula_6 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 formula_7 nodes are connected in pairs and at each iteration at most half of the sources are eliminated. By restructuring each of  the surviving formula_8 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 formula_9 number of iterations over the latest computation, i.e. the one between the two farthest away surviving sources, placed at formula_10. The total cost amounts to formula_11. 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.