Actions for Link reversal algorithms [electronic resource]

Email RIS file
Bookmark
Report an Issue

Link reversal algorithms [electronic resource] / Jennifer L. Welch, Jennifer E. Walter

Author
Welch, Jennifer
Published
San Rafael, Calif. (1537 Fourth Street, San Rafael, CA 94901 USA) : Morgan & Claypool, [2012]
Copyright Date
©2012
Physical Description
1 electronic text (viii, 93 pages) : illustrations, digital file
Additional Creators
Walter, Jennifer E.
Access Online

Availability

I Want It
I Want It

Finding items...

Series
Restrictions on Access
Abstract freely available; full-text restricted to subscribers or individual document purchasers.
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 --, and 9. Conclusion -- Bibliography -- Authors' biographies.
Summary
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.
Subject(s)
Other Subject(s)
ISBN
9781608450428 (electronic bk.)
9781608450411 (pbk.)
Note
Part of: Synthesis digital library of engineering and computer science.
Series from website.
AVAILABLE ONLINE TO AUTHORIZED PSU USERS.
Bibliography Note
Includes bibliographical references (pages 89-92).
Other Forms
Also available in print.
Technical Details
Mode of access: World Wide Web.
System requirements: Adobe Acrobat Reader.
Indexed By
Compendex
INSPEC
Google scholar
Google book search
View MARC record | catkey: 12563877