Sharing is harder than agreeing

ABSTRACT

One of the most celebrated results of the theory of distributed computing is the impossibility, in an asynchronous system of n processes that communicate through shared memory registers, to solve the set agreement problem where the processes need to decide on up to n-1 among their n initial values. In short, the result indicates that the register abstraction is too weak to implement the set agreement one.

This paper explores the relation between these abstractions in a message passing system where a register is not a given physical device but is rather itself implemented by processes communicating through message passing. We show that, maybe surprisingly, the information about process failures that is necessary and sufficient to implement a register shared by two particular processes is sufficient but not necessary to implement set agreement.

We later generalize this result by considering k-set agreement, where the processes can decide on up to k values, and comparing it with a register shared by any particular subset of 2k processes. We prove

that, for 1 ≤ k ≤ n/2, (a) any failure information that is sufficient to implement a register shared by 2k processes is sufficient to implement (n-k)-set agreement but (b) a failure information that is sufficient for (n-k)-set agreement is not sufficient for a register shared by 2k processes. We also prove that (c) a failure information that is sufficient for a register shared by 2k processes is not sufficient for ((n-k)-1)-set agreement.

REFERENCES

• 1: Hagit Attiya , Amotz Bar-Noy , Danny Dolev, Sharing memory robustly in message-passing systems, Journal of the ACM (JACM), v.42 n.1, p.124-142, Jan. 1995 [doi>10.1145/200836.200869]
• 2: Jennifer L. Welch , Hagit Attiya, Distributed computing: fundamentals, simulations and advanced topics, McGraw-Hill, Inc., Hightstown, NJ, 1998
• 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: Tushar Deepak Chandra , Vassos Hadzilacos , Sam Toueg, The weakest failure detector for solving consensus, Journal of the ACM (JACM), v.43 n.4, p.685-722, July 1996 [doi>10.1145/234533.234549]
• 5: Tushar Deepak Chandra , Sam Toueg, Unreliable failure detectors for reliable distributed systems, Journal of the ACM (JACM), v.43 n.2, p.225-267, March 1996 [doi>10.1145/226643.226647]
• 6: 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]
• 7: W. Chen, J. Zhang, Y. Chen, and X. Liu. Weakening failure detectors for k-set agreement via the approach. In Proceedings of DIStributed Computing, volume 4731 of Lecture Notes in Computer Science, pages 123--138, Sept. 2007.
• 8: C. Delporte-Gallet, H. Fauconnier, and R. Guerraoui. Shared memory vs message passing. Technical Report 200377, EPFL Lausanne, 2003.
• 9: C. Delporte-Gallet, H. Fauconnier, and R. Guerraoui. (almost) all objects are universal in message passing systems. In Proceedings of DIStributed Computing, volume 3724 of Lecture Notes in Computer Science, pages 184--198, Sept. 2005.
• 10: Carole Delporte-Gallet , Hugues Fauconnier , Rachid Guerraoui , Vassos Hadzilacos , Petr Kouznetsov , Sam Toueg, The weakest failure detectors to solve certain fundamental problems in distributed computing, Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing, July 25-28, 2004, St. John's, Newfoundland, Canada [doi>10.1145/1011767.1011818]
• 11: Eli GAFNI , Michel RAYNAL , Corentin TRAVERS, Test & Set, Adaptive Renaming and Set Agreement: a Guided Visit to Asynchronous Computability, Proceedings of the 26th IEEE International Symposium on Reliable Distributed Systems, p.93-102, October 10-12, 2007
• 12: Rachid Guerraoui , Maurice Herlihy , Petr Kouznetsov , Nancy Lynch , Calvin Newport, On the weakest failure detector ever, Proceedings of the twenty-sixth annual ACM symposium on Principles of distributed computing, August 12-15, 2007, Portland, Oregon, USA [doi>10.1145/1281100.1281135]
• 13: Maurice Herlihy , Nir Shavit, The asynchronous computability theorem for t-resilient tasks, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.111-120, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167125]
• 14: 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]
• 15: L. Lamport. On interprocess communication; part I and II. Distributed Computing, 1(2):77--101, 1986.
• 16: L. Lamport. On interprocess communication; part I: Basic formalism. Distributed Computing, 1(2):77--85, 1986.
• 17: Achour Mostefaoui , Sergio Rajsbaum , Michel Raynal, The combined power of conditions and failure detectors to solve asynchronous set agreement, Proceedings of the twenty-fourth annual ACM symposium on Principles of distributed computing, July 17-20, 2005, Las Vegas, NV, USA [doi>10.1145/1073814.1073848]
• 18: Achour Mostefaoui , Sergio Rajsbaum , Michel Raynal , Corentin Travers, Irreducibility and additivity of set agreement-oriented failure detector classes, Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing, July 23-26, 2006, Denver, Colorado, USA [doi>10.1145/1146381.1146406]
• 19: Achour Mostéfaoui , Michel Raynal, k-set agreement with limited accuracy failure detectors, Proceedings of the nineteenth annual ACM symposium on Principles of distributed computing, p.143-152, July 16-19, 2000, Portland, Oregon, United States [doi>10.1145/343477.343536]
• 20: Gil Neiger, Failure detectors and the wait-free hierarchy (extended abstract), Proceedings of the fourteenth annual ACM symposium on Principles of distributed computing, p.100-109, August 20-23, 1995, Ottowa, Ontario, Canada [doi>10.1145/224964.224976]
• 21: Michael Saks , Fotios Zaharoglou, Wait-free k-set agreement is impossible: the topology of public knowledge, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.101-110, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167122]
• 22: P. Zielinski. Anti-Ω: the weakest failure detector for set agreement. Technical report, UCAM-CL-TR-694, 2007.

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.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems
          Subjects: Network operating systems

  D. Software
  D.4 OPERATING SYSTEMS
      D.4.1 Process Management
          Subjects: Multiprocessing/multiprogramming/multitasking; Concurrency; Synchronization

  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.1 Models of Computation
          Subjects: Computability theory

General Terms:
Algorithms, Reliability, Theory

Keywords:
asynchronous system, failure detector, k-set agreement, message passing, register