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.

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. 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 u > 1 incoming edges: trivially 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 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. 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 \sum_{v \in V} deg(v) = 2m . The Yo-Yo phases consist of a forward and backward scan of the structure, hence 2m_i messages, where 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 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 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 log_2 n number of iterations over the latest computation, i.e. the one between the two farthest away surviving sources, placed at diam(G) . The total cost amounts to 2m \log{n} . ==References==

Text derived from https://en.wikipedia.org/w/index.php?oldid=1229718876 under CC BY-SA 4.0; modifications have been made.