{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,30]],"date-time":"2026-09-30T07:59:59Z","timestamp":1790755199335,"version":"4.1.0"},"reference-count":61,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2026,7,30]],"date-time":"2026-07-30T00:00:00Z","timestamp":1785369600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2026,7,30]],"date-time":"2026-07-30T00:00:00Z","timestamp":1785369600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"publisher","award":["730\/24"],"award-info":[{"award-number":["730\/24"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100015440","name":"Nancy and Stephen Grand Technion Energy Program","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100015440","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Distrib. Comput."],"published-print":{"date-parts":[[2026,9]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>\n                    A novel long-lived distributed problem, called\n                    <jats:italic>Team Formation (TF)<\/jats:italic>\n                    , is introduced together with a message- and time-efficient randomized algorithm. The problem is defined over the asynchronous model with a complete communication graph, using bounded size messages, where a certain fraction of the nodes may experience a generalized, strictly stronger, version of initial failures. The goal of a TF algorithm is to assemble tokens injected by the environment, in a distributed manner, into\n                    <jats:italic>teams<\/jats:italic>\n                    of size\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$\\sigma $$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mi>\u03c3<\/mml:mi>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    , where\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$\\sigma $$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mi>\u03c3<\/mml:mi>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    is a parameter of the problem. The usefulness of TF is demonstrated by using it to derive efficient algorithms for many distributed problems. Specifically, we show that various (one-shot as well as long-lived) distributed problems reduce to TF. This includes well-known (and extensively studied) distributed problems such as several versions of leader election and threshold detection. For example, we are the first to break the linear message complexity bound for asynchronous implicit leader election. We also improve the time complexity of message-optimal algorithms for asynchronous explicit leader election. Other distributed problems that reduce to TF are new ones, including matching players in online gaming platforms, a generalization of gathering, constructing a perfect matching in an induced subgraph of the complete graph, and more. To complement our positive contribution, we establish a tight lower bound on the message complexity of TF algorithms.\n                  <\/jats:p>","DOI":"10.1007\/s00446-026-00510-5","type":"journal-article","created":{"date-parts":[[2026,7,30]],"date-time":"2026-07-30T02:42:29Z","timestamp":1785379349000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Team formation and applications"],"prefix":"10.1007","volume":"39","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-3123-3451","authenticated-orcid":false,"given":"Yuval","family":"Emek","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2062-6855","authenticated-orcid":false,"given":"Shay","family":"Kutten","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4923-4660","authenticated-orcid":false,"given":"Ido","family":"Rafael","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3070-5370","authenticated-orcid":false,"given":"Gadi","family":"Taubenfeld","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2026,7,30]]},"reference":[{"issue":"1","key":"510_CR1","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/227595.227596","volume":"43","author":"Y Afek","year":"1996","unstructured":"Afek, Y., Awerbuch, B., Plotkin, S.A., Saks, M.E.: Local management of a global resource in a communication network. J. ACM 43(1), 1\u201319 (1996). https:\/\/doi.org\/10.1145\/227595.227596","journal-title":"J. ACM"},{"issue":"2","key":"510_CR2","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). https:\/\/doi.org\/10.1137\/0220023","journal-title":"SIAM J. Comput."},{"key":"510_CR3","doi-asserted-by":"publisher","unstructured":"Afek, Y., Matias, Y.: Elections in anonymous networks. Inf. Comput., 113(2):312\u2013330, (1994). URL: https:\/\/doi.org\/10.1006\/inco.1994.1075, https:\/\/doi.org\/10.1006\/INCO.1994.1075","DOI":"10.1006\/INCO.1994.1075"},{"key":"510_CR4","doi-asserted-by":"publisher","unstructured":"Afek, Y., Saks, M.E.: Detecting global termination conditions in the face of uncertainty. In Fred\u00a0B. Schneider, editor, Proceedings of the Sixth Annual ACM Symposium on Principles of Distributed Computing, Vancouver, British Columbia, Canada, August 10-12, 1987, pages 109\u2013124. ACM, (1987). https:\/\/doi.org\/10.1145\/41840.41850","DOI":"10.1145\/41840.41850"},{"issue":"1","key":"510_CR5","doi-asserted-by":"publisher","first-page":"56","DOI":"10.1137\/050645221","volume":"36","author":"N Agmon","year":"2006","unstructured":"Agmon, N., Peleg, D.: Fault-tolerant gathering algorithms for autonomous mobile robots. SIAM J. Comput. 36(1), 56\u201382 (2006). https:\/\/doi.org\/10.1137\/050645221","journal-title":"SIAM J. Comput."},{"key":"510_CR6","doi-asserted-by":"publisher","unstructured":"Angluin, D.: Local and global properties in networks of processors (extended abstract). In Raymond\u00a0E. Miller, Seymour Ginsburg, Walter\u00a0A. Burkhard, and Richard\u00a0J. Lipton, editors, Proceedings of the 12th Annual ACM Symposium on Theory of Computing, April 28-30, 1980, Los Angeles, California, USA, pages 82\u201393. ACM, (1980). https:\/\/doi.org\/10.1145\/800141.804655","DOI":"10.1145\/800141.804655"},{"key":"510_CR7","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.L.: Distributed computing - fundamentals, simulations, and advanced topics, 2nd edn. Wiley, Wiley series on parallel and distributed computing (2004)","edition":"2"},{"key":"510_CR8","doi-asserted-by":"crossref","unstructured":"Augustine, J., Molla, A.R., Pandurangan, G.: Sublinear message bounds for randomized agreement. In Calvin Newport and Idit Keidar, editors, Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing, PODC 2018, Egham, United Kingdom, July 23-27, 2018, pages 315\u2013324. ACM, (2018). URL: https:\/\/dl.acm.org\/citation.cfm?id=3212751","DOI":"10.1145\/3212734.3212751"},{"key":"510_CR9","doi-asserted-by":"publisher","unstructured":"Awerbuch, B., Cowen, L., Smith, M.A.: Efficient asynchronous distributed symmetry breaking. In Frank\u00a0Thomson Leighton and Michael\u00a0T. Goodrich, editors, Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing, 23-25 May 1994, Montr\u00e9al, Qu\u00e9bec, Canada, pages 214\u2013223. ACM, (1994) https:\/\/doi.org\/10.1145\/195058.195136","DOI":"10.1145\/195058.195136"},{"issue":"2","key":"510_CR10","doi-asserted-by":"publisher","first-page":"238","DOI":"10.1145\/77600.77618","volume":"37","author":"B Awerbuch","year":"1990","unstructured":"Awerbuch, B., Goldreich, O., Vainish, R., Peleg, D.: A trade-off between information and communication in broadcast protocols. Journal of the ACM (JACM) 37(2), 238\u2013256 (1990)","journal-title":"Journal of the ACM (JACM)"},{"key":"510_CR11","doi-asserted-by":"publisher","unstructured":"Bar-Yehuda, R., Kutten, S., Wolfstahl, Y., Zaks, S.: Making distributed spanning tree algorithms fault-resilient. In Franz-Josef Brandenburg, Guy Vidal-Naquet, and Martin Wirsing, editors, STACS 87, 4th Annual Symposium on Theoretical Aspects of Computer Science, Passau, Germany, February 19-21, 1987, Proceedings, volume 247 of Lecture Notes in Computer Science, pages 432\u2013444. Springer, (1987). URL: https:\/\/doi.org\/10.1007\/BFb0039625, https:\/\/doi.org\/10.1007\/BFB0039625","DOI":"10.1007\/BFB0039625"},{"key":"510_CR12","unstructured":"Bassler, B.: Quorum Sensing: How Bacteria Communicate. The Explorer\u2019s Guide to Biology, September (2019). 48 pages; https:\/\/explorebiology.org\/summary\/cell-biology\/quorum-sensing:-how-bacteria-communicate"},{"key":"510_CR13","doi-asserted-by":"publisher","unstructured":"Ben-Or, M.: Another advantage of free choice: Completely asynchronous agreement protocols (extended abstract). In Robert\u00a0L. Probert, Nancy\u00a0A. Lynch, and Nicola Santoro, editors, Proceedings of the Second Annual ACM Symposium on Principles of Distributed Computing, Montreal, Quebec, Canada, August 17-19, 1983, pages 27\u201330. ACM, (1983). https:\/\/doi.org\/10.1145\/800221.806707","DOI":"10.1145\/800221.806707"},{"key":"510_CR14","doi-asserted-by":"publisher","unstructured":"Bracha, G.: An asynchronou [(n-1)\/3]-resilient consensus protocol. In Tiko Kameda, Jayadev Misra, Joseph\u00a0G. Peters, and Nicola Santoro, editors, Proceedings of the Third Annual ACM Symposium on Principles of Distributed Computing, Vancouver, B. C., Canada, August 27-29, 1984, pages 154\u2013162. ACM, (1984). https:\/\/doi.org\/10.1145\/800222.806743","DOI":"10.1145\/800222.806743"},{"key":"510_CR15","doi-asserted-by":"publisher","unstructured":"Bracha, G., Toueg, S.: Resilient consensus protocols. In Robert\u00a0L. Probert, Nancy\u00a0A. Lynch, and Nicola Santoro, editors, Proceedings of the Second Annual ACM Symposium on Principles of Distributed Computing, Montreal, Quebec, Canada, August 17-19, 1983, pages 12\u201326. ACM, (1983). https:\/\/doi.org\/10.1145\/800221.806706","DOI":"10.1145\/800221.806706"},{"key":"510_CR16","doi-asserted-by":"publisher","unstructured":"Chakaravarthy, V.T., Choudhury, A.R., Garg, V.K., Sabharwal, Y.: Efficient decentralized algorithms for the distributed trigger counting problem. Theory Comput. Syst., 51(4):447\u2013473, (2012). URL: https:\/\/doi.org\/10.1007\/s00224-012-9405-4, https:\/\/doi.org\/10.1007\/S00224-012-9405-4","DOI":"10.1007\/S00224-012-9405-4"},{"key":"510_CR17","doi-asserted-by":"publisher","unstructured":"Chang, C.-C., Tsai, J.: Distributed trigger counting algorithms for arbitrary network topology. Wirel. Commun. Mob. Comput., 16(16):2463\u20132476, (2016). URL: https:\/\/doi.org\/10.1002\/wcm.2698, https:\/\/doi.org\/10.1002\/WCM.2698","DOI":"10.1002\/WCM.2698"},{"key":"510_CR18","doi-asserted-by":"publisher","unstructured":"Datar, A., N, S.M.N., Augustine, J.: Gathering of anonymous agents. In Noa Agmon, Bo\u00a0An, Alessandro Ricci, and William Yeoh, editors, Proceedings of the 2023 International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2023, London, United Kingdom, 29 May 2023 - 2 June 2023, pages 1457\u20131465. ACM, (2023). URL: https:\/\/dl.acm.org\/doi\/10.5555\/3545946.3598798, https:\/\/doi.org\/10.5555\/3545946.3598798","DOI":"10.5555\/3545946.3598798"},{"issue":"9","key":"510_CR19","doi-asserted-by":"publisher","first-page":"569","DOI":"10.1145\/365559.365617","volume":"8","author":"EW Dijkstra","year":"1965","unstructured":"Dijkstra, E.W.: Solution of a problem in concurrent programming control. Commun. ACM 8(9), 569 (1965). https:\/\/doi.org\/10.1145\/365559.365617","journal-title":"Commun. ACM"},{"key":"510_CR20","doi-asserted-by":"publisher","unstructured":"Dobrev, S., Kralovic, R., Santoro, N., Shi, W.: Black hole search in asynchronous rings using tokens. In Tiziana Calamoneri, Irene Finocchi, and Giuseppe\u00a0F. Italiano, editors, Algorithms and Complexity, 6th Italian Conference, CIAC 2006, Rome, Italy, May 29-31, 2006, Proceedings, volume 3998 of Lecture Notes in Computer Science, pages 139\u2013150. Springer, (2006). https:\/\/doi.org\/10.1007\/11758471_16","DOI":"10.1007\/11758471_16"},{"key":"510_CR21","doi-asserted-by":"publisher","unstructured":"Emek, Y., Korman, A.: Efficient threshold detection in a distributed environment: extended abstract. In Andr\u00e9a\u00a0W. Richa and Rachid Guerraoui, editors, Proceedings of the 29th Annual ACM Symposium on Principles of Distributed Computing, PODC 2010, Zurich, Switzerland, July 25-28, 2010, pages 183\u2013191. ACM, (2010). https:\/\/doi.org\/10.1145\/1835698.1835742","DOI":"10.1145\/1835698.1835742"},{"key":"510_CR22","doi-asserted-by":"publisher","unstructured":"Emek, Y., Korman, A.: New bounds for the controller problem. Distributed Comput., 24(3-4):177\u2013186, (2011). URL: https:\/\/doi.org\/10.1007\/s00446-010-0119-z, https:\/\/doi.org\/10.1007\/S00446-010-0119-Z","DOI":"10.1007\/S00446-010-0119-Z"},{"key":"510_CR23","doi-asserted-by":"publisher","unstructured":"Emek, Y., Kutten, S., Wattenhofer, R.: Online matching: haste makes waste! In Daniel Wichs and Yishay Mansour, editors, Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, Cambridge, MA, USA, June 18-21, 2016, pages 333\u2013344. ACM, (2016). https:\/\/doi.org\/10.1145\/2897518.2897557","DOI":"10.1145\/2897518.2897557"},{"issue":"2","key":"510_CR24","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). https:\/\/doi.org\/10.1145\/3149.214121","journal-title":"J. ACM"},{"key":"510_CR25","doi-asserted-by":"publisher","unstructured":"Flocchini, P., Prencipe, G., Santoro, N., Widmayer, P.: Gathering of asynchronous robots with limited visibility. Theor. Comput. Sci., 337(1-3):147\u2013168, (2005). URL: https:\/\/doi.org\/10.1016\/j.tcs.2005.01.001, https:\/\/doi.org\/10.1016\/J.TCS.2005.01.001","DOI":"10.1016\/J.TCS.2005.01.001"},{"key":"510_CR26","doi-asserted-by":"publisher","unstructured":"Fraigniaud, P., Gasieniec, L., Kowalski, D.R., Pelc, A.: Collective tree exploration. Networks, 48(3):166\u2013177, 2006. URL: https:\/\/doi.org\/10.1002\/net.20127, https:\/\/doi.org\/10.1002\/NET.20127","DOI":"10.1002\/NET.20127"},{"key":"510_CR27","doi-asserted-by":"crossref","unstructured":"Claiborne Fuqua, W., Winans, S.C., Peter Greenberg, E.: Quorum sensing in bacteria: the LuxR-LuxI family of cell density-responsive transcriptional regulators. J. Bacteriol. 176(2), 269\u2013275 (1994)","DOI":"10.1128\/jb.176.2.269-275.1994"},{"key":"510_CR28","doi-asserted-by":"publisher","unstructured":"Garg, R., Garg, V.K., Sabharwal, Y.: Scalable algorithms for global snapshots in distributed systems. In Gregory\u00a0K. Egan and Yoichi Muraoka, editors, Proceedings of the 20th Annual International Conference on Supercomputing, ICS 2006, Cairns, Queensland, Australia, June 28 - July 01, 2006, pages 269\u2013277. ACM, (2006). https:\/\/doi.org\/10.1145\/1183401.1183439","DOI":"10.1145\/1183401.1183439"},{"key":"510_CR29","doi-asserted-by":"publisher","unstructured":"Gilbert, S., Kowalski, D.R.: Distributed agreement with optimal communication complexity. In Moses Charikar, editor, Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2010, Austin, Texas, USA, January 17-19, 2010, pages 965\u2013977. SIAM, (2010). https:\/\/doi.org\/10.1137\/1.9781611973075.78","DOI":"10.1137\/1.9781611973075.78"},{"key":"510_CR30","doi-asserted-by":"publisher","unstructured":"Hart, S.: Games in extensive and strategic forms. In Handbook of Game Theory with Economic Applications, volume\u00a01, pages 19\u201340. Elsevier, (1992). URL: https:\/\/www.sciencedirect.com\/science\/article\/pii\/S1574000505800050, https:\/\/doi.org\/10.1016\/S1574-0005(05)80005-0","DOI":"10.1016\/S1574-0005(05)80005-0"},{"key":"510_CR31","doi-asserted-by":"publisher","unstructured":"Hella, L., J\u00e4rvisalo, M., Kuusisto, A., Laurinharju, J., Lempi\u00e4inen, T., Luosto, K., Suomela, J., Virtema, J.: Weak models of distributed computing, with connections to modal logic. Distributed Comput., 28(1):31\u201353, (2015). URL: https:\/\/doi.org\/10.1007\/s00446-013-0202-3, https:\/\/doi.org\/10.1007\/S00446-013-0202-3","DOI":"10.1007\/S00446-013-0202-3"},{"key":"510_CR32","doi-asserted-by":"publisher","unstructured":"Huang, L., Garofalakis, M.N., Joseph, A.D., Taft, N.: Communication-efficient tracking of distributed cumulative triggers. In 27th IEEE International Conference on Distributed Computing Systems (ICDCS 2007), June 25-29, 2007, Toronto, Ontario, Canada, page\u00a054. IEEE Computer Society, (2007). https:\/\/doi.org\/10.1109\/ICDCS.2007.93","DOI":"10.1109\/ICDCS.2007.93"},{"key":"510_CR33","volume-title":"Selecting a leader in a clique in 0 (N log N) messages","author":"PA Humblet","year":"1984","unstructured":"Humblet, P.A.: Selecting a leader in a clique in 0 (N log N) messages. Laboratory for Information and Decision Systems, Massachusetts Institute of Technology (1984)"},{"issue":"4","key":"510_CR34","doi-asserted-by":"publisher","first-page":"415","DOI":"10.1109\/32.54293","volume":"16","author":"A Itai","year":"1990","unstructured":"Itai, A., Kutten, S., Wolfstahl, Y., Zaks, S.: Optimal distributed t-resilient election in complete networks. IEEE Trans. Software Eng. 16(4), 415\u2013420 (1990). https:\/\/doi.org\/10.1109\/32.54293","journal-title":"IEEE Trans. Software Eng."},{"key":"510_CR35","doi-asserted-by":"publisher","unstructured":"Jayanti, P., Jayanti, S., Jayanti, S.: Towards an ideal queue lock. In Nandini Mukherjee and Sriram\u00a0V. Pemmaraju, editors, ICDCN 2020: 21st International Conference on Distributed Computing and Networking, Kolkata, India, January 4-7, 2020, pages 19:1\u201319:10. ACM, (2020). https:\/\/doi.org\/10.1145\/3369740.3369784","DOI":"10.1145\/3369740.3369784"},{"key":"510_CR36","doi-asserted-by":"publisher","unstructured":"Keralapura, R., Cormode, G., Ramamirtham, J.: Communication-efficient distributed monitoring of thresholded counts. In Surajit Chaudhuri, Vagelis Hristidis, and Neoklis Polyzotis, editors, Proceedings of the ACM SIGMOD International Conference on Management of Data, Chicago, Illinois, USA, June 27-29, 2006, pages 289\u2013300. ACM, (2006). https:\/\/doi.org\/10.1145\/1142473.1142507","DOI":"10.1145\/1142473.1142507"},{"key":"510_CR37","doi-asserted-by":"publisher","unstructured":"Kim, S., Fattori, G., Park, Y.: A simple and efficient distributed trigger counting algorithm based on local thresholds. ICT Express, 10(4):895\u2013901, (2024). URL: https:\/\/doi.org\/10.1016\/j.icte.2024.05.005, https:\/\/doi.org\/10.1016\/J.ICTE.2024.05.005","DOI":"10.1016\/J.ICTE.2024.05.005"},{"key":"510_CR38","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 Tiko Kameda, Jayadev Misra, Joseph\u00a0G. Peters, and Nicola Santoro, editors, Proceedings of the Third Annual ACM Symposium on Principles of Distributed Computing, Vancouver, B. C., Canada, August 27-29, 1984, pages 199\u2013207. ACM, (1984). https:\/\/doi.org\/10.1145\/800222.806747","DOI":"10.1145\/800222.806747"},{"key":"510_CR39","doi-asserted-by":"publisher","unstructured":"Korman, A., Kutten, S.: Controller and estimator for dynamic networks. In Indranil Gupta and Roger Wattenhofer, editors, Proceedings of the Twenty-Sixth Annual ACM Symposium on Principles of Distributed Computing, PODC 2007, Portland, Oregon, USA, August 12-15, 2007, pages 175\u2013184. ACM, (2007). https:\/\/doi.org\/10.1145\/1281100.1281127","DOI":"10.1145\/1281100.1281127"},{"key":"510_CR40","doi-asserted-by":"publisher","unstructured":"Kumar, M., Molla, A.R.: On the message complexity of fault-tolerant computation: Leader election and agreement. In 24th International Conference on Distributed Computing and Networking, ICDCN 2023, Kharagpur, India, January 4-7, 2023, pages 294\u2013295. ACM, (2023) https:\/\/doi.org\/10.1145\/3571306.3571424","DOI":"10.1145\/3571306.3571424"},{"key":"510_CR41","doi-asserted-by":"publisher","unstructured":"Kumar, M., Molla, A.R.: Sublinear message bounds of authenticated implicit byzantine agreement. In Proceedings of the 25th International Conference on Distributed Computing and Networking, ICDCN 2024, Chennai, India, January 4-7, 2024, pages 124\u2013133. ACM, (2024). https:\/\/doi.org\/10.1145\/3631461.3631548","DOI":"10.1145\/3631461.3631548"},{"issue":"6","key":"510_CR42","doi-asserted-by":"publisher","first-page":"299","DOI":"10.1016\/0020-0190(88)90217-7","volume":"27","author":"S Kutten","year":"1988","unstructured":"Kutten, S.: Optimal fault-tolerant distributed construction of a spanning forest. Inf. Process. Lett. 27(6), 299\u2013307 (1988). https:\/\/doi.org\/10.1016\/0020-0190(88)90217-7","journal-title":"Inf. Process. Lett."},{"key":"510_CR43","doi-asserted-by":"publisher","unstructured":"Kutten, S., Moses Jr, W.K., Pandurangan, G., Peleg, D.: Singularly near optimal leader election in asynchronous networks. In Seth Gilbert, editor, 35th International Symposium on Distributed Computing, DISC 2021, October 4-8, 2021, Freiburg, Germany (Virtual Conference), volume 209 of LIPIcs, pages 27:1\u201327:18. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, (2021). URL: https:\/\/doi.org\/10.4230\/LIPIcs.DISC.2021.27, https:\/\/doi.org\/10.4230\/LIPICS.DISC.2021.27","DOI":"10.4230\/LIPICS.DISC.2021.27"},{"key":"510_CR44","unstructured":"Kutten, S., Moses\u00a0Jr, W.K., Pandurangan, G., Peleg, D.: Singularly optimal randomized leader election. In 34th International Symposium on Distributed Computing (DISC 2020), volume 179, (2020)"},{"key":"510_CR45","doi-asserted-by":"publisher","unstructured":"Kutten, S., Pandurangan, G., Peleg, D., Robinson, P., Trehan, A.: Sublinear bounds for randomized leader election. Theor. Comput. Sci., 561:134\u2013143, (2015). URL: https:\/\/doi.org\/10.1016\/j.tcs.2014.02.009, https:\/\/doi.org\/10.1016\/J.TCS.2014.02.009","DOI":"10.1016\/J.TCS.2014.02.009"},{"key":"510_CR46","doi-asserted-by":"publisher","unstructured":"Kutten, S., Robinson, P., Tan, M.M., Zhu, X.: Improved tradeoffs for leader election. In Rotem Oshman, Alexandre Nolin, Magn\u00fas\u00a0M. Halld\u00f3rsson, and Alkida Balliu, editors, Proceedings of the 2023 ACM Symposium on Principles of Distributed Computing, PODC 2023, Orlando, FL, USA, June 19-23, 2023, pages 355\u2013365. ACM, (2023). https:\/\/doi.org\/10.1145\/3583668.3594576","DOI":"10.1145\/3583668.3594576"},{"issue":"8","key":"510_CR47","doi-asserted-by":"publisher","first-page":"453","DOI":"10.1145\/361082.361093","volume":"17","author":"L Lamport","year":"1974","unstructured":"Lamport, L.: A new solution of dijkstra\u2019s concurrent programming problem. Commun. ACM 17(8), 453\u2013455 (1974). https:\/\/doi.org\/10.1145\/361082.361093","journal-title":"Commun. ACM"},{"key":"510_CR48","doi-asserted-by":"publisher","unstructured":"Luna, G.A.D., Uehara, R., Viglietta, G., Yamauchi, Y.: Gathering on a circle with limited visibility by anonymous oblivious robots. In Hagit Attiya, editor, 34th International Symposium on Distributed Computing, DISC 2020, October 12-16, (2020), Virtual Conference, volume 179 of LIPIcs, pages 12:1\u201312:17. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, (2020). https:\/\/doi.org\/10.4230\/LIPICS.DISC.2020.12","DOI":"10.4230\/LIPICS.DISC.2020.12"},{"key":"510_CR49","volume-title":"Lynch","author":"A Nancy","year":"1996","unstructured":"Nancy, A.: Lynch. Morgan Kaufmann, Distributed Algorithms (1996)"},{"key":"510_CR50","doi-asserted-by":"crossref","unstructured":"McKinney, E.H.: Generalized birthday problem. Am. Math. Mon. 73(4), 385\u2013387 (1966)","DOI":"10.2307\/2315408"},{"key":"510_CR51","unstructured":"El Mhamdi, E.M., Guerraoui, R., Maurer, A., Tempez, V.: Exploring the borderlands of the gathering problem. Bull. EATCS, 129, URL: http:\/\/bulletin.eatcs.org\/index.php\/beatcs\/article\/view\/593\/602 (2019)"},{"key":"510_CR52","doi-asserted-by":"publisher","unstructured":"Peleg, D.: Distributed Computing: A Locality-Sensitive Approach. Society for Industrial and Applied Mathematics, (2000). URL: https:\/\/epubs.siam.org\/doi\/abs\/10.1137\/1.9780898719772, arXiv: https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/1.9780898719772, https:\/\/doi.org\/10.1137\/1.9780898719772","DOI":"10.1137\/1.9780898719772"},{"issue":"2","key":"510_CR53","doi-asserted-by":"publisher","first-page":"488","DOI":"10.1093\/beheco\/ari020","volume":"16","author":"SC Pratt","year":"2005","unstructured":"Pratt, S.C.: Quorum sensing by encounter rates in the ant Temnothorax albipennis. Behav. Ecol. 16(2), 488\u2013496 (2005)","journal-title":"Behav. Ecol."},{"key":"510_CR54","doi-asserted-by":"publisher","unstructured":"Rabin, M.O.: Randomized byzantine generals. In 24th Annual Symposium on Foundations of Computer Science, Tucson, Arizona, USA, 7-9 November 1983, pages 403\u2013409. IEEE Computer Society, (1983). https:\/\/doi.org\/10.1109\/SFCS.1983.48","DOI":"10.1109\/SFCS.1983.48"},{"key":"510_CR55","unstructured":"Red Hat Publication. Stateful vs. stateless applications. Accessed online, February 5th, 2025. URL: https:\/\/www.redhat.com\/en\/topics\/cloud-native-apps\/stateful-vs-stateless#:~:text=Stateless%20applications%20are%20generally%20more,it%20more%20difficult%20to%20scale"},{"key":"510_CR56","doi-asserted-by":"crossref","unstructured":"Seeley, T.D., Kirk Visscher, P.: Group decision making in nest-site selection by honey bees. Apidologie, 35(2):101\u201316, (2004)","DOI":"10.1051\/apido:2004004"},{"key":"510_CR57","doi-asserted-by":"publisher","unstructured":"Styer, E., Peterson, G.L.: Tight bounds for shared memory symmetric mutual exclusion problems. In Piotr Rudnicki, editor, Proceedings of the Eighth Annual ACM Symposium on Principles of Distributed Computing, Edmonton, Alberta, Canada, August 14-16, 1989, pages 177\u2013191. ACM, (1989) https:\/\/doi.org\/10.1145\/72981.72993","DOI":"10.1145\/72981.72993"},{"key":"510_CR58","doi-asserted-by":"publisher","unstructured":"Suzuki, I., Yamashita, M.: Distributed anonymous mobile robots: Formation of geometric patterns. SIAM J. Comput. 28(4), 1347\u20131363 (1999). https:\/\/doi.org\/10.1137\/S009753979628292X","DOI":"10.1137\/S009753979628292X"},{"key":"510_CR59","unstructured":"Taubenfeld, G.: Synchronization Algorithms and Concurrent Programming. Pearson \/ Prentice-Hall, ISBN 0-131-97259-6, 423 pages (2006)"},{"issue":"4","key":"510_CR60","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1007\/BF01407859","volume":"18","author":"G Taubenfeld","year":"1989","unstructured":"Taubenfeld, G., Katz, S., Moran, S.: Initial failures in distributed computations. Int. J. Parallel Program. 18(4), 255\u2013276 (1989). https:\/\/doi.org\/10.1007\/BF01407859","journal-title":"Int. J. Parallel Program."},{"key":"510_CR61","doi-asserted-by":"publisher","unstructured":"Yamashita, M., Kameda, T.: Computing on an anonymous network. In Danny Dolev, editor, Proceedings of the Seventh Annual ACM Symposium on Principles of Distributed Computing, Toronto, Ontario, Canada, August 15-17, 1988, pages 117\u2013130. ACM, (1988) https:\/\/doi.org\/10.1145\/62546.62568","DOI":"10.1145\/62546.62568"}],"container-title":["Distributed Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-026-00510-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00446-026-00510-5","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-026-00510-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,9,30]],"date-time":"2026-09-30T07:28:12Z","timestamp":1790753292000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00446-026-00510-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,7,30]]},"references-count":61,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2026,9]]}},"alternative-id":["510"],"URL":"https:\/\/doi.org\/10.1007\/s00446-026-00510-5","relation":{"has-preprint":[{"id-type":"doi","id":"10.21203\/rs.3.rs-8366122\/v1","asserted-by":"object"}]},"ISSN":["0178-2770","1432-0452"],"issn-type":[{"value":"0178-2770","type":"print"},{"value":"1432-0452","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,7,30]]},"assertion":[{"value":"15 December 2025","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 June 2026","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"30 July 2026","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"The authors declare no competing interests.","order":1,"name":"Ethics","label":"Competing interests","group":{"name":"EthicsHeading","label":"Declarations"}}],"article-number":"19"}}