{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:24:07Z","timestamp":1759638247125,"version":"3.40.4"},"publisher-location":"Berlin, Heidelberg","reference-count":37,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783662451731"},{"type":"electronic","value":"9783662451748"}],"license":[{"start":{"date-parts":[[2014,1,1]],"date-time":"2014-01-01T00:00:00Z","timestamp":1388534400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-662-45174-8_1","type":"book-chapter","created":{"date-parts":[[2014,9,29]],"date-time":"2014-09-29T15:28:20Z","timestamp":1412004500000},"page":"1-15","source":"Crossref","is-referenced-by-count":2,"title":["Automatically Adjusting Concurrency to the Level of Synchrony"],"prefix":"10.1007","author":[{"given":"Pierre","family":"Fraigniaud","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Eli","family":"Gafni","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sergio","family":"Rajsbaum","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Matthieu","family":"Roy","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"4","key":"1_CR1","doi-asserted-by":"publisher","first-page":"873","DOI":"10.1145\/153724.153741","volume":"40","author":"Y. Afek","year":"1993","unstructured":"Afek, Y., Attiya, H., Dolev, D., Gafni, E., Merritt, M., Shavit, N.: Atomic snapshots of shared memory. J. ACM\u00a040(4), 873\u2013890 (1993)","journal-title":"J. ACM"},{"issue":"3","key":"1_CR2","doi-asserted-by":"publisher","first-page":"249","DOI":"10.1007\/s00446-012-0158-8","volume":"25","author":"M.K. Aguilera","year":"2012","unstructured":"Aguilera, M.K., Delporte-Gallet, C., Fauconnier, H., Toueg, S.: Partial synchrony based on set timeliness. Distributed Computing\u00a025(3), 249\u2013260 (2012)","journal-title":"Distributed Computing"},{"doi-asserted-by":"crossref","unstructured":"Aguilera, M.K., Keidar, I., Malkhi, D., Shraer, A.: Dynamic atomic storage without consensus. J. ACM\u00a058(2), 7:1\u20137:32 (2011)","key":"1_CR3","DOI":"10.1145\/1944345.1944348"},{"issue":"5-6","key":"1_CR4","doi-asserted-by":"publisher","first-page":"303","DOI":"10.1007\/s00446-010-0106-4","volume":"22","author":"M.K. Aguilera","year":"2010","unstructured":"Aguilera, M.K., Toueg, S.: Adaptive progress: A gracefully-degrading liveness property. Distributed Computing\u00a022(5-6), 303\u2013334 (2010)","journal-title":"Distributed Computing"},{"issue":"4","key":"1_CR5","doi-asserted-by":"publisher","first-page":"404","DOI":"10.1007\/s00224-012-9407-2","volume":"51","author":"D. Alistarh","year":"2012","unstructured":"Alistarh, D., Gilbert, S., Guerraoui, R., Travers, C.: Generating fast indulgent algorithms. Theory Comput. Syst.\u00a051(4), 404\u2013424 (2012)","journal-title":"Theory Comput. Syst."},{"key":"1_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"10","DOI":"10.1007\/11780823_2","volume-title":"Structural Information and Communication Complexity","author":"H. Attiya","year":"2006","unstructured":"Attiya, H.: Adapting to point contention with long-lived safe agreement. In: Flocchini, P., G\u0105sieniec, L. (eds.) SIROCCO 2006. LNCS, vol.\u00a04056, pp. 10\u201323. Springer, Heidelberg (2006)"},{"issue":"1","key":"1_CR7","doi-asserted-by":"publisher","first-page":"124","DOI":"10.1145\/200836.200869","volume":"42","author":"H. Attiya","year":"1995","unstructured":"Attiya, H., Bar-Noy, A., Dolev, D.: Sharing memory robustly in message-passing systems. J. ACM\u00a042(1), 124\u2013142 (1995)","journal-title":"J. ACM"},{"issue":"3","key":"1_CR8","doi-asserted-by":"publisher","first-page":"524","DOI":"10.1145\/79147.79158","volume":"37","author":"H. Attiya","year":"1990","unstructured":"Attiya, H., Bar-Noy, A., Dolev, D., Peleg, D., Reischuk, R.: Renaming in an asynchronous environment. Journal of the ACM\u00a037(3), 524\u2013548 (1990)","journal-title":"Journal of the ACM"},{"doi-asserted-by":"crossref","unstructured":"Attiya, H., Welch, J.: Distributed Computing Fundamentals, Simulations, and Advanced Topics, 2nd edn. John Wiley and Sons, Inc. (2004)","key":"1_CR9","DOI":"10.1002\/0471478210"},{"doi-asserted-by":"crossref","unstructured":"Borowsky, E., Gafni, E.: Generalized FLP impossibility result for t-resilient asynchronous computations. In: STOC 1993, pp. 91\u2013100. ACM (1993)","key":"1_CR10","DOI":"10.1145\/167088.167119"},{"unstructured":"Borowsky, E., Gafni, E.: The Implication of the Borowsky-Gafni Simulation on the Set-Consensus Hierarchy. Technical report, UCLA (1993)","key":"1_CR11"},{"issue":"3","key":"1_CR12","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1007\/PL00008933","volume":"14","author":"E. Borowsky","year":"2001","unstructured":"Borowsky, E., Gafni, E., Lynch, N., Rajsbaum, S.: The BG distributed simulation algorithm. Distributed Computing\u00a014(3), 127\u2013146 (2001)","journal-title":"Distributed Computing"},{"doi-asserted-by":"crossref","unstructured":"Burns, J.E., Peterson, G.L.: The ambiguity of choosing. In: PODC 1989, pp. 145\u2013157. ACM (1989)","key":"1_CR13","DOI":"10.1145\/72981.72991"},{"key":"1_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"145","DOI":"10.1007\/978-3-642-29344-3_13","volume-title":"LATIN 2012: Theoretical Informatics","author":"A. Casta\u00f1eda","year":"2012","unstructured":"Casta\u00f1eda, A., Imbs, D., Rajsbaum, S., Raynal, M.: Renaming is weaker than set agreement but for perfect renaming: A map of sub-consensus tasks. In: Fern\u00e1ndez-Baca, D. (ed.) LATIN 2012. LNCS, vol.\u00a07256, pp. 145\u2013156. Springer, Heidelberg (2012)"},{"issue":"3","key":"1_CR15","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1016\/j.cosrev.2011.04.001","volume":"5","author":"A. Casta\u00f1eda","year":"2011","unstructured":"Casta\u00f1eda, A., Rajsbaum, S., Raynal, M.: The renaming problem in shared memory systems: An introduction. Comput. Sci. Rev.\u00a05(3), 229\u2013251 (2011)","journal-title":"Comput. Sci. Rev."},{"doi-asserted-by":"crossref","unstructured":"Chandra, T., Hadzilacos, V., Jayanti, P., Toueg, S.: Wait-freedom vs. t-resiliency and the robustness of wait-free hierarchies (extended abstract). In: PODC 1994, pp. 334\u2013343. ACM (1994)","key":"1_CR16","DOI":"10.1145\/197917.198121"},{"issue":"1","key":"1_CR17","doi-asserted-by":"publisher","first-page":"132","DOI":"10.1006\/inco.1993.1043","volume":"105","author":"S. Chaudhuri","year":"1993","unstructured":"Chaudhuri, S.: More choices allow more faults: Set consensus problems in totally asynchronous systems. Information and Computation\u00a0105(1), 132\u2013158 (1993)","journal-title":"Information and Computation"},{"key":"1_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"362","DOI":"10.1007\/3-540-61769-8_23","volume-title":"Distributed Algorithms","author":"S. Chaudhuri","year":"1996","unstructured":"Chaudhuri, S., Reiners, P.: Understanding the Set Consensus Partial Order Using the Borowsky-Gafni Simulation (Extended Abstract). In: Babao\u011flu, \u00d6., Marzullo, K. (eds.) WDAG 1996. LNCS, vol.\u00a01151, pp. 362\u2013379. Springer, Heidelberg (1996)"},{"issue":"6","key":"1_CR19","doi-asserted-by":"publisher","first-page":"642","DOI":"10.1109\/71.774912","volume":"10","author":"F. Cristian","year":"1999","unstructured":"Cristian, F., Fetzer, C.: The timed asynchronous distributed system model. IEEE Trans. Parallel Distrib. Syst.\u00a010(6), 642\u2013657 (1999)","journal-title":"IEEE Trans. Parallel Distrib. Syst."},{"issue":"1","key":"1_CR20","doi-asserted-by":"publisher","first-page":"14","DOI":"10.1016\/0196-6774(82)90004-9","volume":"3","author":"D. Dolev","year":"1982","unstructured":"Dolev, D.: The byzantine generals strike again. J. of Algorithms\u00a03(1), 14\u201330 (1982)","journal-title":"J. of Algorithms"},{"issue":"2","key":"1_CR21","doi-asserted-by":"publisher","first-page":"288","DOI":"10.1145\/42282.42283","volume":"35","author":"C. Dwork","year":"1988","unstructured":"Dwork, C., Lynch, N., Stockmeyer, L.: Consensus in the presence of partial synchrony. J. ACM\u00a035(2), 288\u2013323 (1988)","journal-title":"J. ACM"},{"doi-asserted-by":"crossref","unstructured":"Fischer, M., Lynch, N.A., Paterson, M.S.: Impossibility of Distributed Commit With One Faulty Process. Journal of the ACM\u00a032(2) (April 1985)","key":"1_CR22","DOI":"10.1145\/3149.214121"},{"key":"1_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1007\/3-540-12689-9_99","volume-title":"Foundations of Computation Theory","author":"M.J. Fischer","year":"1983","unstructured":"Fischer, M.J.: The consensus problem in unreliable distributed systems (a brief survey). In: Karpinski, M. (ed.) FCT 1983. LNCS, vol.\u00a0158, pp. 127\u2013140. Springer, Heidelberg (1983)"},{"doi-asserted-by":"crossref","unstructured":"Gafni, E.: The extended BG-simulation and the characterization of t-resiliency. In: STOC 2009, pp. 85\u201392. ACM (2009)","key":"1_CR24","DOI":"10.1145\/1536414.1536428"},{"key":"1_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1007\/978-3-642-23217-6_2","volume-title":"CONCUR 2011 \u2013 Concurrency Theory","author":"E. Gafni","year":"2011","unstructured":"Gafni, E., Guerraoui, R.: Generalized universality. In: Katoen, J.-P., K\u00f6nig, B. (eds.) CONCUR 2011. LNCS, vol.\u00a06901, pp. 17\u201327. Springer, Heidelberg (2011)"},{"doi-asserted-by":"crossref","unstructured":"Guerraoui, R.: Indulgent algorithms. In: PODC, pp. 289\u2013297. ACM (2000)","key":"1_CR26","DOI":"10.1145\/343477.343630"},{"issue":"1","key":"1_CR27","doi-asserted-by":"publisher","first-page":"124","DOI":"10.1145\/114005.102808","volume":"13","author":"M. Herlihy","year":"1991","unstructured":"Herlihy, M.: Wait-free synchronization. ACM Trans. Program. Lang. Syst.\u00a013(1), 124\u2013149 (1991)","journal-title":"ACM Trans. Program. Lang. Syst."},{"doi-asserted-by":"crossref","unstructured":"Herlihy, M., Ruppert, E.: On the existence of booster types. In: FOCS 2000, pp. 653\u2013663. IEEE Computer Society (2000)","key":"1_CR28","DOI":"10.1109\/SFCS.2000.892333"},{"key":"1_CR29","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"66","DOI":"10.1007\/978-3-642-22212-2_7","volume-title":"Structural Information and Communication Complexity","author":"D. Imbs","year":"2011","unstructured":"Imbs, D., Rajsbaum, S., Raynal, M.: The universe of symmetry breaking tasks. In: Kosowski, A., Yamashita, M. (eds.) SIROCCO 2011. LNCS, vol.\u00a06796, pp. 66\u201377. Springer, Heidelberg (2011)"},{"key":"1_CR30","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"369","DOI":"10.1007\/978-3-642-05118-0_26","volume-title":"Stabilization, Safety, and Security of Distributed Systems","author":"D. Imbs","year":"2009","unstructured":"Imbs, D., Raynal, M.: Visiting Gafni\u2019s Reduction Land: From the BG Simulation to the Extended BG Simulation. In: Guerraoui, R., Petit, F. (eds.) SSS 2009. LNCS, vol.\u00a05873, pp. 369\u2013383. Springer, Heidelberg (2009)"},{"doi-asserted-by":"crossref","unstructured":"Imbs, D., Raynal, M.: The multiplicative power of consensus numbers. In: PODC 2010, pp. 26\u201335. ACM (2010)","key":"1_CR31","DOI":"10.1145\/1835698.1835705"},{"issue":"2","key":"1_CR32","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1145\/504192.504195","volume":"32","author":"I. Keidar","year":"2001","unstructured":"Keidar, I., Rajsbaum, S.: On the cost of fault-tolerant consensus when there are no faults: Preliminary version. SIGACT News\u00a032(2), 45\u201363 (2001)","journal-title":"SIGACT News"},{"issue":"7","key":"1_CR33","doi-asserted-by":"publisher","first-page":"558","DOI":"10.1145\/359545.359563","volume":"21","author":"L. Lamport","year":"1978","unstructured":"Lamport, L.: Time, clocks, and the ordering of events in a distributed system. Commun. ACM\u00a021(7), 558\u2013565 (1978)","journal-title":"Commun. ACM"},{"issue":"2","key":"1_CR34","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1145\/279227.279229","volume":"16","author":"L. Lamport","year":"1998","unstructured":"Lamport, L.: The part-time parliament. ACM Trans. Comput. Syst.\u00a016(2), 133\u2013169 (1998)","journal-title":"ACM Trans. Comput. Syst."},{"issue":"4","key":"1_CR35","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1007\/PL00008920","volume":"13","author":"W.-K. Lo","year":"2000","unstructured":"Lo, W.-K., Hadzilacos, V.: On the power of shared object types to implement one-resilient Consensus. Distributed Computing\u00a013(4), 219\u2013238 (2000)","journal-title":"Distributed Computing"},{"doi-asserted-by":"crossref","unstructured":"Lynch, N., Rajsbaum, S.: On the Borowsky-Gafni Simulation Algorithm. In: ISTCS 1996, pp. 4\u201315. IEEE Computer Society (June 1996)","key":"1_CR36","DOI":"10.1145\/248052.248060"},{"issue":"4","key":"1_CR37","doi-asserted-by":"publisher","first-page":"299","DOI":"10.1145\/98163.98167","volume":"22","author":"F.B. Schneider","year":"1990","unstructured":"Schneider, F.B.: Implementing Fault-Tolerant Services Using the State Machine Approach: A Tutorial. ACM Computing Surveys\u00a022(4), 299\u2013319 (1990)","journal-title":"ACM Computing Surveys"}],"container-title":["Lecture Notes in Computer Science","Distributed Computing"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-45174-8_1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,4]],"date-time":"2025-05-04T22:11:34Z","timestamp":1746396694000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-45174-8_1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783662451731","9783662451748"],"references-count":37,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-45174-8_1","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2014]]}}}