Memory-efficient and self-stabilizing network RESET (extended abstract)
Baruch Awerbuch, Rafail Ostrovsky · 1994
) Baruch Awerbuch Rafail Ostrovsky y August 15, 1994 Abstract In this paper we consider the question of fault-tolerant distributed network protocols with extremely small memory requirements per processor. In particular, we show that even in the case of worst-case transient faults (i.e., in a self-stabilizing setting), many fundamental network protocols can be achieved using only O(log n) bits of memory per incident network edge. In the heart of our construction is a self-stabilizing asynchronous network reset protocol with the same small memory requirements. Johns Hopkins University, Baltimore, MD 21218, and MIT Lab. for Computer Science. E-mail: [email protected]. Supported by Air Force Contract TNDGAFOSR-86-0078, ARPA/Army contract DABT63-93-C-0038, ARO contract DAAL03-86-K-0171, NSF contract 9114440-CCR, DARPA contract N00014-J-92-1799. y U.C. Berkeley and ICSI. Supported by NSF postdoctoral fellowship and ICSI. E-mail: [email protected]. 1 1 Introduction...