Time and Space Optimality of Distributed Depth-First Token Circulation Algorithms.
Franck Petit, Vincent Villain · 1999
this paper, we first propose two optimal depth-first token circulation algorithms for tree structured networks using the state model [2]. One runs on trees having a (minimal) sense of direction. The other runs for trees without any sense of direction. Both algorithms are both space (or state) and time optimal. The first surprising result is that the optimal number of states per processor (for both algorithms) is about the half of what it was previously expected in [16]. The second surprising result is that the stabilization time of both algorithms is 0 steps, i.e., the This work has been supported in part by the Pole of Modelization of Picardie