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.

References

1. Yehuda Afek, Hagit Attiya, Danny Dolev, Eli Gafni, Michael Merritt, and Nir Shavit. Atomic snapshots of shared memory. Journal of the ACM, 40(4):873--890, September 1993.
2. Elizabeth Borowsky and Eli Gafni. Generalized FLP impossibility result for $t$-resilient asynchronous computations. In Proc. 25th ACM Symposium on Theory of Computing, pages 91--100, 1993.
3. Soma Chaudhuri. More choices allow more faults: Set consensus problems in totally asynchronous systems. Information and Computation, 105(1):132--158, July 1993.
4. Carole Delporte-Gallet, Hugues Fauconnier, Eli Gafni, and Sergio Rajsbaum. Black art: Obstruction-free k-set agreement with |MWMR registers|<|proccesses|. In Proc. 1st International Conference on Networked Systems, volume 7853 of LNCS, pages 28--41, 2013.
5. Carole Delporte-Gallet, Hugues Fauconnier, Petr Kuznetsov, and Eric Ruppert. On the space complexity of set agreement. CoRR, abs/1505.02690, 2015.
6. Faith Ellen, Panagiota Fatourou, and Eric Ruppert. Time lower bounds for implementations of multi-writer snapshots. Journal of the ACM, 54(6), December 2007.
7. Faith Ellen Fich, Maurice Herlihy, and Nir Shavit. On the space complexity of randomized synchronization. Journal of the ACM, 45(5):843--862, September 1998.
8. Rachid Guerraoui and Eric Ruppert. Anonymous and fault-tolerant shared-memory computing. Distributed Computing, 20(3):165--177, October 2007.
9. Maurice Herlihy. Wait-free synchronization. ACM Transactions on Programming Languages and Systems, 13(1):124--149, January 1991.
10. Maurice Herlihy, Victor Luchangco, and Mark Moir. Obstruction-free synchronization: Double-ended queues as an example. In Proc. 23rd International Conference on Distributed Computing Systems, pages 522--529, 2003.
11. Maurice Herlihy and Nir Shavit. The topological structure of asynchronous computability. Journal of the ACM, 46(6):858--923, November 1999.
12. Michael Saks and Fotios Zaharoglou. Wait-free k-set agreement is impossible: The topology of public knowledge. SIAM Journal on Computing, 29(5):1449--1483, 2000.
13. Gadi Taubenfeld. Contention-sensitive data structures and algorithms. In Proc.\ 23rd International Symposium on Distributed Computing, volume 5805 of LNCS, pages 157--171, 2009.
14. Paul M. B. Vitányi and Baruch Awerbuch. Atomic shared register access by asynchronous hardware. In Proc. 27th Symposium on Foundations of Computer Science, pages 233--243, 1986.
15. Jiong Yang, Gil Neiger, and Eli Gafni. Structured derivations of consensus algorithms for failure detectors. In Proc. 17th ACM Symposium on Principles of Distributed Computing, pages 297--306, 1998.

Index Terms

• Software and its engineering

  • Software organization and properties

    • Contextual software domains

      • Operating systems

        • Process management

          • Concurrency control

          • Multiprocessing / multiprogramming / multitasking

          • Process synchronization

• Theory of computation

  • Design and analysis of algorithms