{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,3]],"date-time":"2026-04-03T05:13:37Z","timestamp":1775193217748,"version":"3.50.1"},"reference-count":32,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2020,1,29]],"date-time":"2020-01-29T00:00:00Z","timestamp":1580256000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001742","name":"Israel Science Foundation","doi-asserted-by":"publisher","award":["2061\/19"],"award-info":[{"award-number":["2061\/19"]}],"id":[{"id":"10.13039\/501100001742","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2020,2,29]]},"abstract":"<jats:p>\n            The cost of communication is a substantial factor affecting the scalability of many distributed applications. Every message sent can incur a cost in storage, computation, energy, and bandwidth. Consequently, reducing the communication costs of distributed applications is highly desirable. The best way to reduce message costs is by communicating without sending any messages whatsoever. This article initiates a rigorous investigation into the use of silence in synchronous settings, in which processes can fail. We formalize sufficient conditions for information transfer using silence, as well as necessary conditions for particular cases of interest. This allows us to identify message patterns that enable communication through silence. In particular, a pattern called a\n            <jats:italic>silent choir<\/jats:italic>\n            is identified, and shown to be central to information transfer via silence in failure-prone systems. The power of the new framework is demonstrated on the\n            <jats:italic>atomic commitment<\/jats:italic>\n            problem (AC). A complete characterization of the tradeoff between message complexity and round complexity in the synchronous model with crash failures is provided, in terms of lower bounds and matching protocols. In particular, a new message-optimal AC protocol is designed using silence, in which processes decide in three rounds in the common case. This significantly improves on the best previously known message-optimal AC protocol, in which decisions were performed in \u0398(\n            <jats:italic>n<\/jats:italic>\n            ) rounds.\n          <\/jats:p>\n          <jats:p>\n            <jats:italic>And in the naked light I saw<\/jats:italic>\n          <\/jats:p>\n          <jats:p>\n            <jats:italic>Ten thousand people, maybe more<\/jats:italic>\n          <\/jats:p>\n          <jats:p>\n            <jats:italic>People talking without speaking<\/jats:italic>\n          <\/jats:p>\n          <jats:p>\u2026<\/jats:p>\n          <jats:p>\n            <jats:italic>People writing songs that voices never share<\/jats:italic>\n          <\/jats:p>\n          <jats:p>\n            <jats:italic>And no one dared<\/jats:italic>\n          <\/jats:p>\n          <jats:p>\n            <jats:italic>Disturb the sound of silence<\/jats:italic>\n          <\/jats:p>\n          <jats:p>Paul Simon, 1964<\/jats:p>","DOI":"10.1145\/3377883","type":"journal-article","created":{"date-parts":[[2020,1,29]],"date-time":"2020-01-29T11:10:47Z","timestamp":1580296247000},"page":"1-26","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["Silence"],"prefix":"10.1145","volume":"67","author":[{"given":"Guy","family":"Goren","sequence":"first","affiliation":[{"name":"The Viterbi Faculty of Electrical Engineering, Technion, Haifa, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yoram","family":"Moses","sequence":"additional","affiliation":[{"name":"The Viterbi Faculty of Electrical Engineering, Technion, Haifa, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2020,1,29]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.5555\/3271116.3271169"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01798957"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/2542181"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSE.1985.232483"},{"key":"e_1_2_1_5_1","unstructured":"Philip A. Bernstein Vassos Hadzilacos and Nathan Goodman. 1987. Concurrency Control and Recovery in Database Systems. Vol. 370. Addison-Wesley New York.  Philip A. Bernstein Vassos Hadzilacos and Nathan Goodman. 1987. Concurrency Control and Recovery in Database Systems. Vol. 370. Addison-Wesley New York."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-45174-8_7"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgor.2003.11.001"},{"key":"e_1_2_1_8_1","unstructured":"Danny Dolev. [n.d.]. Beep protocols. (Personal Communication) ([n. d.]).  Danny Dolev. [n.d.]. Beep protocols. (Personal Communication) ([n. d.])."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/7531.7533"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1137\/0212045"},{"key":"e_1_2_1_11_1","unstructured":"Arthur Conan Doyle. 1892. The Adventure of Silver Blaze. The Strand Magazine London.  Arthur Conan Doyle. 1892. The Adventure of Silver Blaze. The Strand Magazine London."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(90)90014-9"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/800221.806705"},{"key":"e_1_2_1_14_1","doi-asserted-by":"crossref","unstructured":"Ronald Fagin Joseph Y. Halpern Yoram Moses and Moshe Y. Vardi. 2003. Reasoning About Knowledge. MIT Press Cambridge MA.  Ronald Fagin Joseph Y. Halpern Yoram Moses and Moshe Y. Vardi. 2003. Reasoning About Knowledge. MIT Press Cambridge MA.","DOI":"10.7551\/mitpress\/5803.001.0001"},{"key":"e_1_2_1_15_1","volume-title":"Silence. In Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC\u201918)","author":"Goren Guy","year":"2018"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/3034786.3034799"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/28659.28672"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01187075"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01187074"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/79147.79161"},{"key":"e_1_2_1_21_1","volume-title":"Proceedings of the USENIX Annual Technical Conference. 145--158","author":"Hunt Patrick","year":"2010"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/71.862209"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/2993.2994"},{"key":"e_1_2_1_24_1","unstructured":"Leslie Lamport and Michael J. Fischer. 1982. Byzantine Generals and Transactions Commit Protocols. Technical Report Opus 62. SRI International Menlo Park CA.  Leslie Lamport and Michael J. Fischer. 1982. Byzantine Generals and Transactions Commit Protocols. Technical Report Opus 62. SRI International Menlo Park CA."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-49259-9_21"},{"key":"e_1_2_1_26_1","volume-title":"Proceedings of the USENIX Annual Technical Conference. 251--264","author":"Lev-Ari Kfir","year":"2016"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02242709"},{"key":"e_1_2_1_28_1","volume-title":"Proceedings of the 12th USENIX Symposium on Operating Systems Design and Implementation (OSDI\u201916)","author":"Liu Shengyun","year":"2016"},{"key":"e_1_2_1_29_1","volume-title":"Proceedings of the 15th Conference on Theoretical Aspects of Rationality and Knowledge (TARK\u201915)","author":"Moses Yoram","year":"2015"},{"key":"e_1_2_1_30_1","volume-title":"Bitcoin: A peer-to-peer electronic cash system (white paper). Retrieved on","author":"Nakamoto Satoshi","year":"2008"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/322186.322188"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11036-011-0317-3"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3377883","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3377883","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:38:52Z","timestamp":1750199932000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3377883"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,1,29]]},"references-count":32,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2020,2,29]]}},"alternative-id":["10.1145\/3377883"],"URL":"https:\/\/doi.org\/10.1145\/3377883","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,1,29]]},"assertion":[{"value":"2018-11-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-12-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-01-29","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}