Record:   Prev Next
作者 Welch, Jennifer
書名 Link reversal algorithms [electronic resource] / Jennifer L. Welch, Jennifer E. Walter
出版項 San Rafael, Calif. (1537 Fourth Street, San Rafael, CA 94901 USA) : Morgan & Claypool, c2012
國際標準書號 9781608450428 (electronic bk.)
9781608450411 (pbk.)
國際標準號碼 10.2200/S00389ED1V01Y201111DCT008 doi
book jacket
說明 1 electronic text (viii, 93 p.) : ill., digital file
系列 Synthesis lectures on distributed computing theory, 2155-1634 ; # 8
Synthesis digital library of engineering and computer science
Synthesis lectures on distributed computing theory, 2155-1634 ; # 8
附註 Part of: Synthesis digital library of engineering and computer science
Series from website
Includes bibliographical references (p. 89-92)
1. Introduction --
2. Routing in a graph: correctness -- 2.1 Abstract link reversal -- 2.2 Vertex labels -- 2.3 Link labels --
3. Routing in a graph: complexity -- 3.1 Work complexity -- 3.1.1 Vertex labeling -- 3.1.2 Link labeling -- 3.1.3 FR vs. PR with game theory -- 3.2 Time complexity -- 3.2.1 Full reversal -- 3.2.2 General LR and partial reversal --
4. Routing and leader election in a distributed system -- 4.1 Distributed system model for applications -- 4.2 Routing in dynamic graphs -- 4.2.1 Overview of TORA -- 4.2.2 Route creation -- 4.2.3 Route maintenance -- 4.2.4 Erasing routes -- 4.2.5 Discussion -- 4.3 Leader election in dynamic graphs --
5. Mutual exclusion in a distributed system -- 5.1 Mutual exclusion in fixed topologies -- 5.1.1 LRME algorithm -- 5.1.2 Correctness of LRME algorithm -- 5.2 Mutual exclusion for dynamic topologies --
6. Distributed queueing -- 6.1 The arrow protocol -- 6.2 Correctness of arrow -- 6.3 Discussion --
7. Scheduling in a graph -- 7.1 Preliminaries -- 7.2 Analysis for trees -- 7.3 Analysis for non-trees -- 7.4 Discussion --
8. Resource allocation in a distributed system -- 8.1 Chandy and Misra's algorithm -- 8.2 Correctness of Chandy and Misra's algorithm --
9. Conclusion -- Bibliography -- Authors' biographies
Abstract freely available; full-text restricted to subscribers or individual document purchasers
Google scholar
Google book search
Mode of access: World Wide Web
System requirements: Adobe Acrobat Reader
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
Also available in print
Title from PDF t.p. (viewed on November 19, 2011)
鏈接 Print version: 9781608450411
主題 Distributed algorithms
Electronic data processing -- Distributed processing
link reversal
distributed algorithms
leader election
mutual exclusion
distributed queueing
resource allocation
Alt Author Walter, Jennifer E
Record:   Prev Next