{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:50:23Z","timestamp":1750308623021,"version":"3.41.0"},"reference-count":44,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2011,10,1]],"date-time":"2011-10-01T00:00:00Z","timestamp":1317427200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Auton. Adapt. Syst."],"published-print":{"date-parts":[[2011,10]]},"abstract":"\n This article addresses the consensus problem in asynchronous systems prone to process crashes, where additionally the processes are anonymous (they cannot be distinguished one from the other: they have no name and execute the same code). To circumvent the three computational adversaries (asynchrony, failures, and anonymity) each process is provided with a failure detector of a class denoted\n \u03c8<\/jats:italic>\n , that gives it an upper bound on the number of processes that are currently alive (in a nonanonymous system, the classes\n \u03c8<\/jats:italic>\n and\n P<\/jats:italic>\n ---the class of perfect failure detectors---are equivalent).\n <\/jats:p>\n \n The article first presents a simple\n \u03c8<\/jats:italic>\n -based consensus algorithm where the processes decide in 2\n t<\/jats:italic>\n + 1 asynchronous rounds (where\n t<\/jats:italic>\n is an upper bound on the number of faulty processes). It then shows one of its main results, namely 2\n t<\/jats:italic>\n + 1 is a lower bound for consensus in the anonymous systems equipped with\n \u03c8<\/jats:italic>\n . The second contribution addresses early-decision. The article presents and proves correct an early-deciding algorithm where the processes decide in min(2\n f<\/jats:italic>\n + 2, 2\n t<\/jats:italic>\n + 1) asynchronous rounds (where\n f<\/jats:italic>\n is the actual number of process failures). This leads us to think that anonymity doubles the cost (with respect to synchronous systems) and it is conjectured that min(2\n f<\/jats:italic>\n + 2, 2\n t<\/jats:italic>\n + 1) is the corresponding lower bound.\n <\/jats:p>\n \n The article finally considers the\n k<\/jats:italic>\n -set agreement problem in anonymous systems. It first shows that the previous\n \u03c8<\/jats:italic>\n -based consensus algorithm solves the\n k<\/jats:italic>\n -set agreement problem in\n Rt<\/jats:italic>\n = 2\u230at k\u230b + 1 asynchronous rounds. Then, considering a family of failure detector classes {\n \u03c8\u2113<\/jats:italic>\n }0 \u2264\n \u2113<\/jats:italic>\n <\n k<\/jats:italic>\n that generalizes the class\n \u03c8<\/jats:italic>\n (=\n \u03c8<\/jats:italic>\n 0<\/jats:sub>\n ), the article presents an algorithm that solves the\n k<\/jats:italic>\n -set agreement in\n Rt,\u2113<\/jats:italic>\n = 2 \u230a\n t k \u2212 \u2113<\/jats:italic>\n \u230b + 1 asynchronous rounds. This last formula relates the cost (\n Rt,\u2113<\/jats:italic>\n ) the coordination degree of the problem (\n k<\/jats:italic>\n ), the maximum number of failures (\n t<\/jats:italic>\n ), and the the strength (\n \u2113<\/jats:italic>\n ) of the underlying failure detector. Finally the article concludes by presenting problems that remain open.\n <\/jats:p>","DOI":"10.1145\/2019591.2019592","type":"journal-article","created":{"date-parts":[[2011,10,27]],"date-time":"2011-10-27T13:17:37Z","timestamp":1319721457000},"page":"1-28","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":11,"title":["The Price of Anonymity"],"prefix":"10.1145","volume":"6","author":[{"given":"Fran\u00e7ois","family":"Bonnet","sequence":"first","affiliation":[{"name":"IRISA, University of Rennes"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michel","family":"Raynal","sequence":"additional","affiliation":[{"name":"IRISA, University of Rennes"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2011,10]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(99)00100-3"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/800141.804655"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/509907.509983"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-005-0145-4"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1006\/inco.2001.3119"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/48014.48247"},{"key":"e_1_2_1_7_1","doi-asserted-by":"crossref","unstructured":"Attiya H. and Welch J. 2004. Distributed Computing Fundamentals Simulation and Advanced Topics 2nd Ed. Series on Parallel and Distributed Computing Wiley. Attiya H. and Welch J. 2004. Distributed Computing Fundamentals Simulation and Advanced Topics 2nd Ed. Series on Parallel and Distributed Computing Wiley.","DOI":"10.1002\/0471478210"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/167088.167119"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-005-0121-z"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/226643.226647"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/234533.234549"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1993.1043"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/355483.355489"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/11596042_77"},{"volume-title":"Proceedings of the IEEE International Conference on Dependable Systems and Networks (DSN\u201902)","author":"Delporte-Gallet C.","key":"e_1_2_1_15_1","unstructured":"Delporte-Gallet , C. , Fauconnier , H. , and Guerraoui , R . 2002. A realistic look at failure detectors . In Proceedings of the IEEE International Conference on Dependable Systems and Networks (DSN\u201902) . 345--352. Delporte-Gallet, C., Fauconnier, H., and Guerraoui, R. 2002. A realistic look at failure detectors. In Proceedings of the IEEE International Conference on Dependable Systems and Networks (DSN\u201902). 345--352."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2003.1233713"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/96559.96565"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/11596356_111"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(90)90014-9"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/0167-6423(83)90013-8"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(82)90033-3"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/3149.214121"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/277697.277724"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/bxl046"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-007-0042-0"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/79147.79161"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/114005.102808"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/71.879773"},{"volume-title":"Proceedings of the 23th International IEEE Conference on Distributed Computing Systems (ICDCS\u201903)","author":"Herlihy M.","key":"e_1_2_1_29_1","unstructured":"Herlihy , M. , Luchangco , V. , and Moir , M . 2003. Obstruction-free synchronization: Double-ended queues as an example . In Proceedings of the 23th International IEEE Conference on Distributed Computing Systems (ICDCS\u201903) . 522--529. Herlihy, M., Luchangco, V., and Moir, M. 2003. Obstruction-free synchronization: Double-ended queues as an example. In Proceedings of the 23th International IEEE Conference on Distributed Computing Systems (ICDCS\u201903). 522--529."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/331524.331529"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(02)00333-2"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/12.262125"},{"key":"e_1_2_1_33_1","first-page":"163","article-title":"Memory requirements for agreement among unreliable asynchronous processes","volume":"4","author":"Loui M.","year":"1987","unstructured":"Loui , M. and Abu-Amara , H. 1987 . Memory requirements for agreement among unreliable asynchronous processes . Adv. Comput. Res. 4 , 163 -- 183 . Loui, M. and Abu-Amara, H. 1987. Memory requirements for agreement among unreliable asynchronous processes. Adv. Comput. Res. 4, 163--183.","journal-title":"Adv. Comput. Res."},{"volume-title":"Distributed Algorithms","author":"Lynch N.","key":"e_1_2_1_34_1","unstructured":"Lynch , N. 1996. Distributed Algorithms . Morgan Kaufmann Publisher . Lynch, N. 1996. Distributed Algorithms. Morgan Kaufmann Publisher."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2009.01.001"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01762112"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0129626401000452"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1137\/050645580"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-008-0064-2"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1007\/s004460050045"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.5555\/826039.826979"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539796307698"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1109\/71.481599"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1109\/71.481600"}],"container-title":["ACM Transactions on Autonomous and Adaptive Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2019591.2019592","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2019591.2019592","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T19:07:42Z","timestamp":1750273662000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2019591.2019592"}},"subtitle":["Optimal Consensus Despite Asynchrony, Crash, and Anonymity"],"short-title":[],"issued":{"date-parts":[[2011,10]]},"references-count":44,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2011,10]]}},"alternative-id":["10.1145\/2019591.2019592"],"URL":"https:\/\/doi.org\/10.1145\/2019591.2019592","relation":{},"ISSN":["1556-4665","1556-4703"],"issn-type":[{"type":"print","value":"1556-4665"},{"type":"electronic","value":"1556-4703"}],"subject":[],"published":{"date-parts":[[2011,10]]},"assertion":[{"value":"2009-11-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2010-08-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2011-10-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}