deterministic distance-2 coloring

Self-Stabilizing Deterministic Time Division Multiple Access for Sensor Networks
In this paper, we present a self-stabilizing deterministic algorithm for TDMA in networks where a sensor is only aware of its neighbors. To our knowledge, this is the first such algorithm that achieves these properties. Moreover, this is the firrst algorithm that demonstrates the feasibility of stabilization-preserving deterministic transformation of a program in shared-memory model on an arbitrary topology into a program that is consistent with the sensor network model.
Mahesh Arumugam, Sandeep S. Kulkarni
PDF Cite