{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,1]],"date-time":"2022-04-01T23:22:55Z","timestamp":1648855375510},"reference-count":40,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2010,4,23]],"date-time":"2010-04-23T00:00:00Z","timestamp":1271980800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/2.0"},{"start":{"date-parts":[[2010,4,23]],"date-time":"2010-04-23T00:00:00Z","timestamp":1271980800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/2.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Braz Comput Soc"],"published-print":{"date-parts":[[2010,5]]},"abstract":"Abstract<\/jats:title>\n Agents in agreement protocols play well-distinct roles. Proposers<\/jats:italic> propose values to the acceptors<\/jats:italic>, which will accept proposals and inform the learners<\/jats:italic> so they detect that an agreement has been reached. A\u00a0fourth role is that of the coordinator<\/jats:italic>, who filters the proposals from proposers to acceptors. While proposers, learners, and coordinators are easily replaced, substituting an acceptor is prohibitive. Protocols that do not employ a coordinator are less resilient to acceptor failures. Protocols that use one coordinator are more resilient to acceptor failures, at the expense of one extra communication step even in the absence of failures. Moreover, they require replacing the coordinator as soon as it fails, a reconfiguration that, although relatively inexpensive, diminishes the protocol availability. Hence, either option, i.e., one or zero coordinator, has its drawbacks. In previous works, we have presented an alternative: multicoordinated agreement protocols. Such protocols are as resilient as single-coordinated protocols but require less reconfiguration to cope with coordinator failures. In fact, most reconfiguration can be done in parallel to the execution of the protocol\u2019s normal steps. Multicoordination can be applied to several problems. In this paper we exemplify its use in solving consensus and then introduce a fast multicoordinated agreement protocol for agents organized in groups, an abstraction for fast local area networks interconnected by slower links.<\/jats:p>","DOI":"10.1007\/s13173-010-0001-7","type":"journal-article","created":{"date-parts":[[2010,5,24]],"date-time":"2010-05-24T23:51:12Z","timestamp":1274745072000},"page":"49-68","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Multicoordinated agreement for groups of agents"],"prefix":"10.1007","volume":"16","author":[{"given":"Lasaro","family":"Camargos","sequence":"first","affiliation":[]},{"given":"Rodrigo","family":"Schmidt","sequence":"additional","affiliation":[]},{"given":"Edmundo","family":"Madeira","sequence":"additional","affiliation":[]},{"given":"Fernando","family":"Pedone","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2010,4,23]]},"reference":[{"key":"1_CR1","volume-title":"Proceedings of the 12th international symposium on distributed computing, September 1998","author":"M Aguilera","year":"1998","unstructured":"Aguilera M, Chen W, Toueg S (1998) Failure detection and consensus in the crash\u2013recovery model. In: Proceedings of the 12th international symposium on distributed computing, September 1998"},{"key":"1_CR2","unstructured":"Amir Y, Danilov C, Dolev D, Kirsch J, Lane J, Nita-Rotaru C, Olsen J, Zage D. Steward: scaling Byzantine fault-tolerant replication to wide area networks. IEEE Trans Depend Secure Comput 99(2):5555"},{"key":"1_CR3","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1145\/800221.806707","volume-title":"PODC \u201983: proceedings of the second annual ACM symposium on principles of distributed computing","author":"M Ben-Or","year":"1983","unstructured":"Ben-Or M (1983) Another advantage of free choice (extended abstract): Completely asynchronous agreement protocols. In: PODC \u201983: proceedings of the second annual ACM symposium on principles of distributed computing. ACM, New York, pp\u00a027\u201330"},{"key":"1_CR4","doi-asserted-by":"publisher","first-page":"12","DOI":"10.1145\/800221.806706","volume-title":"PODC \u201983: proceedings of the second annual ACM symposium on principles of distributed computing","author":"G Bracha","year":"1983","unstructured":"Bracha G, Toueg S (1983) Resilient consensus protocols. In: PODC \u201983: proceedings of the second annual ACM symposium on principles of distributed computing. ACM, New York, pp\u00a012\u201326"},{"key":"1_CR5","series-title":"Lecture notes in computer science","doi-asserted-by":"publisher","first-page":"549","DOI":"10.1007\/11823285_57","volume-title":"Euro-Par 2006 parallel processing","author":"L Camargos","year":"2006","unstructured":"Camargos L, Madeira E, Pedone F (2006) Optimal and practical WAB-based consensus algorithms. In: Euro-Par 2006 parallel processing. Lecture notes in computer science, vol\u00a04128. Springer, Berlin, pp\u00a0549\u2013558"},{"key":"1_CR6","doi-asserted-by":"publisher","first-page":"204","DOI":"10.1109\/NCA.2006.7","volume-title":"NCA \u201906: proceedings of the fifth IEEE international symposium on network computing and applications","author":"L Camargos","year":"2006","unstructured":"Camargos L, Pedone F, Schmidt R (2006) A\u00a0primary-backup protocol for in-memory database replication. In: NCA \u201906: proceedings of the fifth IEEE international symposium on network computing and applications. IEEE Computer Society, Washington, pp\u00a0204\u2013211"},{"key":"1_CR7","unstructured":"Camargos L, Schmidt R, Pedone F (2006) Multicoordinated Paxos. Technical Report 2006\/2, EPFL and University of Lugano, 2006"},{"key":"1_CR8","doi-asserted-by":"publisher","first-page":"316","DOI":"10.1145\/1281100.1281150","volume-title":"PODC \u201907: proceedings of the twenty-sixth annual ACM symposium on principles of distributed computing","author":"L Camargos","year":"2007","unstructured":"Camargos L, Schmidt R, Pedone F (2007) Multicoordinated Paxos: brief announcement. In: PODC \u201907: proceedings of the twenty-sixth annual ACM symposium on principles of distributed computing. ACM, New York, pp\u00a0316\u2013317"},{"key":"1_CR9","volume-title":"NCA \u201908: proceedings of the seventh IEEE international symposium on network computing and applications","author":"L Camargos","year":"2008","unstructured":"Camargos L, Schmidt R, Pedone F (2008) Multicoordinated agreement protocols for higher availability. In: NCA \u201908: proceedings of the seventh IEEE international symposium on network computing and applications. IEEE Computer Society, Washington"},{"key":"1_CR10","first-page":"173","volume-title":"OSDI \u201999: proceedings of the third symposium on operating systems design and implementation","author":"M Castro","year":"1999","unstructured":"Castro M, Liskov B (1999) Practical Byzantine fault tolerance. In: OSDI \u201999: proceedings of the third symposium on operating systems design and implementation. USENIX Association, Berkeley, pp\u00a0173\u2013186"},{"issue":"4","key":"1_CR11","doi-asserted-by":"publisher","first-page":"685","DOI":"10.1145\/234533.234549","volume":"43","author":"TD Chandra","year":"1996","unstructured":"Chandra TD, Hadzilacos V, Toueg S (1996) The weakest failure detector for solving consensus. J ACM 43(4):685\u2013722","journal-title":"J ACM"},{"issue":"2","key":"1_CR12","first-page":"225","volume":"43","author":"TD Chandra","year":"1996","unstructured":"Chandra TD, Toueg S (1996) Unreliable failure detectors for reliable distributed systems. Commun ACM 43(2):225\u2013267","journal-title":"Commun ACM"},{"issue":"6","key":"1_CR13","doi-asserted-by":"publisher","first-page":"642","DOI":"10.1109\/71.774912","volume":"10","author":"F Cristian","year":"1999","unstructured":"Cristian F, Fetzer C (1999) The timed asynchronous distributed system model. IEEE Trans Parallel Distrib Syst 10(6):642\u2013657","journal-title":"IEEE Trans Parallel Distrib Syst"},{"issue":"1","key":"1_CR14","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1145\/7531.7533","volume":"34","author":"D Dolev","year":"1987","unstructured":"Dolev D, Dwork C, Stockmeyer L (1987) On the minimal synchronism needed for distributed consensus. J ACM 34(1):77\u201397","journal-title":"J ACM"},{"key":"1_CR15","volume-title":"Lecture notes in computer science","author":"P Dutta","year":"2002","unstructured":"Dutta P, Guerraoui R (2002) Fast indulgent consensus with zero degradation. In: Lecture notes in computer science, vol\u00a02485. Springer, Berlin"},{"issue":"2","key":"1_CR16","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 (1988) Consensus in the presence of partial synchrony. J\u00a0ACM 35(2):288\u2013323","journal-title":"J\u00a0ACM"},{"issue":"2","key":"1_CR17","doi-asserted-by":"publisher","first-page":"374","DOI":"10.1145\/3149.214121","volume":"32","author":"M Fischer","year":"1985","unstructured":"Fischer M, Lynch N, Paterson M (1985) Impossibility of distributed consensus with one faulty process. J\u00a0ACM 32(2):374\u2013382","journal-title":"J\u00a0ACM"},{"key":"1_CR18","doi-asserted-by":"publisher","first-page":"280","DOI":"10.1109\/RELDIS.1998.740510","volume-title":"Proceedings seventeenth IEEE symposium on reliable distributed systems","author":"M Hurfin","year":"1998","unstructured":"Hurfin M, Mostefaoui A, Raynal M (1998) Consensus in asynchronous systems where processes can crash and recover. In: Proceedings seventeenth IEEE symposium on reliable distributed systems. IEEE Computer Society, Los Alamitos, pp\u00a0280\u2013286"},{"issue":"4","key":"1_CR19","doi-asserted-by":"publisher","first-page":"395","DOI":"10.1109\/12.995450","volume":"51","author":"M Hurfin","year":"2002","unstructured":"Hurfin M, Most\u00e9faoui A, Raynal M (2002) A\u00a0versatile family of consensus protocols based on Chandra\u2013Toueg\u2019s unreliable failure detectors. IEEE Trans Comput 51(4):395\u2013408","journal-title":"IEEE Trans Comput"},{"issue":"4","key":"1_CR20","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1007\/s004460050067","volume":"12","author":"M Hurfin","year":"1999","unstructured":"Hurfin M, Raynal M (1999) A\u00a0simple and fast asynchronous consensus protocol based on a weak failure detector. Distrib Comput 12(4):209\u2013223","journal-title":"Distrib Comput"},{"key":"1_CR21","volume-title":"Proceedings of the 12th international conference on parallel and distributed computing systems","author":"N Kooh","year":"1999","unstructured":"Kooh N, Haddad S (1999) Reaching agreement in hierarchical groups. In: Proceedings of the 12th international conference on parallel and distributed computing systems. IASTED Press, Fort Lauderdale"},{"issue":"7","key":"1_CR22","doi-asserted-by":"publisher","first-page":"558","DOI":"10.1145\/359545.359563","volume":"21","author":"L Lamport","year":"1978","unstructured":"Lamport L (1978) Time, clocks, and the ordering of events in a distributed system. Commun ACM 21(7):558\u2013565","journal-title":"Commun ACM"},{"issue":"2","key":"1_CR23","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1145\/279227.279229","volume":"16","author":"L Lamport","year":"1998","unstructured":"Lamport L (1998) The part-time parliament. ACM Trans Comput Syst 16(2):133\u2013169","journal-title":"ACM Trans Comput Syst"},{"issue":"4","key":"1_CR24","first-page":"18","volume":"32","author":"L Lamport","year":"2001","unstructured":"Lamport L (2001) Paxos made simple. ACM SIGACT News 32(4):18\u201325","journal-title":"ACM SIGACT News"},{"key":"1_CR25","unstructured":"Lamport L (2004) Generalized consensus and Paxos. Technical Report MSR-TR-2005-33, Microsoft Research"},{"issue":"2","key":"1_CR26","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1007\/s00446-006-0005-x","volume":"19","author":"L Lamport","year":"2006","unstructured":"Lamport L (2006) Fast Paxos. Distrib Comput 19(2):79\u2013103","journal-title":"Distrib Comput"},{"issue":"2","key":"1_CR27","doi-asserted-by":"publisher","first-page":"104","DOI":"10.1007\/s00446-006-0155-x","volume":"19","author":"L Lamport","year":"2006","unstructured":"Lamport L (2006) Lower bounds for asynchronous consensus. Distrib Comput 19(2):104\u2013125","journal-title":"Distrib Comput"},{"key":"1_CR28","volume-title":"PODC \u201901: Proceedings of the twentieth annual ACM symposium on principles of distributed computing","author":"B Lampson","year":"2001","unstructured":"Lampson B (2001) The abcd\u2019s of Paxos. In: PODC \u201901: Proceedings of the twentieth annual ACM symposium on principles of distributed computing. ACM, New York"},{"issue":"3","key":"1_CR29","doi-asserted-by":"publisher","first-page":"202","DOI":"10.1109\/TDSC.2006.35","volume":"3","author":"JP Martin","year":"2006","unstructured":"Martin JP, Alvisi L (2006) Fast Byzantine consensus. IEEE Trans Dependable Secure Comput 3(3):202\u2013215","journal-title":"IEEE Trans Dependable Secure Comput"},{"issue":"1","key":"1_CR30","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1023\/A:1022887812188","volume":"14","author":"F Pedone","year":"2003","unstructured":"Pedone F, Guerraoui R, Schiper A (2003) The database state machine approach. Distrib Parallel Databases 14(1):71\u201398","journal-title":"Distrib Parallel Databases"},{"key":"1_CR31","doi-asserted-by":"crossref","unstructured":"Pedone F, Schiper A (1999) Generic broadcast. In: Proceedings of the 13th international symposium on distributed computing (DISC\u201999, formerly WDAG)","DOI":"10.1007\/3-540-48169-9_7"},{"issue":"2","key":"1_CR32","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1007\/s004460100061","volume":"15","author":"F Pedone","year":"2002","unstructured":"Pedone F, Schiper A (2002) Handling message semantics with generic broadcast protocols. Distrib Comput 15(2):97\u2013107","journal-title":"Distrib Comput"},{"key":"1_CR33","first-page":"44","volume-title":"EDCC-4: proceedings of the 4th European dependable computing conference on dependable computing","author":"F Pedone","year":"2002","unstructured":"Pedone F, Schiper A, Urb\u00e1n P, Cavin D (2002) Solving agreement problems with weak ordering oracles. In: EDCC-4: proceedings of the 4th European dependable computing conference on dependable computing. Springer, London, pp\u00a044\u201361"},{"key":"1_CR34","unstructured":"Pedone F, Schiper A, Urb\u00e1n P, Cavin D (2002) Weak ordering oracles for failure detection-free systems. In: Proceedings of the international conference on dependable systems and networks (DSN), supplemental volume"},{"key":"1_CR35","doi-asserted-by":"crossref","unstructured":"Rabin MO (1983) Randomized Byzantine generals. In: Proceedings of the 24th annual IEEE symposium on foundations of computer science, pp\u00a0403\u2013409","DOI":"10.1109\/SFCS.1983.48"},{"issue":"3","key":"1_CR36","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1007\/s004460050032","volume":"10","author":"A Schiper","year":"1997","unstructured":"Schiper A (1997) Early consensus in an asynchronous system with a weak failure detector. Distrib Comput 10(3):149\u2013157","journal-title":"Distrib Comput"},{"key":"1_CR37","unstructured":"Schmidt R, Camargos L, Pedone F (2007) On collision-fast atomic broadcast. Technical report, EPFL"},{"key":"1_CR38","first-page":"190","volume-title":"Proceedings of the 21st IEEE symposium on reliable distributed systems","author":"A Sousa","year":"2002","unstructured":"Sousa A, Pereira J, Moura F, Oliveira R (2002) Optimistic total order in wide area networks. In: Proceedings of the 21st IEEE symposium on reliable distributed systems. IEEE Computer Society, New York, pp\u00a0190\u2013199"},{"key":"1_CR39","first-page":"92","volume-title":"Proceedings of the 21st symposium on reliable distributed systems","author":"P Vicente","year":"2002","unstructured":"Vicente P, Rodrigues L (2002) An indulgent uniform total order algorithm with optimistic delivery. In: Proceedings of the 21st symposium on reliable distributed systems, Osaka University, Suita, Japan. IEEE, New York, pp\u00a092\u2013101"},{"key":"1_CR40","unstructured":"Zielinski P (2004) Paxos at war. Technical Report UCAM-CL-TR-593, University of Cambridge, Computer Laboratory"}],"container-title":["Journal of the Brazilian Computer Society"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s13173-010-0001-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s13173-010-0001-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s13173-010-0001-7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s13173-010-0001-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,8,31]],"date-time":"2021-08-31T20:57:19Z","timestamp":1630443439000},"score":1,"resource":{"primary":{"URL":"https:\/\/journal-bcs.springeropen.com\/articles\/10.1007\/s13173-010-0001-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,4,23]]},"references-count":40,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2010,5]]}},"alternative-id":["1"],"URL":"https:\/\/doi.org\/10.1007\/s13173-010-0001-7","relation":{},"ISSN":["0104-6500","1678-4804"],"issn-type":[{"value":"0104-6500","type":"print"},{"value":"1678-4804","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,4,23]]},"assertion":[{"value":"30 July 2009","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"1 March 2010","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"23 April 2010","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}