Distributed computing has to adapt its techniques to mobile sensor networks and cope with constraints like small memory size or lack of computation power. In this paper we extend the results of Angluin et al (see [1,2,3,4]) by finding self-stabilizing algorithms to count the number of agents in the network. We focus on two different models of communication, with a fixed antenna or with pairwise interactions. In both models we decide if there exist algorithms (probabilistic, deterministic, with k-fair adversary) to solve the self-stabilizing counting problem.

In [2], J. Beauquier, M. Gradinariu and C. Johnen presented a probabilistic self-stabilizing token circulation algorithm for asynchronous uniform unidirectional rings. This paper provides an improvement on this algorithm. It also computes the (message) complexity of the stabilization period of the original algorithm, which is T(N3), and the improved version, which is T(N2 log N), where N is the number of processes plus the number of messages in transit. Such algorithms are mostly used for mutual exclusion.