{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,11]],"date-time":"2025-09-11T19:16:15Z","timestamp":1757618175631,"version":"3.44.0"},"reference-count":31,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2025,6,10]],"date-time":"2025-06-10T00:00:00Z","timestamp":1749513600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,6,10]],"date-time":"2025-06-10T00:00:00Z","timestamp":1749513600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100000266","name":"Engineering and Physical Sciences Research Council","doi-asserted-by":"publisher","award":["UKRI155"],"award-info":[{"award-number":["UKRI155"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Distrib. Comput."],"published-print":{"date-parts":[[2025,9]]},"abstract":"Abstract<\/jats:title>\n Beeping models are models for networks of weak devices, such as sensor networks or biological networks. In these networks, nodes are allowed to communicate only via emitting beeps: unary pulses of energy. Listening nodes have only the capability of carrier sensing<\/jats:italic>: they can only distinguish between the presence or absence of a beep, but receive no other information. The noisy beeping model further assumes listening nodes may be disrupted by random noise. Despite this extremely restrictive communication model, it transpires that complex distributed tasks can still be performed by such networks. In this paper we provide an optimal procedure for simulating general message passing in the beeping and noisy beeping models. We show that a round of can be simulated in \n \n $$O(\\Delta \\log n)$$<\/jats:tex-math>\n \n \n O<\/mml:mi>\n (<\/mml:mo>\n \u0394<\/mml:mi>\n log<\/mml:mo>\n n<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula> rounds of the noisy (or noiseless) beeping model, and a round of can be simulated in \n \n $$O(\\Delta ^2\\log n)$$<\/jats:tex-math>\n \n \n O<\/mml:mi>\n (<\/mml:mo>\n \n \u0394<\/mml:mi>\n 2<\/mml:mn>\n <\/mml:msup>\n log<\/mml:mo>\n n<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula> rounds (where \n \n $$\\Delta $$<\/jats:tex-math>\n \n \u0394<\/mml:mi>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula> is the maximum degree of the network). We also prove lower bounds demonstrating that no simulation can use asymptotically fewer rounds. This allows a host of graph algorithms to be efficiently implemented in beeping models. We present several example applications, including an \n \n $$O(\\log n)$$<\/jats:tex-math>\n \n \n O<\/mml:mi>\n (<\/mml:mo>\n log<\/mml:mo>\n n<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>-round algorithm for maximal matching, which, when simulated using our method, immediately implies a near-optimal \n \n $$O(\\Delta \\log ^2 n)$$<\/jats:tex-math>\n \n \n O<\/mml:mi>\n (<\/mml:mo>\n \u0394<\/mml:mi>\n \n log<\/mml:mo>\n 2<\/mml:mn>\n <\/mml:msup>\n n<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>-round maximal matching algorithm in the noisy beeping model. A preliminary version of this paper appeared in the proceedings of the 2023 ACM Symposium on Principles of Distributed Computing (PODC) [14].<\/jats:p>","DOI":"10.1007\/s00446-025-00488-6","type":"journal-article","created":{"date-parts":[[2025,6,10]],"date-time":"2025-06-10T10:45:10Z","timestamp":1749552310000},"page":"247-260","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Optimal message-passing with noisy beeps"],"prefix":"10.1007","volume":"38","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-5646-9524","authenticated-orcid":false,"given":"Peter","family":"Davies-Peck","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,6,10]]},"reference":[{"issue":"4","key":"488_CR1","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1007\/s00446-012-0175-7","volume":"26","author":"Y Afek","year":"2013","unstructured":"Afek, Y., Alon, N., Bar-Joseph, Z., Cornejo, A., Haeupler, B., Kuhn, F.: Beeping a maximal independent set. Distrib. Comput. 26(4), 195\u2013208 (2013)","journal-title":"Distrib. Comput."},{"issue":"6014","key":"488_CR2","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1126\/science.1193210","volume":"331","author":"Y Afek","year":"2011","unstructured":"Afek, Y., Alon, N., Barad, O., Hornstein, E., Barkai, N., Bar-Joseph, Ziv: A biological solution to a fundamental distributed computing problem. Science 331(6014), 183\u2013185 (2011)","journal-title":"Science"},{"key":"488_CR3","unstructured":"Ahmadi, M., Kuhn, F., Oshman, R.: Distributed approximate maximum matching in the CONGEST model. In 32nd International Symposium on Distributed Computing (DISC 2018). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, (2018)"},{"key":"488_CR4","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2022.104925","volume":"289","author":"Y Ashkenazi","year":"2022","unstructured":"Ashkenazi, Y., Gelles, R., Leshem, A.: Noisy beeping networks. Inf. Comput. 289, 104925 (2022)","journal-title":"Inf. Comput."},{"issue":"3","key":"488_CR5","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/2903137","volume":"63","author":"L Barenboim","year":"2016","unstructured":"Barenboim, L., Elkin, M., Pettie, S., Schneider, J.: The locality of distributed symmetry breaking. J. ACM (JACM) 63(3), 1\u201345 (2016)","journal-title":"J. ACM (JACM)"},{"key":"488_CR6","doi-asserted-by":"publisher","first-page":"66","DOI":"10.1007\/978-3-030-24922-9_5","volume-title":"Structural Information and Communication Complexity","author":"J Beauquier","year":"2019","unstructured":"Beauquier, J., Burman, J., Davies, P., Dufoulon, F.: Optimal multi-cast with beeps using group testing. In: Censor-Hillel, K., Flammini, M. (eds.) Structural Information and Communication Complexity, pp. 66\u201380. Springer, New York (2019)"},{"key":"488_CR7","doi-asserted-by":"crossref","unstructured":"Beauquier, J., Burman, J., Dufoulon, F., Kutten, S.: Fast beeping protocols for deterministic mis and $$(\\Delta + 1)$$-coloring in sparse graphs. In IEEE INFOCOM 2018 - IEEE Conference on Computer Communications, pages 1754\u20131762, (2018)","DOI":"10.1109\/INFOCOM.2018.8486015"},{"key":"488_CR8","doi-asserted-by":"crossref","unstructured":"Bernstein, A., Nanongkai, D.: Distributed exact weighted all-pairs shortest paths in near-linear time. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, pages 334\u2013342, (2019)","DOI":"10.1145\/3313276.3316326"},{"key":"488_CR9","doi-asserted-by":"publisher","first-page":"32","DOI":"10.1016\/j.ic.2018.10.001","volume":"264","author":"A Casteigts","year":"2019","unstructured":"Casteigts, A., M\u00e9tivier, Y., Robson, J.M., Zemmari, A.: Design patterns in beeping algorithms: Examples, emulation, and analysis. Inf. Comput. 264, 32\u201351 (2019)","journal-title":"Inf. Comput."},{"key":"488_CR10","unstructured":"Chechik, S., Mukhtar, D.: Reachability and shortest paths in the broadcast congest model. In 33rd International Symposium on Distributed Computing (DISC 2019). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, (2019)"},{"key":"488_CR11","doi-asserted-by":"crossref","unstructured":"Cornejo, A., Kuhn, F.: Deploying wireless networks with beeps. In International Symposium on Distributed Computing, pages 148\u2013162. Springer, (2010)","DOI":"10.1007\/978-3-642-15763-9_15"},{"key":"488_CR12","doi-asserted-by":"publisher","first-page":"98","DOI":"10.1016\/j.jpdc.2019.03.020","volume":"130","author":"A Czumaj","year":"2019","unstructured":"Czumaj, A., Davies, P.: Communicating with beeps. J. Parallel Distrib. Comput. 130, 98\u2013109 (2019)","journal-title":"J. Parallel Distrib. Comput."},{"key":"488_CR13","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1016\/j.tcs.2019.02.027","volume":"792","author":"A Czumaj","year":"2019","unstructured":"Czumaj, A., Davies, P.: Leader election in multi-hop radio networks. Theoret. Comput. Sci. 792, 2\u201311 (2019)","journal-title":"Theoret. Comput. Sci."},{"key":"488_CR14","doi-asserted-by":"crossref","unstructured":"Davies, P.: Optimal message-passing with noisy beeps. In Proceedings of the 2023 ACM Symposium on Principles of Distributed Computing, pages 300\u2013309, (2023)","DOI":"10.1145\/3583668.3594594"},{"key":"488_CR15","unstructured":"Dufoulon, F., Burman, J., Beauquier, J.: Beeping a deterministic time-optimal leader election. In 32nd International Symposium on Distributed Computing (DISC 2018). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, (2018)"},{"key":"488_CR16","doi-asserted-by":"crossref","unstructured":"Dufoulon, F., Burman, J., Beauquier, J.: Can uncoordinated beeps tell stories? In Proceedings of the 39th Symposium on Principles of Distributed Computing, PODC \u201920, page 408\u2013417, New York, NY, USA, (2020). Association for Computing Machinery","DOI":"10.1145\/3382734.3405699"},{"issue":"3","key":"488_CR17","first-page":"7","volume":"18","author":"AG D\u2019yachkov","year":"1982","unstructured":"D\u2019yachkov, A.G., Rykov, V.V.: Bounds on the length of disjunctive codes. Problemy Peredachi Informatsii 18(3), 7\u201313 (1982)","journal-title":"Problemy Peredachi Informatsii"},{"issue":"1","key":"488_CR18","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1007\/s10623-016-0279-3","volume":"82","author":"A D\u2019yachkov","year":"2017","unstructured":"D\u2019yachkov, A., Vorobyev, I., Polyanskii, N., Shchukin, V.: Almost cover-free codes and designs. Des. Codes Crypt. 82(1), 231\u2013247 (2017)","journal-title":"Des. Codes Crypt."},{"key":"488_CR19","doi-asserted-by":"publisher","first-page":"212","DOI":"10.1007\/978-3-662-45174-8_15","volume-title":"Distributed Computing","author":"K-T F\u00f6rster","year":"2014","unstructured":"F\u00f6rster, K.-T., Seidel, J., Wattenhofer, R.: Deterministic leader election in multi-hop beeping networks. In: Kuhn, F. (ed.) Distributed Computing, pp. 212\u2013226. Springer, Berlin Heidelberg (2014)"},{"issue":"1","key":"488_CR20","doi-asserted-by":"publisher","first-page":"172","DOI":"10.1006\/jcta.1996.0012","volume":"73","author":"Z F\u00fcredi","year":"1996","unstructured":"F\u00fcredi, Z.: Onr-cover-free families. J. Comb. Theory, Ser. A 73(1), 172\u2013173 (1996)","journal-title":"J. Comb. Theory, Ser. A"},{"key":"488_CR21","doi-asserted-by":"crossref","unstructured":"Ghaffari, M.: An improved distributed algorithm for maximal independent set. In Proceedings of the twenty-seventh annual ACM-SIAM symposium on Discrete algorithms, pages 270\u2013277. SIAM, (2016)","DOI":"10.1137\/1.9781611974331.ch20"},{"key":"488_CR22","doi-asserted-by":"crossref","unstructured":"Ghaffari, M., Haeupler, B.: Near optimal leader election in multi-hop radio networks. In Proceedings of the twenty-fourth annual ACM-SIAM symposium on Discrete algorithms, pages 748\u2013766. SIAM, (2013)","DOI":"10.1137\/1.9781611973105.54"},{"key":"488_CR23","doi-asserted-by":"crossref","unstructured":"Halld\u00f3rsson, M.M., Kuhn, F., Maus, Y., Tonoyan, T.: Efficient randomized distributed coloring in congest. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2021, page 1180\u20131193, New York, NY, USA, (2021). Association for Computing Machinery","DOI":"10.1145\/3406325.3451089"},{"key":"488_CR24","doi-asserted-by":"crossref","unstructured":"Holzer, S., Wattenhofer, R.: Optimal distributed all pairs shortest paths and applications. In Proceedings of the 2012 ACM symposium on Principles of distributed computing, pages 355\u2013364, (2012)","DOI":"10.1145\/2332432.2332504"},{"key":"488_CR25","volume-title":"Fundamentals of Error-Correcting Codes","author":"WC Huffman","year":"2010","unstructured":"Huffman, W.C., Pless, V.: Fundamentals of Error-Correcting Codes. Cambridge university press (2010)"},{"issue":"4","key":"488_CR26","doi-asserted-by":"publisher","first-page":"363","DOI":"10.1109\/TIT.1964.1053689","volume":"10","author":"W Kautz","year":"1964","unstructured":"Kautz, W., Singleton, R.: Nonrandom binary superimposed codes. IEEE Trans. Inf. Theory 10(4), 363\u2013377 (1964)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"488_CR27","doi-asserted-by":"crossref","unstructured":"King, V., Kutten, S., Thorup, M.: Construction and impromptu repair of an mst in a distributed network with o (m) communication. In Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing, pages 71\u201380, (2015)","DOI":"10.1145\/2767386.2767405"},{"issue":"4","key":"488_CR28","doi-asserted-by":"publisher","first-page":"1036","DOI":"10.1137\/0215074","volume":"15","author":"M Luby","year":"1986","unstructured":"Luby, M.: A simple parallel algorithm for the maximal independent set problem. SIAM J. Comput. 15(4), 1036\u20131053 (1986)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"488_CR29","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1007\/PL00008932","volume":"14","author":"A Panconesi","year":"2001","unstructured":"Panconesi, A., Rizzi, R.: Some simple distributed algorithms for sparse networks. Distrib. Comput. 14(2), 97\u2013100 (2001)","journal-title":"Distrib. Comput."},{"key":"488_CR30","doi-asserted-by":"crossref","unstructured":"Rozho\u0148, V., Ghaffari, M.: Polylogarithmic-time deterministic network decomposition and distributed derandomization. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, pages 350\u2013363, (2020)","DOI":"10.1145\/3357713.3384298"},{"issue":"2","key":"488_CR31","doi-asserted-by":"publisher","first-page":"302","DOI":"10.1016\/0097-3165(94)90067-1","volume":"66","author":"M Ruszink\u00f3","year":"1994","unstructured":"Ruszink\u00f3, M.: On the upper bound of the size of the r-cover-free families. J. Comb. Theory, Ser. A 66(2), 302\u2013310 (1994)","journal-title":"J. Comb. Theory, Ser. A"}],"container-title":["Distributed Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-025-00488-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00446-025-00488-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-025-00488-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,9,6]],"date-time":"2025-09-06T19:05:08Z","timestamp":1757185508000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00446-025-00488-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,6,10]]},"references-count":31,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2025,9]]}},"alternative-id":["488"],"URL":"https:\/\/doi.org\/10.1007\/s00446-025-00488-6","relation":{},"ISSN":["0178-2770","1432-0452"],"issn-type":[{"type":"print","value":"0178-2770"},{"type":"electronic","value":"1432-0452"}],"subject":[],"published":{"date-parts":[[2025,6,10]]},"assertion":[{"value":"16 October 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"27 May 2025","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"10 June 2025","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"There are no other financial interests or conflicts of interest to disclose.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}]}}