{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:38:29Z","timestamp":1787341109346,"version":"build-2736575974"},"reference-count":41,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"2","funder":[{"DOI":"10.13039\/501100000038","name":"Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"publisher","award":["2018-03899"],"award-info":[{"award-number":["2018-03899"]}],"id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100012376","name":"Universit\u00e9 du Qu\u00e9bec en Outaouais","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100012376","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2023,4,30]]},"abstract":"<jats:p>Abstract.<\/jats:p>\n                  <jats:p>A team of mobile agents with different labels, starting from different nodes of an unknown anonymous network, must meet at the same node and declare that they all met. This task of gathering was traditionally considered assuming that agents at the same node can exchange information. We ask if this ability of talking is needed. The answer turns out to be no. We design two deterministic algorithms that accomplish gathering in a much weaker model. We only assume that each agent knows how many agents are at the node that it currently occupies. Our first algorithm assumes that agents know some upper bound N on the size of the network, and works in time polynomial in N and in the length [Formula: see text] of the smallest label. Our second algorithm does not assume any knowledge about the network, but its complexity is at least exponential in the size of the network and in the labels of agents. Its purpose is to show feasibility of gathering under this harsher scenario. As a by-product we solve, in the same weak model, the fundamental problem of leader election among agents. As an application we solve the gossiping problem in this model: if each agent has a message, all agents can learn all messages. This is perhaps our most surprising finding: agents without any transmitting devices can solve the most general information exchange problem if they can count the number of agents present at visited nodes.<\/jats:p>","DOI":"10.1137\/20m1362899","type":"journal-article","created":{"date-parts":[[2023,3,21]],"date-time":"2023-03-21T09:40:50Z","timestamp":1679391650000},"page":"358-411","source":"Crossref","is-referenced-by-count":2,"title":["Want to Gather? No Need to Chatter!"],"prefix":"10.1137","volume":"52","author":[{"given":"S\u00e9bastien","family":"Bouchard","sequence":"first","affiliation":[{"name":"D\u00e9partement d\u2019informatique, Universit\u00e9 du Qu\u00e9bec en Outaouais, Gatineau, Qu\u00e9bec J8X 3X7, Canada."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yoann","family":"Dieudonn\u00e9","sequence":"additional","affiliation":[{"name":"MIS Lab., Universit\u00e9 de Picardie Jules Verne, Amiens 80039, France."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Andrzej","family":"Pelc","sequence":"additional","affiliation":[{"name":"D\u00e9partement d\u2019informatique, Universit\u00e9 du Qu\u00e9bec en Outaouais, Gatineau, Qu\u00e9bec J8X 3X7, Canada."}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2023,3,15]]},"reference":[{"key":"ref1","doi-asserted-by":"publisher","DOI":"10.1137\/050645221"},{"key":"ref2","doi-asserted-by":"publisher","DOI":"10.1137\/S0363012993249195"},{"key":"ref3","doi-asserted-by":"publisher","DOI":"10.1002\/nav.10011"},{"key":"ref4","series-title":"Int. Ser. Oper. Res. Management Sci.","volume-title":"The Theory of Search Games and Rendezvous","author":"Alpern S.","year":"2003"},{"key":"ref5","doi-asserted-by":"crossref","unstructured":"E. Anderson  and \nS. Fekete , Asymmetric rendezvous on the plane, in Proceedings of the 14th Annual ACM Symposium on Computational Geometry, 1998, pp. 365\u2013373.","DOI":"10.1145\/276884.276925"},{"key":"ref6","doi-asserted-by":"publisher","DOI":"10.1287\/opre.49.1.107.11191"},{"key":"ref7","doi-asserted-by":"crossref","unstructured":"E. Bampas , \nJ. Czyzowicz , \nL. Gasieniec , \nD. Ilcinkas , and \nA. Labourel , Almost optimal asynchronous rendezvous in infinite multidimensional grids, in Proceedings of the 24th International Symposium on Distributed Computing (DISC), Springer, 2010, pp. 297\u2013311.","DOI":"10.1007\/978-3-642-15763-9_28"},{"key":"ref8","doi-asserted-by":"publisher","DOI":"10.1137\/S0363012996314130"},{"key":"ref9","doi-asserted-by":"publisher","DOI":"10.1002\/nav.1044"},{"key":"ref10","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-016-0276-9"},{"key":"ref11","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2018.11.026"},{"key":"ref12","doi-asserted-by":"crossref","unstructured":"J. Chalopin , \nS. Das , and \nA. Kosowski , Constructing a map of an anonymous graph: Applications of universal sequences, in Proceedings of the 14th International Conference on Principles of Distributed Systems (OPODIS), Springer, 2010, pp.119\u2013134.","DOI":"10.1007\/978-3-642-17653-1_10"},{"key":"ref13","doi-asserted-by":"publisher","DOI":"10.1137\/100796534"},{"key":"ref14","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539704446475"},{"key":"ref15","doi-asserted-by":"publisher","DOI":"10.1137\/060665257"},{"key":"ref16","doi-asserted-by":"crossref","unstructured":"J. Czyzowicz , \nS. Dobrev , \nE. Kranakis , and \nD. Krizanc , The power of tokens: Rendezvous and symmetry detection for two mobile agents in a ring, in Proceedings of the 34th Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM), Springer, 2008, pp. 234\u2013246.","DOI":"10.1007\/978-3-540-77566-9_20"},{"key":"ref17","doi-asserted-by":"crossref","unstructured":"J. Czyzowicz , \nL. Gasieniec , \nR. Killick , and \nE. Kranakis , Symmetry breaking in the plane: Rendezvous by robots with unknown attributes, in Proceedings of the 38th ACM Symposium on Principles of Distributed Computing (PODC), 2019, pp. 4\u201313.","DOI":"10.1145\/3293611.3331608"},{"key":"ref18","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-011-0141-9"},{"key":"ref19","doi-asserted-by":"publisher","DOI":"10.1145\/2344422.2344427"},{"key":"ref20","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-016-0274-y"},{"key":"ref21","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.12.016"},{"key":"ref22","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-006-0074-2"},{"key":"ref23","doi-asserted-by":"crossref","unstructured":"Y. Dieudonn\u00e9 , \nS. Dolev , \nF. Petit , and \nM. Segal , Deaf, dumb, and chatting asynchronous robots, in Proceedings of the 13th International Conference on Principles of Distributed Systems (OPODIS), Springer, 2009, pp. 71\u201385.","DOI":"10.1007\/978-3-642-10877-8_8"},{"key":"ref24","doi-asserted-by":"publisher","DOI":"10.1145\/2594581"},{"key":"ref25","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-015-9982-0"},{"key":"ref26","doi-asserted-by":"publisher","DOI":"10.1137\/130931990"},{"key":"ref27","doi-asserted-by":"crossref","unstructured":"S. Dobrev , \nP. Flocchini , \nG. Prencipe , and \nN. Santoro , Mobile search for a black hole in an anonymous ring, in Proceedings of the 15th International Conference on Distributed Computing (DISC), Springer, 2001, pp. 166\u2013179.","DOI":"10.1007\/3-540-45414-4_12"},{"key":"ref28","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.01.001"},{"key":"ref29","doi-asserted-by":"publisher","DOI":"10.1287\/opre.47.6.974"},{"key":"ref30","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2007.09.032"},{"key":"ref31","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(02)00023-5"},{"key":"ref32","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2008.02.010"},{"key":"ref33","doi-asserted-by":"crossref","unstructured":"E. Kranakis , \nD. Krizanc , and \nP. Morin , Randomized rendez-vous with limited memory, in Proceedings of the 8th Latin American Theoretical Informatics (LATIN 2008), Lecture Notes in Comput. Sci. 4957, Springer, 2008, pp. 605\u2013616.","DOI":"10.1007\/978-3-540-78773-0_52"},{"key":"ref34","doi-asserted-by":"crossref","unstructured":"E. Kranakis , \nD. Krizanc , \nN. Santoro , and \nC. Sawchuk , Mobile agent rendezvous in a ring, in Proceedings of the 23rd International Conference on Distributed Computing Systems (ICDCS 2003), IEEE, pp. 592\u2013599.","DOI":"10.1109\/ICDCS.2003.1203510"},{"key":"ref35","doi-asserted-by":"publisher","DOI":"10.1137\/S036301299427816X"},{"key":"ref36","volume-title":"Distributed algorithms","author":"Lynch N. L.","year":"1996"},{"key":"ref37","doi-asserted-by":"publisher","DOI":"10.1002\/net.21453"},{"key":"ref38","doi-asserted-by":"publisher","DOI":"10.1145\/1391289.1391291"},{"key":"ref39","doi-asserted-by":"publisher","DOI":"10.1145\/2601068"},{"key":"ref40","doi-asserted-by":"publisher","DOI":"10.1057\/jors.1992.89"},{"key":"ref41","doi-asserted-by":"crossref","unstructured":"X. Yu  and \nM. Yung , Agent rendezvous: A dynamic symmetry-breaking problem, in Proceedings of the International Colloquium on Automata, Languages, and Programming, Lecture Notes in Comput. Sci. 1099, Springer, 1996, pp. 610\u2013621.","DOI":"10.1007\/3-540-61440-0_163"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/20M1362899","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:06:00Z","timestamp":1787339160000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/20M1362899"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,3,15]]},"references-count":41,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2023,4,30]]}},"alternative-id":["10.1137\/20M1362899"],"URL":"https:\/\/doi.org\/10.1137\/20m1362899","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,3,15]]}}}