Black Art: Obstruction-Free k-set Agreement with |MWMR registers| < |proccesses|

Abstract : When n processes communicate by writing to and reading from k < n MWMR registers the "communication bandwidth" precludes emulation of SWMR system, even non-blocking. Nevertheless, recently a positive result was shown that such a system either wait-free or obstruction-free can solve an interesting one-shot task. This paper demonstrates another such result. It shows that (n − 1)-set agreement can be solved obstruction-free with merely 2 MWMR registers. Achieving k-set agreement with n − k + 1 registers is a challenge. We make the first step toward it by showing k-set agreement with 2(n − k) registers.
Type de document :
Communication dans un congrès
Vincent Gramoli and Rachid Guerraoui. NETYS 2013 - First International Conference Networked Systems, May 2013, Marrakech, Morocco. Springer, 7853, pp.28-41, 2013, Lecture Notes in Computer Science. 〈10.1007/978-3-642-40148-0_3〉
Liste complète des métadonnées

https://hal.inria.fr/hal-00922423
Contributeur : Carole Delporte-Gallet <>
Soumis le : jeudi 26 décembre 2013 - 15:51:22
Dernière modification le : jeudi 11 janvier 2018 - 06:21:34

Identifiants

Collections

Citation

Carole Delporte-Gallet, Hugues Fauconnier, Eli Gafni, Sergio Rajsbaum. Black Art: Obstruction-Free k-set Agreement with |MWMR registers| < |proccesses|. Vincent Gramoli and Rachid Guerraoui. NETYS 2013 - First International Conference Networked Systems, May 2013, Marrakech, Morocco. Springer, 7853, pp.28-41, 2013, Lecture Notes in Computer Science. 〈10.1007/978-3-642-40148-0_3〉. 〈hal-00922423〉

Partager

Métriques

Consultations de la notice

163