{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T17:13:46Z","timestamp":1760202826737},"publisher-location":"Cham","reference-count":35,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030349912"},{"type":"electronic","value":"9783030349929"}],"license":[{"start":{"date-parts":[[2019,1,1]],"date-time":"2019-01-01T00:00:00Z","timestamp":1546300800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2019]]},"DOI":"10.1007\/978-3-030-34992-9_5","type":"book-chapter","created":{"date-parts":[[2019,11,14]],"date-time":"2019-11-14T13:02:48Z","timestamp":1573736568000},"page":"53-68","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Synchronous t-Resilient Consensus in Arbitrary Graphs"],"prefix":"10.1007","author":[{"given":"Armando","family":"Casta\u00f1eda","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pierre","family":"Fraigniaud","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ami","family":"Paz","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"}]},{"given":"Corentin","family":"Travers","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2019,11,14]]},"reference":[{"issue":"3","key":"5_CR1","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1016\/S0020-0190(99)00100-3","volume":"71","author":"MK Aguilera","year":"1999","unstructured":"Aguilera, M.K., Toueg, S.: A simple bivalency proof that t-resilient consensus requires t+1 rounds. Inf. Process. Lett. 71(3), 155\u2013158 (1999)","journal-title":"Inf. Process. Lett."},{"issue":"4","key":"5_CR2","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1016\/0020-0190(85)90056-0","volume":"21","author":"B Alpern","year":"1985","unstructured":"Alpern, B., Schneider, F.B.: Defining liveness. Inf. Process. Lett. 21(4), 181\u2013185 (1985)","journal-title":"Inf. Process. Lett."},{"issue":"1","key":"5_CR3","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1137\/16M1081439","volume":"48","author":"H Attiya","year":"2019","unstructured":"Attiya, H., Casta\u00f1eda, A., Herlihy, M., Paz, A.: Bounds on the step and namespace complexity of renaming. SIAM J. Comput. 48(1), 1\u201332 (2019)","journal-title":"SIAM J. Comput."},{"key":"5_CR4","series-title":"Wiley Series on Parallel and Distributed Computing","doi-asserted-by":"publisher","DOI":"10.1002\/0471478210","volume-title":"Distributed Computing: Fundamentals, Simulations, and Advanced Topics","author":"H Attiya","year":"2004","unstructured":"Attiya, H., Welch, J.: Distributed Computing: Fundamentals, Simulations, and Advanced Topics. Wiley Series on Parallel and Distributed Computing. Wiley, Hoboken (2004)"},{"issue":"2","key":"5_CR5","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1007\/BF02280836","volume":"7","author":"P Berman","year":"1993","unstructured":"Berman, P., Garay, J.A.: Fast consensus in networks of bounded degree. Distrib. Comput. 7(2), 67\u201373 (1993)","journal-title":"Distrib. Comput."},{"key":"5_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/978-3-030-24922-9_1","volume-title":"Structural Information and Communication Complexity","author":"A Casta\u00f1eda","year":"2019","unstructured":"Casta\u00f1eda, A., Fraigniaud, P., Paz, A., Rajsbaum, S., Roy, M., Travers, C.: A topological perspective on distributed network algorithms. In: Censor-Hillel, K., Flammini, M. (eds.) SIROCCO 2019. LNCS, vol. 11639, pp. 3\u201318. Springer, Cham (2019). \nhttps:\/\/doi.org\/10.1007\/978-3-030-24922-9_1"},{"key":"5_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1007\/978-3-662-45174-8_7","volume-title":"Distributed Computing","author":"A Casta\u00f1eda","year":"2014","unstructured":"Casta\u00f1eda, A., Gonczarowski, Y.A., Moses, Y.: Unbeatable consensus. In: Kuhn, F. (ed.) DISC 2014. LNCS, vol. 8784, pp. 91\u2013106. Springer, Heidelberg (2014). \nhttps:\/\/doi.org\/10.1007\/978-3-662-45174-8_7"},{"key":"5_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"206","DOI":"10.1007\/978-3-319-59647-1_16","volume-title":"Networked Systems","author":"A Casta\u00f1eda","year":"2017","unstructured":"Casta\u00f1eda, A., Moses, Y., Raynal, M., Roy, M.: Early decision and stopping in synchronous consensus: a predicate-based guided tour. In: El Abbadi, A., Garbinato, B. (eds.) NETYS 2017. LNCS, vol. 10299, pp. 206\u2013221. Springer, Cham (2017). \nhttps:\/\/doi.org\/10.1007\/978-3-319-59647-1_16"},{"key":"5_CR9","unstructured":"Charron-Bost, B., Moran, S.: Minmax algorithms for stabilizing consensus. CoRR, abs\/1906.09073 (2019)"},{"key":"5_CR10","doi-asserted-by":"publisher","first-page":"80","DOI":"10.1016\/j.tcs.2015.01.024","volume":"584","author":"\u00c9 Coulouma","year":"2015","unstructured":"Coulouma, \u00c9., Godard, E., Peters, J.G.: A characterization of oblivious message adversaries for which consensus is solvable. Theor. Comput. Sci. 584, 80\u201390 (2015)","journal-title":"Theor. Comput. Sci."},{"issue":"4","key":"5_CR11","doi-asserted-by":"publisher","first-page":"656","DOI":"10.1137\/0212045","volume":"12","author":"D Dolev","year":"1983","unstructured":"Dolev, D., Strong, H.: Authenticated algorithms for Byzantine agreement. SIAM J. Comput. 12(4), 656\u2013666 (1983)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"5_CR12","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. Algorithms 3(1), 14\u201330 (1982)","journal-title":"J. Algorithms"},{"key":"5_CR13","doi-asserted-by":"crossref","unstructured":"Dwork, C., Peleg, D., Pippenger, N., Upfal, E.: Fault tolerance in networks of bounded degree. In: Proceedings of the Eighteenth Annual ACM Symposium on Theory of Computing, STOC 1986, pp. 370\u2013379. ACM (1986)","DOI":"10.1145\/12130.12169"},{"issue":"2","key":"5_CR14","doi-asserted-by":"publisher","first-page":"156","DOI":"10.1016\/0890-5401(90)90014-9","volume":"88","author":"C Dwork","year":"1990","unstructured":"Dwork, C., Moses, Y.: Knowledge and common knowledge in a Byzantine environment: crash failures. Inf. Comput. 88(2), 156\u2013186 (1990)","journal-title":"Inf. Comput."},{"issue":"4","key":"5_CR15","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1016\/0020-0190(82)90033-3","volume":"14","author":"MJ Fischer","year":"1982","unstructured":"Fischer, M.J., Lynch, N.A.: A lower bound for the time to assure interactive consistency. Inf. Process. Lett. 14(4), 183\u2013186 (1982)","journal-title":"Inf. Process. Lett."},{"issue":"1","key":"5_CR16","doi-asserted-by":"publisher","first-page":"26","DOI":"10.1007\/BF01843568","volume":"1","author":"MJ Fischer","year":"1986","unstructured":"Fischer, M.J., Lynch, N.A., Merritt, M.: Easy impossibility proofs for distributed consensus problems. Distrib. Comput. 1(1), 26\u201339 (1986)","journal-title":"Distrib. Comput."},{"issue":"2","key":"5_CR17","doi-asserted-by":"publisher","first-page":"374","DOI":"10.1145\/3149.214121","volume":"32","author":"MJ Fischer","year":"1985","unstructured":"Fischer, M.J., Lynch, N.A., Paterson, M.: Impossibility of distributed consensus with one faulty process. J. ACM 32(2), 374\u2013382 (1985)","journal-title":"J. ACM"},{"key":"5_CR18","series-title":"Graduate Texts in Mathematics","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4613-0163-9","volume-title":"Algebraic Graph Theory","author":"C Godsil","year":"2001","unstructured":"Godsil, C., Royle, G.: Algebraic Graph Theory. Graduate Texts in Mathematics, vol. 207. Springer, New York (2001). \nhttps:\/\/doi.org\/10.1007\/978-1-4613-0163-9"},{"key":"5_CR19","unstructured":"Hadzilacos, V.: A lower bound for Byzantine agreement with fail-stop processors. Technical report 21\u201383, Department of Computer Science, Harvard University, Cambridge, MA, July 1983"},{"key":"5_CR20","volume-title":"Distributed Computing Through Combinatorial Topology","author":"M Herlihy","year":"2013","unstructured":"Herlihy, M., Kozlov, D., Rajsbaum, S.: Distributed Computing Through Combinatorial Topology. Morgan Kaufmann, Burlington (2013)"},{"key":"5_CR21","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1016\/j.entcs.2009.02.018","volume":"230","author":"M Herlihy","year":"2009","unstructured":"Herlihy, M., Rajsbaum, S., Tuttle, M.R.: An axiomatic approach to computing the connectivity of synchronous and asynchronous systems. Electr. Notes Theor. Comput. Sci. 230, 79\u2013102 (2009)","journal-title":"Electr. Notes Theor. Comput. Sci."},{"key":"5_CR22","doi-asserted-by":"crossref","unstructured":"Khan, M.S., Naqvi, S.S., Vaidya, N.H.: Exact Byzantine consensus on undirected graphs under local broadcast model. In: Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, PODC, pp. 327\u2013336 (2019)","DOI":"10.1145\/3293611.3331619"},{"issue":"1","key":"5_CR23","doi-asserted-by":"publisher","first-page":"82","DOI":"10.1145\/1959045.1959064","volume":"42","author":"F Kuhn","year":"2011","unstructured":"Kuhn, F., Oshman, R.: Dynamic networks: models and algorithms. SIGACT News 42(1), 82\u201396 (2011)","journal-title":"SIGACT News"},{"issue":"3","key":"5_CR24","doi-asserted-by":"publisher","first-page":"382","DOI":"10.1145\/357172.357176","volume":"4","author":"L Lamport","year":"1982","unstructured":"Lamport, L., Shostak, R., Pease, M.: The Byzantine generals problem. ACM Trans. Program. Lang. Syst. 4(3), 382\u2013401 (1982)","journal-title":"ACM Trans. Program. Lang. Syst."},{"key":"5_CR25","volume-title":"Distributed Algorithms","author":"NA Lynch","year":"1996","unstructured":"Lynch, N.A.: Distributed Algorithms. Morgan Kaufmann Publishers Inc., San Francisco (1996)"},{"issue":"4","key":"5_CR26","doi-asserted-by":"publisher","first-page":"989","DOI":"10.1137\/S0097539799364006","volume":"31","author":"Y Moses","year":"2002","unstructured":"Moses, Y., Rajsbaum, S.: A layered analysis of consensus. SIAM J. Comput. 31(4), 989\u20131021 (2002)","journal-title":"SIAM J. Comput."},{"key":"5_CR27","doi-asserted-by":"crossref","unstructured":"Nowak, T., Schmid, U., Winkler, K.: Topological characterization of consensus under general message adversaries. In: Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, PODC, pp. 218\u2013227 (2019)","DOI":"10.1145\/3293611.3331624"},{"key":"5_CR28","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898719772","volume-title":"Distributed Computing: A Locality-Sensitive Approach","author":"D Peleg","year":"2000","unstructured":"Peleg, D.: Distributed Computing: A Locality-Sensitive Approach. SIAM, Philadelphia (2000)"},{"key":"5_CR29","unstructured":"Raynal, M.: Consensus in synchronous systems: a concise guided tour. In: 9th Pacific Rim International Symposium on Dependable Computing (PRDC), pp. 221\u2013228 (2002)"},{"key":"5_CR30","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-94141-7","volume-title":"Fault-Tolerant Message-Passing Distributed Systems - An Algorithmic Approach","author":"M Raynal","year":"2018","unstructured":"Raynal, M.: Fault-Tolerant Message-Passing Distributed Systems - An Algorithmic Approach. Springer, Cham (2018)"},{"issue":"2\u20133","key":"5_CR31","doi-asserted-by":"publisher","first-page":"232","DOI":"10.1016\/j.tcs.2007.04.036","volume":"384","author":"N Santoro","year":"2007","unstructured":"Santoro, N., Widmayer, P.: Agreement in synchronous networks with ubiquitous faults. Theor. Comput. Sci. 384(2\u20133), 232\u2013249 (2007)","journal-title":"Theor. Comput. Sci."},{"key":"5_CR32","doi-asserted-by":"crossref","unstructured":"Tseng, L., Vaidya, N.H.: Fault-tolerant consensus in directed graphs. In: Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing, PODC, pp. 451\u2013460. ACM (2015)","DOI":"10.1145\/2767386.2767399"},{"issue":"3","key":"5_CR33","doi-asserted-by":"publisher","first-page":"70","DOI":"10.1145\/2993749.2993764","volume":"47","author":"L Tseng","year":"2016","unstructured":"Tseng, L., Vaidya, N.H.: A note on fault-tolerant consensus in directed networks. SIGACT News 47(3), 70\u201391 (2016)","journal-title":"SIGACT News"},{"key":"5_CR34","doi-asserted-by":"publisher","first-page":"1240","DOI":"10.1109\/PROC.1978.11114","volume":"66","author":"JH Wensley","year":"1978","unstructured":"Wensley, J.H., et al.: Sift: design and analysis of a fault-tolerant computer for aircraft control. Proc. IEEE 66, 1240\u20131255 (1978)","journal-title":"Proc. IEEE"},{"key":"5_CR35","first-page":"41","volume":"128","author":"K Winkler","year":"2019","unstructured":"Winkler, K., Schmid, U.: An overview of recent results for consensus in directed dynamic networks. Bull. Eur. Assoc. Theor. Comput. Sci. (EATCS) 128, 41\u201372 (2019)","journal-title":"Bull. Eur. Assoc. Theor. Comput. Sci. (EATCS)"}],"container-title":["Lecture Notes in Computer Science","Stabilization, Safety, and Security of Distributed Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-34992-9_5","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,11,14]],"date-time":"2019-11-14T13:32:35Z","timestamp":1573738355000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-030-34992-9_5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019]]},"ISBN":["9783030349912","9783030349929"],"references-count":35,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-34992-9_5","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2019]]},"assertion":[{"value":"14 November 2019","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"SSS","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Symposium on Stabilizing, Safety, and Security of Distributed Systems","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Pisa","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Italy","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2019","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"22 October 2019","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"25 October 2019","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"21","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"sss2019a","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/sss2019.lip6.fr\/symp\/sss2019\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"EasyChair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"45","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"21","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"7","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"47% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3.3","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"2.8","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}