Space and Time Efficient Self-Stabilizing ℓ-Exclusion in Tree Networks

✍ Scribed by R. Hadid

• Publisher: Elsevier Science
• Year: 2002
• Tongue: English
• Weight: 292 KB
• Volume: 62
• Category: Article
• ISSN: 0743-7315
• DOI: 10.1006/jpdc.2001.1834

✦ Synopsis

We propose an efficient self-stabilizing '-exclusion algorithm in rooted tree networks running under an unfair distributed daemon. The '-exclusion problem is a generalization of the mutual exclusion problem}' ð'51) processors, instead of 1, are permitted to use a shared resource. The algorithm is semi-uniform and its space requirement is ð' þ 3ÞD r states (or dlogðð' þ 3ÞD r Þe bits) for the root r, 4ðD p À 1Þ states (or d2 logðD p À 1Þe bits) for an internal processor p, and 3 states (or 2 bits) for a leaf processor, where D p is the degree of processor p. This is the first '-exclusion algorithm on trees with the property that the space requirement is independent of the size of the network for any processor, and is independent of ' for all processors except the root. The stabilization time of the algorithm is only Oð' þ hÞ rounds, where h is the height of the tree.