Partial synchrony based on set timeliness

ABSTRACT

We introduce a new model of partial synchrony for read-write shared memory systems. This model is based on the notion of set timeliness--a natural and straightforward generalization of the seminal concept of timeliness in the partially synchrony model of Dwork, Lynch and Stockmeyer [8].

Despite its simplicity, the concept of set timeliness is powerful enough to describe the first partially synchronous system for read/write shared memory that separates consensus and set agreement: we show that this system has enough timeliness for solving set agreement but not enough for solving consensus.

Set timeliness also allows us to define a family of partially synchronous systems of n processes, denoted S^k_n (1 ≤ k ≤ n − 1), which closely matches the family of k-anti-Ω failure detectors that were recently shown to be the weakest failure detectors for the k-set agreement problem: We prove that for 1 ≤ k ≤ n − 1, S^k_n is synchronous enough to implement k-anti-Ω but not enough to implement (k − 1)-anti-Ω.

The results above show that set timeliness can be used to study and compare the partial synchrony requirements of problems that are strictly weaker than consensus.

REFERENCES

• 1: Marcos K. Aguilera , Carole Delporte-Gallet , Hugues Fauconnier , Sam Toueg, Communication-efficient leader election and consensus with limited link synchrony, 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.1011816]
• 2: M. K. Aguilera, C. Delporte-Gallet, H. Fauconnier, and S. Toueg. On implementing Omega in systems with weak reliability and synchrony assumptions. Distributed Computing, 21(4):285--314, Oct. 2008.
• 3: Marcos K. Aguilera , Sam Toueg, Timeliness-based wait-freedom: a gracefully degrading progress condition, Proceedings of the twenty-seventh ACM symposium on Principles of distributed computing, August 18-21, 2008, Toronto, Canada [doi>10.1145/1400751.1400792]
• 4: A. F. Anta, S. Rajsbaum, and C. Travers. Weakest failure detectors via an egg-laying simulation (preliminary version). Tech Report RoSaC-2009-2, Grupo de Sistemas y Comunicaciones, Universidad Rey Juan Carlos, Jan. 2009. Also appears as a brief announcement in PODC 2009.
• 5: 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]
• 6: 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]
• 7: C. Delporte-Gallet, H. Fauconnier, R. Guerraoui, and A. Tielmann. The disagreement power of an adversary. Article id hal-00376981, Hyper Article en Ligne, Apr. 2009. Available at http://hal.archives-ouvertes.fr/hal-00376981.
• 8: Cynthia Dwork , Nancy Lynch , Larry Stockmeyer, Consensus in the presence of partial synchrony, Journal of the ACM (JACM), v.35 n.2, p.288-323, April 1988 [doi>10.1145/42282.42283]
• 9: A. Fernández and M. Raynal. From an intermittent rotating star to a leader. Technical Report 1810, IRISA, Université de Rennes, France, Aug. 2006.
• 10: 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]
• 11: Eli Gafni, Round-by-round fault detectors (extended abstract): unifying synchrony and asynchrony, Proceedings of the seventeenth annual ACM symposium on Principles of distributed computing, p.143-152, June 28-July 02, 1998, Puerto Vallarta, Mexico [doi>10.1145/277697.277724]
• 12: Eli Gafni , Petr Kuznetsov, The weakest failure detector for solving k-set agreement, Proceedings of the 28th ACM symposium on Principles of distributed computing, August 10-12, 2009, Calgary, AB, Canada [doi>10.1145/1582716.1582735]
• 13: M. Hutle, D. Malkhi, U. Schmid, and L. Zhou. Chasing the weakest system model for implementing Ω and Consensus. IEEE Transactions on Dependable and Secure Computing. To appear.
• 14: Ernesto Jiménez , Sergio Arévalo , Antonio Fernández, Implementing unreliable failure detectors with unknown membership, Information Processing Letters, v.100 n.2, p.60-63, 31 October 2006 [doi>10.1016/j.ipl.2006.05.009]
• 15: Wai-Kau Lo , Vassos Hadzilacos, Using Failure Detectors to Solve Consensus in Asynchronous Sharde-Memory Systems (Extended Abstract), Proceedings of the 8th International Workshop on Distributed Algorithms, p.280-295, September 29-October 01, 1994
• 16: M. C. Loui and H. H. Abu-Amara. Memory requirements for agreement among unreliable asynchronous processes. Advances in Computing Research, 4:163--183, 1987.
• 17: D. Malkhi, F. Oprea, and L. Zhou. Omega meets Paxos: leader election and stability without eventual timely links. In International Conference on Distributed Computing, volume 3724 of LNCS, pages 199--213. Springer Verlag, Sept. 2005.
• 18: Yoram Moses , Sergio Rajsbaum, A Layered Analysis of Consensus, SIAM Journal on Computing, v.31 n.4, p.989-1021, 2002 [doi>10.1137/S0097539799364006]
• 19: Achour Mostefaoui , Michel Raynal , Corentin Travers, Time-Free and Timer-Based Assumptions Can Be Combined to Obtain Eventual Leadership, IEEE Transactions on Parallel and Distributed Systems, v.17 n.7, p.656-666, July 2006 [doi>10.1109/TPDS.2006.95]
• 20: S. Rajsbaum, M. Raynal, and C. Travers. Failure detectors as schedulers (an algorithmically-reasoned characterization). Technical Report 1838, IRISA, Université de Rennes, France, Mar. 2007.
• 21: Sergio Rajsbaum , Michel Raynal , Corentin Travers, The Iterated Restricted Immediate Snapshot Model, Proceedings of the 14th annual international conference on Computing and Combinatorics, June 27-29, 2008, Dalian, China [doi>10.1007/978-3-540-69733-6_48]
• 22: Piotr Zielinski, Anti-Ω: the weakest failure detector for set agreement, Proceedings of the twenty-seventh ACM symposium on Principles of distributed computing, August 18-21, 2008, Toronto, Canada [doi>10.1145/1400751.1400761]

INDEX TERMS

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

Additional Classification:
  B. Hardware
  B.3 MEMORY STRUCTURES
      B.3.2 Design Styles
          Subjects: Shared memory

  D. Software
  D.4 OPERATING SYSTEMS
      D.4.1 Process Management
          Subjects: Concurrency

  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.1 Models of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.m Miscellaneous

General Terms:
Algorithms, Design, Theory

Keywords:
algorithms, bivalency, consensus, failure detectors, impossibility, partial synchrony, set agreement, timeliness