Snap-Stabilizing Waves in Anonymous Networks
We propose the first snap-stabilizing wave algorithm for anonymous networks. In the worst case, a process decides in O(n + D) time units, where n and D are the number of process and the diameter of the network, respectively. The proposed algorithm uses a
- PDF / 512,382 Bytes
- 12 Pages / 430 x 660 pts Page_size
- 84 Downloads / 176 Views
Abstract. We propose the first snap-stabilizing wave algorithm for anonymous networks. In the worst case, a process decides in O(n + D) time units, where n and D are the number of process and the diameter of the network, respectively. The proposed algorithm uses a self-stabilizing underlying unison protocol. If the underlying unison is stabilized when a process request a wave, then a decide event occurs in an optimal time, i.e., O(D) time units. The proposed solution is generic in the sense that, it can be used for any static or dynamic scheme which is feasible in an anonymous network. In particular, as an application of our scheme, we provide a snap-stabilizing causal atomic broadcast for anonymous networks, which can be used as a pipeline of messages.
1
Introduction
Wave algorithms (or, Total algorithms) [16] are widely used as the basis to solve many network control problems. A wave algorithm is a distributed algorithm where the participation of all processes in the network is required before a particular event, called a decision, is taken. Wave algorithms include well-know and basis schemes of distributed systems such as Spanning Tree Construction (STC), Token Circulation (TC), Propagation of Information with Feedback (PIF), etc. Wave algorithms are also related to message broadcasting [13]. They are often designed to be executed either only once or infinitely often. In the former case, they leads the whole system toward a fixed point and are said to be static. They mainly refer to STC algorithms. In the latter case (TC and PIF) are said to be dynamic. Solutions to these basic problems can then be used as the basis for the solution to a wide class of problems in distributed computing, mainly in order to improve the coordination of the processes. So, designing efficient fault-tolerant wave algorithms is an important task in the distributed computing research. The concept of self-stabilization [9] is a general technique to design a system to tolerate arbitrary transient faults. A self-stabilizing system, regardless of the initial states of the processors and initial messages in the links, is guaranteed to converge to the intended behavior in finite time. Snap-stabilization was first introduced in [4]. A snap-stabilizing protocol guarantees that the system always
This research is supported in part by R´egion Picardie (France), Project “APREDY”.
S. Rao et al. (Eds.): ICDCN 2008, LNCS 4904, pp. 191–202, 2008. c Springer-Verlag Berlin Heidelberg 2008
192
C. Boulinier, M. Levert, and F. Petit
maintains the desirable behavior. In other words, a snap-stabilizing algorithm is also a self-stabilizing algorithm that stabilizes in 0 steps. Obviously, any snapstabilizing protocol is optimal in terms of the worst-case stabilization time. Related Works. Many self-stabilizing wave algorithms for arbitrary networks have been proposed in the literature, e.g., [1,7,10,14,15]. Snap-Stabilizing wave algorithms for arbitrary networks are given in [5,6]. All the above solutions assume the existence of a particular process called
Data Loading...
