[Back]

B. Charron-Bost, L. Welch, J. Widder:
"Link Reversal: How to Play Better to Work Less";
Talk: ALGOSENSORS 2009 (5th International Workshop on Algorithmic Aspects of Wireless Sensor Networks), Rhodes, Greece; 2009-07-10 - 2009-07-11; in: "Algorithmic Aspects of Wireless Sensor Networks", Springer, 5304/2008 (2009), ISBN: 9783642054334; 88 - 110.

Sensor networks, with their ad hoc deployments, node mobility, and wireless communication, pose
serious challenges for developing provably correct and efficient applications. A popular algorithm design
technique for such systems is link reversal, first proposed by Gafni and Bertsekas [GB81] for routing, and
subsequently employed in algorithms for partition-tolerant routing [PC97], mutual exclusion [WWV01],
leader election [MWV00, ISWW09, DB08], etc. Understanding the basic foundations of the complexity
of link reversal and how it can be improved will have a positive impact on such ad hoc sensor network
algorithms.
Gafni and Bertsekas [GB81] proposed two algorithms, full reversal (FR) and partial reversal (PR),
together with an implementation of each based on associating an unbounded value with each node in
the graph. In this paper, we consider a generalization, called LR, of these two algorithms, which was
proposed and analyzed in a previous paper [CGWW09]. The key to the generalization is to associate
a binary label with each link of the graph instead of an unbounded label with each node. In the LR
formalism, initial labelings form a continuum with FR and PR at opposite ends. We previously showed
that the number of steps a node takes until convergence-that is, the cost associated to a node-
depends only on the initial labeling of the graph. In this paper, we compare the work complexity of
labelings in which all incoming links of a given node i are labeled with the same binary value μi. Finding
initial labelings that induce good work complexity can be considered as a game in which to each node i
a player is associated who has strategy μi. In this game one tries to minimize the cost, i.e., the work
complexity. Expressing the initial labelings in a natural way as a game allows us to compare the work
complexity of FR and PR in a way that, for the first time, provides a rigorous basis for the intuition
that PR is better than FR.

http://dx.doi.org/10.1007/978-3-642-05434-1_10