Tight bounds for k-set agreement

ABSTRACT

We prove tight bounds on the time needed to solve k-set agreement. In this problem, each processor starts with an arbitrary input value taken from a fixed set, and halts after choosing an output value. In every execution, at most k distinct output values may be chosen, and every processor's output value must be some processor's input value. We analyze this problem in a synchronous, message-passing model where processors fail by crashing. We prove a lower bound of f/k+1 degree of coordination required, and the number of faults tolerated, even in idealized models like the synchronous model. The proof of this result is interesting because it is the first to apply topological techniques to the synchronous model.

REFERENCES

• 1: Hagit Attiya , Sergio Rajsbaum, The Combinatorial Structure of Wait-free Solvable Tasks (Extended Abstract), Proceedings of the 10th International Workshop on Distributed Algorithms, p.322-343, October 09-11, 1996
• 2: Philip A. Bernstein , Vassco Hadzilacos , Nathan Goodman, Concurrency control and recovery in database systems, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1987
• 3: 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, p.91-100, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167119]
• 4: CHAUDHURI, S. 1991. Towards a complexity hierarchy of wait-free concurrent objects. In Proceedings of the 3rd IEEE Symposium on Parallel and Distributed Processing (Dec.). IEEE Computer Society Press, Los Alamitos, Calif.
• 5: Soma Chaudhuri, More choices allow more faults: set consensus problems in totally asynchronous systems, Information and Computation, v.105 n.1, p.132-158, July 1993 [doi>10.1006/inco.1993.1043]
• 6: CHAUDHURI, S., HERLIHY, M., LYNCH, N., AND TUTTLE, M. R. 1993. A tight lower bound for k-set agreement. In Proceedings of the 34th IEEE Symposium on Foundations of Computer Science (Nov.). IEEE Computer Society Press, Los Alamitos, Calif., pp. 206-215.
• 7: DOLEV, D. 1982. The Byzantine generals strike again. J. Algorithms 3, 1 (Mar.). 14-30.
• 8: DOLEV, D., AND STRONG, H. R. 1983. Authenticated algorithms for Byzantine agreement. SIAM J. Comput. 12, 3 (Nov.), 656-666.
• 9: Cynthia Dwork , Yoram Moses, Knowledge and common knowledge in a byzantine environment: crash failures, Information and Computation, v.88 n.2, p.156-186, Oct. 1990 [doi>10.1016/0890-5401(90)90014-9]
• 10: Michael J. Fischer, The Consensus Problem in Unreliable Distributed Systems (A Brief Survey), Proceedings of the 1983 International FCT-Conference on Fundamentals of Computation Theory, p.127-140, August 21-27, 1983
• 11: FISCHER, M. J., AND LYNCH, N. A. 1982. A lower bound for the time to assure interactive consistency. Inf. Proc. Lett. 14, 4 (June), 183-186.
• 12: Michael J. Fischer , Nancy A. Lynch , Michael S. Paterson, Impossibility of distributed consensus with one faulty process, Journal of the ACM (JACM), v.32 n.2, p.374-382, April 1985 [doi>10.1145/3149.214121]
• 13: Eli Gafni , Elias Koutsoupias, Three-Processor Tasks Are Undecidable, SIAM Journal on Computing, v.28 n.3, p.970-983, Feb. 1999 [doi>10.1137/S0097539796305766]
• 14: HADZILACOS, V. 1983. A lower bound for Byzantine agreement with fail-stop processors. Tech. Rep. TR-21-83. Harvard Univ.
• 15: Maurice Herlihy, Wait-free synchronization, ACM Transactions on Programming Languages and Systems (TOPLAS), v.13 n.1, p.124-149, Jan. 1991 [doi>10.1145/114005.102808]
• 16: Maurice Herlihy , Sergio Rajsbaum, Set consensus using arbitrary objects (preliminary version), Proceedings of the thirteenth annual ACM symposium on Principles of distributed computing, p.324-333, August 14-17, 1994, Los Angeles, California, United States [doi>10.1145/197917.198119]
• 17: Maurice Herlihy , Sergio Rajsbaum, Algebraic spans, Mathematical Structures in Computer Science, v.10 n.4, p.549-573, August 2000 [doi>10.1017/S0960129500003170]
• 18: Maurice Herlihy , Nir Shavit, The topological structure of asynchronous computability, Journal of the ACM (JACM), v.46 n.6, p.858-923, Nov. 1999 [doi>10.1145/331524.331529]
• 19: Leslie Lamport , Robert Shostak , Marshall Pease, The Byzantine Generals Problem, ACM Transactions on Programming Languages and Systems (TOPLAS), v.4 n.3, p.382-401, July 1982 [doi>10.1145/357172.357176]
• 20: MERRITT, M. 1985. Notes on the Dolev-Strong lower bound for byzantine agreement. Unpublished manuscript.
• 21: MOSES, Y., AND TUTTLE, M. R. 1988. Programming simultaneous actions using common knowledge. Algorithmica 3, 1, 121-169.
• 22: M. Pease , R. Shostak , L. Lamport, Reaching Agreement in the Presence of Faults, Journal of the ACM (JACM), v.27 n.2, p.228-234, April 1980 [doi>10.1145/322186.322188]
• 23: Michael Saks , Fotios Zaharoglou, Wait-Free k-Set Agreement is Impossible: The Topology of Public Knowledge, SIAM Journal on Computing, v.29 n.5, p.1449-1483, March 2000 [doi>10.1137/S0097539796307698]
• 24: SPANIER, E. H. 1966. Algebraic Topology. Springer-Verlag, New York.
• 25: WENSLEY, J. H., GOLDBERG, J., GREEN, M. W., LEVITT, K. N., MELLIAR-SMITH, P. M., SHOSTAK, R. E., AND WEINSTOCK, C. B. 1978. SIFT: Design and analysis of a fault-tolerant computer for aircraft control. Proc. IEEE 66, 10, (Oct.), 1240-1255.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems
          Subjects: Distributed applications

Additional Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Fault tolerance; Reliability, availability, and serviceability

  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.3 Concurrent Programming
          Subjects: Distributed programming
  D.2 SOFTWARE ENGINEERING
        D.2.12 Interoperability
            Subjects: Distributed objects

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

General Terms:
Algorithms, Design, Performance, Reliability, Theory

Keywords:
k-set agreement, Spwener's Lemma, crash failure model, message-passing systems, synchronous systems, topology