{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,3]],"date-time":"2026-09-03T02:57:15Z","timestamp":1788404235202,"version":"build-2803163510"},"reference-count":36,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2002,1]]},"abstract":"<jats:p>This paper introduces a simple notion of layering as a tool for analyzing well-behaved runs of a given model of distributed computation. Using layering, a model-independent analysis of the consensus problem is performed and then applied to proving lower bounds and impossibility results for consensus in a number of familiar and less familiar models. The proofs are simpler and more direct than existing ones, and they expose a unified structure to the difficulty of reaching consensus. In particular, the proofs for the classical synchronous and asynchronous models now follow the same outline. A new notion of connectivity among states in runs of a consensus protocol, called potence connectivity, is introduced. This notion is more general than previous notions of connectivity used for this purpose and plays a keyrole in the uniform analysis of consensus.<\/jats:p>","DOI":"10.1137\/s0097539799364006","type":"journal-article","created":{"date-parts":[[2003,6,11]],"date-time":"2003-06-11T11:12:06Z","timestamp":1055329926000},"page":"989-1021","source":"Crossref","is-referenced-by-count":85,"title":["A Layered Analysis of Consensus"],"prefix":"10.1137","volume":"31","author":[{"given":"Yoram","family":"Moses","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sergio","family":"Rajsbaum","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2012,2,17]]},"reference":[{"key":"R1","doi-asserted-by":"publisher","DOI":"10.1145\/153724.153741"},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(99)00100-3"},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.1145\/200836.200869"},{"key":"R4","doi-asserted-by":"crossref","unstructured":"H. Attiya and S. Rajsbaum,\n                      The combinatorial structure of wait\u2010free solvable tasks\n                      , in Proceedings of the 10th International Workshop on Distributed Algorithms (WDAG), Lecture Notes in Comput. Sci. 1151, O. Babaoglu and K. Marzullo, eds., Springer\u2010Verlag, New York, 1996, pp. 321\u2013343.","DOI":"10.1007\/3-540-61769-8_21"},{"key":"R5","unstructured":"H. Attiya and J. Welch,\n                      Distributed Computing: Fundamentals, Simulations and Advanced Topics\n                      , McGraw\u2013Hill, New York, 1998."},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1145\/4221.4227"},{"key":"R7","doi-asserted-by":"crossref","unstructured":"Z. Bar\u2010Joseph and M. Ben\u2010Or,\n                      A tight lower bound for randomized synchronous consensus\n                      , in Proceedings of the 17th ACM Symposium on Principles of Distributed Computing (PODC), ACM, New York, 1998, pp. 193\u2013199.","DOI":"10.1145\/277697.277733"},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(90)90020-F"},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(94)00157-E"},{"key":"R10","doi-asserted-by":"crossref","unstructured":"E. Borowsky and E. Gafni,\n                      Generalized FLP impossibility result for t\u2010resilient asynchronous computations\n                      , in Proceedings of the 1993 ACM Symposium on Theory of Computing (STOC), ACM, New York, 1993, pp. 91\u2013100.","DOI":"10.1145\/167088.167119"},{"key":"R11","doi-asserted-by":"crossref","unstructured":"E. Borowsky and E. Gafni,\n                      A simple algorithmically reasoned characterization of wait\u2010free computations\n                      , in Proceedings of the 16th ACM Symposium on Principles of Distributed Computing (PODC), ACM, New York, 1997, pp. 189\u2013198.","DOI":"10.1145\/259380.259439"},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1007\/PL00008933"},{"key":"R13","doi-asserted-by":"crossref","unstructured":"T. Chandra and S. Toueg,\n                      Unreliable failure detectors for asynchronous systems\n                      , in Proceedings of the 10th ACM Symposium on Principles of Distributed Computing (PODC), ACM, New York, 1991, pp. 257\u2013272.","DOI":"10.1145\/112600.112627"},{"key":"R14","doi-asserted-by":"publisher","DOI":"10.1145\/355483.355489"},{"key":"R15","doi-asserted-by":"publisher","DOI":"10.1137\/0212045"},{"key":"R16","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(90)90014-9"},{"key":"R17","doi-asserted-by":"publisher","DOI":"10.7551\/mitpress\/5803.001.0001"},{"key":"R18","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(82)90033-3"},{"key":"R19","unstructured":"M. J. Fischer,\n                      The Consensus Problem in Unreliable Distributed Systems (a Brief Survey)\n                      , Research report YALE\/DCS\/RR\u2010273, Dept. Comp. Sci., Yale University, New Haven, CT, 1983."},{"key":"R20","doi-asserted-by":"publisher","DOI":"10.1145\/3149.214121"},{"key":"R21","doi-asserted-by":"crossref","unstructured":"E. Gafni,\n                      Round\u2010by\u2010round fault detectors: Unifying synchrony and asynchrony\n                      , in Proceedings of the 17th ACM Symposium on Principles of Distributed Computing (PODC), ACM, New York, 1998, pp. 143\u2013152.","DOI":"10.1145\/277697.277724"},{"key":"R22","doi-asserted-by":"publisher","DOI":"10.1145\/114005.102808"},{"key":"R23","doi-asserted-by":"crossref","unstructured":"Maurice Herlihy, Sergio Rajsbaum, Algebraic topology and distributed computing\u2014a primer, Lecture Notes in Comput. Sci., Vol. 1000, Springer, Berlin, 1995, 203\u201321797b:68059","DOI":"10.1007\/BFb0015245"},{"key":"R24","doi-asserted-by":"crossref","unstructured":"M. P. Herlihy, S. Rajsbaum, and M. R. Tuttle,\n                      Unifying synchronous and asynchronous message\u2010passing models\n                      , in Proceedings of the 17th ACM Symposium on Principles of Distributed Computing (PODC), ACM, New York, 1998, pp. 133\u2013142.","DOI":"10.1145\/277697.277722"},{"key":"R25","doi-asserted-by":"crossref","unstructured":"Maurice Herlihy, Sergio Rajsbaum, New perspectives in distributed computing, Lecture Notes in Comput. Sci., Vol. 1672, Springer, Berlin, 1999, 170\u20131861731234","DOI":"10.1007\/3-540-48340-3_16"},{"key":"R26","doi-asserted-by":"publisher","DOI":"10.1145\/331524.331529"},{"key":"R27","doi-asserted-by":"crossref","unstructured":"G. Hoest and N. Shavit,\n                      Towards a topological characterization of asynchronous complexity\n                      , in Proceedings of the 16th ACM Symposium on Principles of Distributed Computing (PODC), ACM, New York, 1997, pp. 199\u2013208.","DOI":"10.1145\/259380.259440"},{"key":"R28","doi-asserted-by":"crossref","unstructured":"I. Keidar and S. Rajsbaum,\n                      On the Cost of Fault\u2010Tolerant Consensus When There Are No Faults\u2014A Tutorial\n                      , Technical report MIT\u2010LCS\u2010TR\u2010821, MIT, Cambridge, MA, 2001.","DOI":"10.1145\/504192.504195"},{"key":"R29","unstructured":"Michael Loui, Hosame Abu\u2010Amara, Memory requirements for agreement among unreliable asynchronous processes, JAI, Greenwich, CT, 1987, 163\u201318389c:68011"},{"key":"R30","doi-asserted-by":"publisher","DOI":"10.1007\/BF02242738"},{"key":"R31","volume-title":"Distributed algorithms","author":"Lynch Nancy","year":"1996"},{"key":"R32","doi-asserted-by":"crossref","unstructured":"Y. Moses and S. Rajsbaum,\n                      The unified structure of consensus: A layered analysis approach\n                      , in Proceedings of the 17th ACM Symposium on Principles of Distributed Computing (PODC), ACM, New York, 1998, pp. 123\u2013132.","DOI":"10.1145\/277697.277720"},{"key":"R33","doi-asserted-by":"publisher","DOI":"10.1145\/322186.322188"},{"key":"R34","doi-asserted-by":"crossref","unstructured":"M. Saks and F. Zaharoglou,\n                      Wait\u2010free k\u2010set agreement is impossible: The topology of public knowledge\n                      , in Proceedings of the 1993 ACM Symposium on Theory of Computing (STOC), ACM, New York, 1993, pp. 101\u2013110.","DOI":"10.1145\/167088.167122"},{"key":"R35","doi-asserted-by":"crossref","unstructured":"Nicola Santoro, Peter Widmayer, Time is not a healer (preliminary version), Lecture Notes in Comput. Sci., Vol. 349, Springer, Berlin, 1989, 304\u20133131027411","DOI":"10.1007\/BFb0028994"},{"key":"R36","doi-asserted-by":"crossref","unstructured":"R. van der Meyden and Y. Moses,\n                      Top\u2010down considerations on distributed computing (invited talk)\n                      , in Proceedings of the 12th International Symposium on Distributed Computing (DISC), S. Kutten, ed., Springer\u2010Verlag, New York, 1998, pp. 16\u201320.","DOI":"10.1007\/BFb0056469"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/S0097539799364006","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:22:04Z","timestamp":1787336524000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/S0097539799364006"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2002,1]]},"references-count":36,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2002,1]]}},"alternative-id":["10.1137\/S0097539799364006"],"URL":"https:\/\/doi.org\/10.1137\/s0097539799364006","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2002,1]]}}}