×

Self-stabilizing space optimal synchronization algorithms on trees. (English) Zbl 1222.68041

Flocchini, Paola (ed.) et al., Structural information and communication complexity. 13th international colloquium, SIROCCO 2006, Chester, UK, July 2–5, 2006. Proceedings. Berlin: Springer (ISBN 978-3-540-35474-1/pbk). Lecture Notes in Computer Science 4056, 334-348 (2006).
Summary: We present a space and (asymptotically) time optimal self-stabilizing algorithm for simultaneously activating non-adjacent processes in a rooted tree (Algorithm \(\mathcal{SSDST}\)). We then give two applications of the proposed algorithm: a time and space optimal solution to the local mutual exclusion problem (Algorithm \(\mathcal{LMET}\)) and a space and (asymptotically) time optimal distributed algorithm to place the values in min-heap order (Algorithm \({\mathcal{HEAP}}\)). All algorithms are self-stabilizing and uniform, and they work under any unfair distributed daemon. In proving the time complexity of the heap construction, we use the notion of pseudo-time. Pseudo-time is similar to logical time introduced by L. Lamport [“Time, clocks, and the ordering of events in a distributed system”, Commun. ACM 21, 558–565 (1978; Zbl 0378.68027)].
For the entire collection see [Zbl 1113.68004].

MSC:

68M14 Distributed systems
68P05 Data structures
68W15 Distributed algorithms

Citations:

Zbl 0378.68027
PDFBibTeX XMLCite
Full Text: DOI