Link reversal algorithms /
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | eBook |
| Language: | English |
| Published: |
[San Rafael, Calif.] :
Morgan & Claypool,
[2012]
|
| Series: | Synthesis lectures on distributed computing theory ;
#8. |
| Subjects: | |
| Online Access: | Connect to the full text of this electronic book |
| Abstract: | 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. |
|---|---|
| Item Description: | Part of: Synthesis digital library of engineering and computer science. Electronic resource. |
| Physical Description: | 1 online resource (viii, 93 pages) : illustrations |
| Bibliography: | Includes bibliographical references (pages 89-92). |
| ISBN: | 9781608450428 (electronic bk.) 1608450422 (electronic bk.) 1608450414 9781608450411 |