Link reversal: How to play better to work less

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 [1] for routing, and subsequently employed in algorithms for, e.g., partition-tolerant routing [2], mutual exclusion [3], and leader election [4,5,6]. Gafni and Bertsekas [1] considered the problem of assigning virtual directions to network links to ensure that the network is loop-free and that every node in the network has a (directed) path to a destination node. They 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, of these two algorithms, which was proposed and analyzed in a previous paper [7]. 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 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.