With Finite Memory Consensus Is Easier Than Reliable Broadcast
作者： Carole Delporte-Gallet , Stéphane Devismes , Hugues Fauconnier , Franck Petit , Sam Toueg
DOI: 10.1007/978-3-540-92221-6_5
关键词: Process memory 、 Failure detector 、 Asynchronous distributed systems 、 Process (computing) 、 Theoretical computer science 、 Consensus 、 Computer science 、 Terminating Reliable Broadcast
摘要: We consider asynchronous distributed systems with message losses and process crashes. study the impact of finite memory on solution to consensus , repeated reliable broadcast . With memory, we show that in some sense is easier solve than broadcast, as difficult consensus: More precisely, can be solved failure detector $\cal S$, ${\cal P}^-$ (a variant perfect which stronger S$) necessary sufficient consensus.
springer.com
core.ac.uk
sci-hub.st 参考文章(31)
Rachid Guerraoui, Michał Kapałka, Petr Kouznetsov, The weakest failure detectors to boost obstruction-freedom Distributed Computing. ,vol. 20, pp. 415- 433 ,(2008) , 10.1007/S00446-007-0046-9
Nancy A. Lynch, Yishay Mansour, Alan Fekete, Data link layer: two impossibility results principles of distributed computing. pp. 149- 170 ,(1988) , 10.1145/62546.62572
B. Chor, B.A. Coan, A Simple and Efficient Randomized Byzantine Agreement Algorithm IEEE Transactions on Software Engineering. ,vol. SE-11, pp. 531- 539 ,(1985) , 10.1109/TSE.1985.232245
Carole Delporte-Gallet, Hugues Fauconnier, Rachid Guerraoui, Petr Kouznetsov, Mutual exclusion in asynchronous systems with failure detectors Journal of Parallel and Distributed Computing. ,vol. 65, pp. 492- 505 ,(2005) , 10.1016/J.JPDC.2004.11.008
Tushar Deepak Chandra, Vassos Hadzilacos, Sam Toueg, None, The weakest failure detector for solving consensus Journal of the ACM. ,vol. 43, pp. 685- 722 ,(1996) , 10.1145/234533.234549
Jonathan Eisler, Vassos Hadzilacos, Sam Toueg, The weakest failure detector to solve nonuniform consensus Distributed Computing. ,vol. 19, pp. 335- 359 ,(2007) , 10.1007/S00446-006-0019-4
Joseph Y. Halpern, Aleta Ricciardi, A knowledge-theoretic analysis of uniform distributed coordination and failure detectors Distributed Computing. ,vol. 17, pp. 223- 236 ,(2005) , 10.1007/S00446-004-0109-0
N.V. Stenning, A data transfer protocol Computer Networks. ,vol. 1, pp. 99- 110 ,(1976) , 10.1016/0376-5075(76)90015-5
A. Fernandez, E. Jimenez, M. Raynal, Eventual Leader Election with Weak Assumptions on Initial Knowledge, Communication Reliability, and Synchrony dependable systems and networks. ,vol. 25, pp. 166- 178 ,(2006) , 10.1109/DSN.2006.34
Tushar Deepak Chandra, Sam Toueg, None, Unreliable failure detectors for reliable distributed systems Journal of the ACM. ,vol. 43, pp. 225- 267 ,(1996) , 10.1145/226643.226647