On the Space Complexity of Set Agreement?

Abstract : The k-set agreement problem is a generalization of the classical consensus problem in which processes are permitted to output up to k different input values. In a system of n processes, an m-obstruction-free solution to the problem requires termination only in executions where the number of processes taking steps is eventually bounded by m. This family of progress conditions generalizes wait-freedom (m = n) and obstruction-freedom (m = 1). In this paper, we prove upper and lower bounds on the number of registers required to solve m-obstruction-free k-set agreement, considering both one-shot and repeated formulations. In particular, we show that repeated k set agreement can be solved using n + 2 m--k registers and establish a nearly matching lower bound of n + 2 m--k.
Type de document :
Communication dans un congrès
ACM Symposium on Principles of Distributed Computing, PODC 2015, Jul 2015, Donostia, France. Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing, PODC 2015, Donostia-San Sebastián, Spain, July 21 - 23, 2015. ACM 2015, ISBN 978-1-4503-3617-8, 2015
Liste complète des métadonnées

https://hal.inria.fr/hal-01251563
Contributeur : Carole Delporte-Gallet <>
Soumis le : mercredi 6 janvier 2016 - 13:49:04
Dernière modification le : jeudi 11 janvier 2018 - 06:21:34

Identifiants

  • HAL Id : hal-01251563, version 1

Collections

Citation

Carole Delporte-Gallet, Hugues Fauconnier, Petr Kouznetsov, Eric Ruppert. On the Space Complexity of Set Agreement? . ACM Symposium on Principles of Distributed Computing, PODC 2015, Jul 2015, Donostia, France. Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing, PODC 2015, Donostia-San Sebastián, Spain, July 21 - 23, 2015. ACM 2015, ISBN 978-1-4503-3617-8, 2015. 〈hal-01251563〉

Partager

Métriques

Consultations de la notice

92