{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,13]],"date-time":"2025-06-13T14:44:57Z","timestamp":1749825897989,"version":"3.37.3"},"reference-count":19,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2019,5,21]],"date-time":"2019-05-21T00:00:00Z","timestamp":1558396800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2019,5,21]],"date-time":"2019-05-21T00:00:00Z","timestamp":1558396800000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/100000143","name":"Division of Computing and Communication Foundations","doi-asserted-by":"publisher","award":["CCF-1540512","CCF-1717075"],"award-info":[{"award-number":["CCF-1540512","CCF-1717075"]}],"id":[{"id":"10.13039\/100000143","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100002790","name":"Canadian Network for Research and Innovation in Machining Technology, Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"crossref","award":["RGPIN-2018-06322"],"award-info":[{"award-number":["RGPIN-2018-06322"]}],"id":[{"id":"10.13039\/501100002790","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Distrib. Comput."],"published-print":{"date-parts":[[2020,4]]},"DOI":"10.1007\/s00446-019-00354-2","type":"journal-article","created":{"date-parts":[[2019,5,22]],"date-time":"2019-05-22T05:04:54Z","timestamp":1558501494000},"page":"189-205","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["The complexity of leader election in diameter-two networks"],"prefix":"10.1007","volume":"33","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-0479-0690","authenticated-orcid":false,"given":"Soumyottam","family":"Chatterjee","sequence":"first","affiliation":[]},{"given":"Gopal","family":"Pandurangan","sequence":"additional","affiliation":[]},{"given":"Peter","family":"Robinson","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2019,5,21]]},"reference":[{"issue":"2","key":"354_CR1","doi-asserted-by":"publisher","first-page":"376","DOI":"10.1137\/0220023","volume":"20","author":"Y Afek","year":"1991","unstructured":"Afek, Y., Gafni, E.: Time and message bounds for election in synchronous and asynchronous complete networks. SIAM J. Comput. 20(2), 376\u2013394 (1991). \nhttps:\/\/doi.org\/10.1137\/0220023","journal-title":"SIAM J. Comput."},{"key":"354_CR2","doi-asserted-by":"publisher","unstructured":"Gilbert, S., Robinson, P., Sourav, S.: Leader election in well-connected graphs. In: Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing, PODC \u201918, pp. 227\u2013236. ACM, New York, NY, USA (2018). \nhttps:\/\/doi.org\/10.1145\/3212734.3212754","DOI":"10.1145\/3212734.3212754"},{"key":"354_CR3","doi-asserted-by":"publisher","unstructured":"Gilbert, S., Robinson, P., Sourav, S.: Slow links, fast links, and the cost of gossip. In: 2018 IEEE 38th International Conference on Distributed Computing Systems, ICDCS \u201918, pp. 786\u2013796 (2018). \nhttps:\/\/doi.org\/10.1109\/ICDCS.2018.00081","DOI":"10.1109\/ICDCS.2018.00081"},{"key":"354_CR4","doi-asserted-by":"crossref","DOI":"10.21236\/ADA146581","volume-title":"Electing a Leader in a Clique in $$O(n\\log {n})$$ Messages","author":"PA Humblet","year":"1984","unstructured":"Humblet, P.A.: Electing a Leader in a Clique in $$O(n\\log {n})$$ Messages. Intern. Memo., Laboratory for Information and Decision Systems, MIT, Cambridge (1984)"},{"issue":"3","key":"354_CR5","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1007\/s00446-012-0157-9","volume":"25","author":"M Khan","year":"2012","unstructured":"Khan, M., Kuhn, F., Malkhi, D., Pandurangan, G., Talwar, K.: Efficient distributed approximation algorithms via probabilistic tree embeddings. Distrib. Comput. 25(3), 189\u2013205 (2012). \nhttps:\/\/doi.org\/10.1007\/s00446-012-0157-9","journal-title":"Distrib. Comput."},{"issue":"1","key":"354_CR6","doi-asserted-by":"publisher","first-page":"84","DOI":"10.1145\/77606.77610","volume":"12","author":"E Korach","year":"1990","unstructured":"Korach, E., Kutten, S., Moran, S.: A modular technique for the design of efficient distributed leader finding algorithms. ACM Trans. Program. Lang. Syst. (TOPLAS) 12(1), 84\u2013101 (1990). \nhttps:\/\/doi.org\/10.1145\/77606.77610","journal-title":"ACM Trans. Program. Lang. Syst. (TOPLAS)"},{"key":"354_CR7","doi-asserted-by":"publisher","unstructured":"Korach, E., Moran, S., Zaks, S.: Tight lower and upper bounds for some distributed algorithms for a complete network of processors. In: Proceedings of the Third Annual ACM Symposium on Principles of Distributed Computing, PODC \u201984, pp. 199\u2013207. ACM, New York, NY, USA (1984). \nhttps:\/\/doi.org\/10.1145\/800222.806747","DOI":"10.1145\/800222.806747"},{"issue":"2","key":"354_CR8","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1137\/0216019","volume":"16","author":"E Korach","year":"1987","unstructured":"Korach, E., Moran, S., Zaks, S.: The optimality of distributive constructions of minimum weight and degree restricted spanning trees in a complete network of processors. SIAM J. Comput. 16(2), 231\u2013236 (1987). \nhttps:\/\/doi.org\/10.1137\/0216019","journal-title":"SIAM J. Comput."},{"issue":"1","key":"354_CR9","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1016\/0304-3975(89)90103-5","volume":"64","author":"E Korach","year":"1989","unstructured":"Korach, E., Moran, S., Zaks, S.: Optimal lower bounds for some distributed algorithms for a complete network of processors. Theor. Comput. Sci. 64(1), 125\u2013132 (1989). \nhttps:\/\/doi.org\/10.1016\/0304-3975(89)90103-5","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"354_CR10","doi-asserted-by":"publisher","first-page":"7:1","DOI":"10.1145\/2699440","volume":"62","author":"S Kutten","year":"2015","unstructured":"Kutten, S., Pandurangan, G., Peleg, D., Robinson, P., Trehan, A.: On the complexity of universal leader election. J. ACM 62(1), 7:1\u20137:27 (2015). \nhttps:\/\/doi.org\/10.1145\/2699440\n\n. Invited paper from ACM PODC 2013","journal-title":"J. ACM"},{"issue":"Part B","key":"354_CR11","doi-asserted-by":"publisher","first-page":"134","DOI":"10.1016\/j.tcs.2014.02.009","volume":"561","author":"S Kutten","year":"2015","unstructured":"Kutten, S., Pandurangan, G., Peleg, D., Robinson, P., Trehan, A.: Sublinear bounds for randomized leader election. Theor. Comput. Sci. 561(Part B), 134\u2013143 (2015). \nhttps:\/\/doi.org\/10.1016\/j.tcs.2014.02.009\n\n. Special Issue on Distributed Computing and Networking","journal-title":"Theor. Comput. Sci."},{"key":"354_CR12","unstructured":"Le Lann, G.: Distributed systems\u2014towards a formal approach. In: IFIP Congress, pp. 155\u2013160 (1977)"},{"key":"354_CR13","volume-title":"Distributed Algorithms","author":"NA Lynch","year":"1996","unstructured":"Lynch, N.A.: Distributed Algorithms. Morgan Kaufmann Publishers Inc., San Francisco (1996)"},{"key":"354_CR14","volume-title":"Probability and Computing: Randomized Algorithms and Probabilistic Analysis","author":"M Mitzenmacher","year":"2017","unstructured":"Mitzenmacher, M., Upfal, E.: Probability and Computing: Randomized Algorithms and Probabilistic Analysis, 2nd edn. Cambridge University Press, Cambridge (2017)","edition":"2"},{"key":"354_CR15","doi-asserted-by":"publisher","unstructured":"Pai, S., Pandurangan, G. V., Pemmaraju, S., Riaz, T., Robinson, P.: Symmetry breaking in the congest model: Time- and message-efficient algorithms for ruling sets. In: 31st International Symposium on Distributed Computing, DISC 2017, October 16\u201320, 2017, pp. 38:1\u201338:16. Vienna, Austria (2017). \nhttps:\/\/doi.org\/10.4230\/LIPIcs.DISC.2017.38","DOI":"10.4230\/LIPIcs.DISC.2017.38"},{"issue":"1","key":"354_CR16","doi-asserted-by":"publisher","first-page":"96","DOI":"10.1016\/0743-7315(90)90074-Y","volume":"8","author":"D Peleg","year":"1990","unstructured":"Peleg, D.: Time-optimal leader election in general networks. J. Parallel Distrib. Comput. 8(1), 96\u201399 (1990). \nhttps:\/\/doi.org\/10.1016\/0743-7315(90)90074-Y","journal-title":"J. Parallel Distrib. Comput."},{"key":"354_CR17","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. Society for Industrial and Applied Mathematics, Philadelphia (2000). \nhttps:\/\/doi.org\/10.1137\/1.9780898719772"},{"key":"354_CR18","series-title":"Wiley Series on Parallel and Distributed Computing","doi-asserted-by":"publisher","DOI":"10.1002\/0470072644","volume-title":"Design and Analysis of Distributed Algorithms","author":"N Santoro","year":"2006","unstructured":"Santoro, N.: Design and Analysis of Distributed Algorithms. Wiley Series on Parallel and Distributed Computing. Wiley, New York (2006)"},{"key":"354_CR19","volume-title":"Introduction to Distributed Algorithms","author":"G Tel","year":"2001","unstructured":"Tel, G.: Introduction to Distributed Algorithms, 2nd edn. Cambridge University Press, New York (2001)","edition":"2"}],"container-title":["Distributed Computing"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-019-00354-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00446-019-00354-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-019-00354-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,5,19]],"date-time":"2020-05-19T23:08:17Z","timestamp":1589929697000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00446-019-00354-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,5,21]]},"references-count":19,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2020,4]]}},"alternative-id":["354"],"URL":"https:\/\/doi.org\/10.1007\/s00446-019-00354-2","relation":{},"ISSN":["0178-2770","1432-0452"],"issn-type":[{"type":"print","value":"0178-2770"},{"type":"electronic","value":"1432-0452"}],"subject":[],"published":{"date-parts":[[2019,5,21]]},"assertion":[{"value":"4 October 2018","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"14 May 2019","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"21 May 2019","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}