Paper Info
Title
Full reversal routing as a linear dynamical system
Abstract
Link reversal is a versatile algorithm design paradigm, originally proposed by Gafni and Bertsekas in 1981 for routing, and subsequently applied to other problems includingmutual exclusion and resource allocation. Although these algorithms arewell-known, until nowthere have been only preliminary results on time complexity, even for the simplest link reversal scheme for routing, called FullReversal (FR). In this paper we tackle this open question for arbitrary communication graphs. Our central technical insight is to describe the behavior of FR as a dynamical system, and to observe that this systemis linear in the min-plus algebra. Fromthis characterization, we derive the first exact formula for the time complexity: Given any node in any (acyclic) graph, we present an exact formula for the time complexity of that node, in terms of some simple properties of the graph. These results for FR are instrumental in analyzing a broader class of link reversal routing algorithms, as we show in a companion paper that such algorithms can be reduced to FR. In the current paper, we further demonstrate the utility of our formulas by using them to show the previously unknown fact that FR is time-efficient when executed on trees.
Year
DOI
Venue
2011
10.1007/978-3-642-22212-2_10
SIROCCO
Keywords
Field
DocType
simplest link reversal scheme,companion paper,algorithms arewell-known,current paper,fromthis characterization,arbitrary communication graph,broader class,link reversal,linear dynamical system,time complexity,full reversal routing,exact formula
Exact formula,Linear dynamical system,Graph,Algorithm design,Computer science,Algorithm,Resource allocation,Time complexity,Mutual exclusion,Dynamical system
Conference
Volume
ISSN
Citations 
6796
0302-9743
7
PageRank 
References 
Authors
0.59
21
4
Name
Order
Citations
PageRank
Bernadette Charron-bost178567.22
Matthias Függer216721.14
Jennifer L. Welch31806257.97
Josef Widder422923.99