The weakest failure detector for solving k-set agreement
作者： Eli Gafni , Petr Kuznetsov
关键词: Computer science 、 Asynchronous communication 、 Impossibility 、 Shared memory 、 Algorithm 、 Theoretical computer science 、 Oracle 、 Extension (predicate logic) 、 K-set 、 Failure detector
摘要: A failure detector is a distributed oracle that provides processes in system with hints about failures. The notion of weakest captures the exact amount synchrony needed for solving given computing problem.In this paper, we determine k-set agreement among n (n > k) using reads and writes shared memory, regardless assumptions on when where failures might occur. This derived directly from impossibility wait-free k + 1-process agreement. Our approach can be viewed as an extension asynchronous BG-simulation technique to partially synchronous systems.
acm.org
tu-berlin.de 参考文章(22)
Michel Raynal, Corentin Travers, In search of the holy grail: looking for the weakest failure detector for wait-free set agreement international conference on principles of distributed systems. pp. 3- 19 ,(2006) , 10.1007/11945529_2
Petr Kuznetsov, Simple CHT: A New Derivation of the Weakest Failure Detector for Consensus. arXiv: Distributed, Parallel, and Cluster Computing. ,(2013)
Francis Chu, Reducing &Ω to ◊ W Information Processing Letters. ,vol. 67, pp. 289- 293 ,(1998) , 10.1016/S0020-0190(98)00122-7
Maurice Herlihy, Nir Shavit, The asynchronous computability theorem for t-resilient tasks Proceedings of the twenty-fifth annual ACM symposium on Theory of computing - STOC '93. pp. 111- 120 ,(1993) , 10.1145/167088.167125
Michael Saks, Fotios Zaharoglou, Wait-Free k -Set Agreement is Impossible: The Topology of Public Knowledge SIAM Journal on Computing. ,vol. 29, pp. 1449- 1483 ,(2000) , 10.1137/S0097539796307698
Piotr Zielinski, Anti-Ω: the weakest failure detector for set agreement principles of distributed computing. pp. 55- 64 ,(2008) , 10.1145/1400751.1400761
Carole Delporte-Gallet, Hugues Fauconnier, Rachid Guerraoui, Andreas Tielmann, The disagreement power of an adversary: extended abstract principles of distributed computing. pp. 288- 289 ,(2009) , 10.1145/1582716.1582769
Prasad Jayanti, Sam Toueg, Every problem has a weakest failure detector principles of distributed computing. pp. 75- 84 ,(2008) , 10.1145/1400751.1400763
Elizabeth Borowsky, Eli Gafni, Generalized FLP impossibility result for t-resilient asynchronous computations Proceedings of the twenty-fifth annual ACM symposium on Theory of computing - STOC '93. pp. 91- 100 ,(1993) , 10.1145/167088.167119
Michael J. Fischer, Nancy A. Lynch, Michael S. Paterson, Impossibility of distributed consensus with one faulty process Journal of the ACM. ,vol. 32, pp. 374- 382 ,(1985) , 10.1145/3149.214121