An optimal snap-stabilizing wave algorithm in arbitrary graphs

A wave is a distributed computation, often made up of a broadcast phase followed by a feedback phase, requiring the participation of all the processes in a network before a particular event called decision is taken. Solutions to a large number of fundamental problems in distributed computing requires waves. In this paper, we propose a time optimal snap-stabilizing wave algorithm implementing Propagation of Information with Feedback (PIF) for arbitrary synchronous networks with O(d) rounds of delay and O(log d) bits per process, where d is the diameter of the communication network. A system is said to be snap-stabilizing if it always behaves according to its specification [A. Bui, A. Datta, F. Petit, V. Villain, State-optimal snap-stabilizing PIF in tree networks, in: Proceedings of the Third Workshop on Self-stabilizing Systems (published in association with ICDCS99 The 19th IEEE International Conference on Distributed Computing Systems), IEEE Computer Society, Washington, DC, USA, vol. 5, 1999, pp. 78–85]. One of the main advantages of the proposed algorithm being snap-stabilizing is that the arbitrary initial configuration has limited or no effect on the pace of the broadcast propagation.