Portal de Periódicos da CAPES

Self-stabilizing wavelets and ϱ-hops coordination

2008; Institute of Electrical and Electronics Engineers; Volume: lncs 335; Linguagem: Inglês

10.1109/ipdps.2008.4536130

1530-2075

Christian Boulinier, Franck Petit,

Parallel Computing and Optimization Techniques

In this paper, we first introduce a simple tool called the wavelet or sigma-wavelet scheme. Wavelets deal with coordination among processes which are at most sigma hops away of each other. We propose a self-stabilizing solution for this scheme. Our solution requires no underlying structure and works in arbitrary anonymous settings, i.e., where process identifiers are not required. We show that our solution provides a simple and generic self-stabilizing sigma-infimum computation. Next, we present a self-stabilizing sigma-barrier synchronization protocol based on the wavelet scheme. We show that our protocol provides an efficient device in the design of local coordination problems at distance sigma, such as the sigma-local resource allocation (LRA). In particular, we propose a solution for the popular sigma-local mutual exclusion (LME) problem. The solution to sigma-LME also provides a transformer to transform algorithms written under sigma-central daemon into algorithms working with any distributed daemon.