Tolerating transient and permanent failures (extended abstract)

Autor:	Efthymios Anagnostou, Vassos Hadzilacos
Rok vydání:	1993
Předmět:	Ring (mathematics) Leader election Asynchronous communication Computer science Distributed algorithm Distributed computing Fault tolerance Self-stabilization Upper and lower bounds Asynchrony (computer programming)
Zdroj:	Distributed Algorithms ISBN: 9783540572718 WDAG
DOI:	10.1007/3-540-57271-6_35
Popis:	We investigate the possibility of designing protocols that are both self-stabilizing and fault-tolerant, in the asynchronous model of distributed systems. We prove that no such protocols exist for a wide range of problems, including determining (even approximately) the size of the distributed system and leader election. All of these problems are solvable in asynchronous systems using (randomized) protocols that are only fault-tolerant (but not self-stabilizing); or only self-stabilizing (but not fault-tolerant). We then focus on the problem of computing distinct names for the processors in a ring. We give three (randomized) protocols that solve this problem in three settings satisfying increasingly weak assumptions: When processors know the exact size n of the ring; when they only know an upper bound on n; and when they have no information about n.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::07f447c8436510e731efa640ce8451ad https://doi.org/10.1007/3-540-57271-6_35 Zobrazit plný text záznamu