Dana Angluin, James Aspnes, Melody Chan, Michael J. Fischer, Hong Jiang, and René Peralta. Stably computable properties of network graphs. Distributed Computing in Sensor Systems: First IEEE International Conference, DCOSS 2005, Marina del Rey, CA, USE, June/July, 2005, Proceedings, Lecture Notes in Computer Science, volume 3560, Springer-Verlag, June 2005, pp. 63–74.
We consider a scenario in which anonymous, finite-state sensing devices are deployed in an ad-hoc communication network of arbitrary size and unknown topology, and explore what properties of the network graph can be stably computed by the devices. We show that they can detect whether the network has degree bounded by a constant d, and, if so, organize a computation that achieves asymptotically optimal linear memory use. We define a model of stabilizing inputs to such devices and show that a large class of predicates of the multiset of final input values are stably computable in any weakly-connected network. We also show that nondeterminism in the transition function does not increase the class of stably computable predicates.
@inproceedings(AngluinACFJP2005,
title="Stably computable properties of network graphs",
author="Dana Angluin and James Aspnes and Melody Chan and Michael J. Fischer and Hong Jiang and Ren\'e Peralta",
booktitle="Distributed Computing in Sensor Systems: First IEEE International Conference, DCOSS 2005, Marina del Rey, CA, USE, June/July, 2005, Proceedings",
editor="Viktor K. Prasanna and Sitharama Iyengar and Paul Spirakis and Matt Welsh",
series="Lecture Notes in Computer Science",
publisher="Springer-Verlag",
pages = {63--74},
volume="3560",
month=jun,
year=2005
)