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

Created from the Publication Database of the Vienna University of Technology.