Edición de la obra Link reversal algorithms
| Autor | Jennifer Welch |
|---|---|
| Editorial | Morgan & Claypool |
| Fecha de publicación | 2012 |
| Lugar | San Rafael, Calif. (1537 Fourth Street, San Rafael, CA 94901 USA) |
| Idioma | inglés |
| Páginas | 93 |
| Formato | [electronic resource] / |
| ISBN-13 | 9781608450428, 9781608450411 |
| OCLC | 761110154 |
| Serie | Synthesis lectures on distributed computing theory -- # 8 |
| Número de Cutter |
W439lLink reversal is a versatile algorithm design technique that has been used in numerous distributed algorithms for a variety of problems. The common thread in these algorithms is that the distributed system is viewed as a graph, with vertices representing the computing nodes and edges representing some other feature of the system (for instance, point-to-point communication channels or a conflict relationship). Each algorithm assigns a virtual direction to the edges of the graph, producing a directed version of the original graph. As the algorithm proceeds, the virtual directions of some of the links in the graph change in order to accomplish some algorithm-specific goal. The criterion for changing link directions is based on information that is local to a node (such as the node having no outgoing links) and thus this approach scales well, a feature that is desirable for distributed algorithms.