Link reversal algorithms
By: Jennifer L. Welch, Jennifer E. Walter
Contributors: Walter, Jennifer E.
Series: Synthesis lectures on distributed computing theory -- # 8
Publisher: Morgan & Claypool
Published: 2012
Place of publication: San Rafael, Calif. (1537 Fourth Street, San Rafael, CA 94901 USA)
Language: eng
Format: [electronic resource] /
Number of pages: 93
ISBN-13: 9781608450428; 9781608450411
Subjects: Distributed algorithms; Distributed processing; Electronic data processing
Other titles: Synthesis digital library of engineering and computer science.
Description: Link 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.
Notes: Part of: Synthesis digital library of engineering and computer science.

Series from website.

Includes bibliographical references (p. 89-92).

Abstract freely available; full-text restricted to subscribers or individual document purchasers.

Also available in print.

Mode of access: World Wide Web.

System requirements: Adobe Acrobat Reader.

Title from PDF t.p. (viewed on November 19, 2011).
Table of contents: title: 1. Introduction; title: 2. Routing in a graph: correctness; title: 2.1 Abstract link reversal; title: 2.2 Vertex labels; title: 2.3 Link labels; title: 3. Routing in a graph: complexity; title: 3.1 Work complexity; title: 3.1.1 Vertex labeling; title: 3.1.2 Link labeling; title: 3.1.3 FR vs. PR with game theory; title: 3.2 Time complexity; title: 3.2.1 Full reversal; title: 3.2.2 General LR and partial reversal; title: 4. Routing and leader election in a distributed system; title: 4.1 Distributed system model for applications; title: 4.2 Routing in dynamic graphs; title: 4.2.1 Overview of TORA; title: 4.2.2 Route creation; title: 4.2.3 Route maintenance; title: 4.2.4 Erasing routes; title: 4.2.5 Discussion; title: 4.3 Leader election in dynamic graphs; title: 5. Mutual exclusion in a distributed system; title: 5.1 Mutual exclusion in fixed topologies; title: 5.1.1 LRME algorithm; title: 5.1.2 Correctness of LRME algorithm; title: 5.2 Mutual exclusion for dynamic topologies; title: 6. Distributed queueing; title: 6.1 The arrow protocol; title: 6.2 Correctness of arrow; title: 6.3 Discussion; title: 7. Scheduling in a graph; title: 7.1 Preliminaries; title: 7.2 Analysis for trees; title: 7.3 Analysis for non-trees; title: 7.4 Discussion; title: 8. Resource allocation in a distributed system; title: 8.1 Chandy and Misra's algorithm; title: 8.2 Correctness of Chandy and Misra's algorithm; title: 9. Conclusion; title: Bibliography; title: Authors' biographies.