Article ID Journal Published Year Pages File Type
450292 Computer Communications 2008 7 Pages PDF
Abstract

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.

Related Topics
Physical Sciences and Engineering Computer Science Computer Networks and Communications
Authors
, ,