TY - GEN
T1 - On the space complexity of set agreement
AU - Delporte-Gallet, Carole
AU - Fauconnier, Hugues
AU - Kuznetsov, Petr
AU - Ruppert, Eric
N1 - Publisher Copyright:
© Copyright 2015 ACM.
PY - 2015/7/21
Y1 - 2015/7/21
N2 - 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 num- ber 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 + 2m - k registers and establish a nearly matching lower bound of n + m - k.
AB - 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 num- ber 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 + 2m - k registers and establish a nearly matching lower bound of n + m - k.
KW - K-set agreement
KW - M-obstruction-freedom
KW - Space complexity
U2 - 10.1145/2767386.2767406
DO - 10.1145/2767386.2767406
M3 - Conference contribution
AN - SCOPUS:84957705831
T3 - Proceedings of the Annual ACM Symposium on Principles of Distributed Computing
SP - 271
EP - 280
BT - PODC 2015 - Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing
PB - Association for Computing Machinery
T2 - ACM Symposium on Principles of Distributed Computing, PODC 2015
Y2 - 21 July 2015 through 23 July 2015
ER -