Many large scale systems, like grids and structured peer to peer systems, operate on a constrained topology. Since underlying networks do not expose the real topology to the applications, an algorithm should build and maintain a virtual topology for the application. This algorithm has to bootstrap the system and react to the arrival and departures of processes. In a previous article, we introduced a computing model designed for scalability in which we gave a self-stabilizing algorithm that builds a spanning tree. At that time, we provided a proof of stabilization and performance measurements of a prototypal implementation. In this work, we present a probabilistic method to evaluate the theoretical performances of algorithms in this model, and provide a probabilistic analysis of the convergence time of the algorithm.

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.

No abstract available.