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 |
Table of Contents:
- 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.