Memory-Efficient and Self-Stabilizing Network RESET.
Baruch Awerbuch, Rafail Ostrovsky
Abstract: A fundamental issue in the design of distributed network protocols is efficiency (measured both in execution-speed and memory requirements) and fault-tolerance. In this paper, we consider the issue of fault-tolerance when processors have extremely small memory and do not have unique ID's. In particular, we consider arbitrary-topology distributed networks with two types of transient faults: arbitrary processor memory faults and dynamically crashing and recovering communication links. A primitive that makes networks fault-tolerant against these types of faults is so-called self-stabilizing network {\sc reset} protocol. We exhibit polynomial time self-stabilizing network {\sc reset\/} protocol which does not require unique processor ID's and works with small memory: $O(\log^*n)$ bits of memory per incident network edge. Our solution yields a self-stabilizing spanning-tree protocol with the same memory requirements. The result compares favorably to the best previously known self-stabilizing network {\sc reset} and spanning-tree protocols of [APV91,V92] which required unique ID's for each processor and additional $O(\log n)$-bits of memory per processor.
comment: Appeared In Proceedings of Thirteens Annual ACM Symposium on Principles of Distributed Computing (PODC-94)
Fetch PostScript file of the paper Fetch PDF file of the paper
| Back to Publications List |