{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,22]],"date-time":"2026-08-22T08:00:42Z","timestamp":1787385642910,"version":"build-2736575974"},"reference-count":14,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[1993,4]]},"abstract":"<jats:p>Consider a bidirectional ring of n identical processors that communicate asynchronously. The processors have no identifiers, and hence the ring is called anonymous. Each processor receives an input letter, and the ring is to compute a function of the circular input string. If the function value is constant for all input strings, then the processors do not need to send any messages. On the other hand, it is proven that any deterministic algorithm that computes any nonconstant function for anonymous rings requires $\\Omega (n\\log n)$ bits of communication for some input string. Also exhibited are nonconstant functions that require $O(n\\log n)$ bits of communication for every input string. The same gap for the bit complexity of nonconstant functions remains even if the processors have distinct identifiers, provided that the identifiers are taken from a large enough domain.<\/jats:p>\n                  <jats:p>When the communication is measured in messages rather than bits, the results change. A nonconstant function that can be computed with $O(n\\log ^ * n)$ messages on an anonymous ring is presented.<\/jats:p>","DOI":"10.1137\/0222028","type":"journal-article","created":{"date-parts":[[2005,2,24]],"date-time":"2005-02-24T06:38:56Z","timestamp":1109227136000},"page":"379-394","source":"Crossref","is-referenced-by-count":12,"title":["Gap Theorems for Distributed Computation"],"prefix":"10.1137","volume":"22","author":[{"given":"Shlomo","family":"Moran","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Manfred K.","family":"Warmuth","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,31]]},"reference":[{"key":"R1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01784021"},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1145\/48014.48247"},{"key":"R3","first-page":"758","volume":"49","author":"de Bruijn N. G.","year":"1946","journal-title":"Nederl. Akad. Wetensch., Proc."},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0028993"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1994.1002"},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(82)90023-2"},{"key":"R7","doi-asserted-by":"crossref","unstructured":"P. Duris, Z. Galil,  Two Lower Bounds in Asynchronous Distributed Computation,  Proceedings of IEEE Conference on Foundations in Computer Science, IEEE Press, New York,  1987,  326\u2013330","DOI":"10.1109\/SFCS.1987.60"},{"key":"R8","volume-title":"Graph algorithms","author":"Even Shimon","year":"1979"},{"key":"R9","doi-asserted-by":"crossref","unstructured":"M. J. Fischer, N. A. Lunch, M. Merritt,  Easy impossibility proofs for distributed consensus problems,  Proceedings of the Fourth Annual ACM Symposium on Principles of Distributed Computation, Minaki, Ontario, Canada,  1985,  59\u201370, August","DOI":"10.1145\/323596.323602"},{"key":"R10","doi-asserted-by":"publisher","DOI":"10.1145\/321450.321464"},{"key":"R11","doi-asserted-by":"crossref","unstructured":"S. Moran, M. K. Warmuth,  Gap theorems for distributed computation,  Proceedings of the Fifth Annual ACM Symposium on Principles of Distributed Computing, Calgary, Alberta, Canada,  1986,  131\u2013140","DOI":"10.1145\/10590.10602"},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(87)90056-3"},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1145\/69622.357194"},{"key":"R14","first-page":"33","volume":"3","author":"Trachtenbrot B. A.","year":"1964","journal-title":"Algebra i Logika Sem."}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/0222028","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:51:06Z","timestamp":1787338266000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/0222028"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1993,4]]},"references-count":14,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1993,4]]}},"alternative-id":["10.1137\/0222028"],"URL":"https:\/\/doi.org\/10.1137\/0222028","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[1993,4]]}}}