{"id":15002,"date":"2022-06-16T19:42:00","date_gmt":"2022-06-16T23:42:00","guid":{"rendered":"https:\/\/carleton.ca\/scs\/?page_id=15002"},"modified":"2026-06-09T10:07:23","modified_gmt":"2026-06-09T14:07:23","slug":"tr-195-the-expressiveness-of-silence-optimal-algorithms-for-synchronous-communication-of-information","status":"publish","type":"page","link":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1991\/tr-195-the-expressiveness-of-silence-optimal-algorithms-for-synchronous-communication-of-information\/","title":{"rendered":"TR-195: The Expressiveness of Silence: Optimal Algorithms for Synchronous Communication of Information"},"content":{"rendered":"\n<section class=\"w-screen px-6 cu-section cu-section--white ml-offset-center md:px-8 lg:px-14\">\n    <div class=\"space-y-6 cu-max-w-child-5xl  md:space-y-10 cu-prose-first-last\">\n\n            <div class=\"cu-textmedia flex flex-col lg:flex-row mx-auto gap-6 md:gap-10 my-6 md:my-12 first:mt-0 max-w-5xl\">\n        <div class=\"justify-start cu-textmedia-content cu-prose-first-last\" style=\"flex: 0 0 100%;\">\n            <header class=\"font-light prose-xl cu-pageheader md:prose-2xl cu-component-updated cu-prose-first-last\">\n                                    <h1 class=\"cu-prose-first-last font-semibold !mt-2 mb-4 md:mb-6 relative after:absolute after:h-px after:bottom-0 after:bg-cu-red after:left-px text-3xl md:text-4xl lg:text-5xl lg:leading-[3.5rem] pb-5 after:w-10 text-cu-black-700 not-prose\">\n                        TR-195: The Expressiveness of Silence: Optimal Algorithms for Synchronous Communication of Information\n                    <\/h1>\n                \n                                \n                            <\/header>\n\n                    <\/div>\n\n            <\/div>\n\n    <\/div>\n<\/section>\n\n\n\n<p>Carleton University<br><a href=\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1991\/\">Technical Report<\/a>&nbsp;<strong>TR-195<\/strong><br>October 1991<\/p>\n\n\n\n<h2 id=\"the-expressiveness-of-silence-optimal-algorithms-for-synchronous-communication-of-information\" class=\"wp-block-heading\">The Expressiveness of Silence: Optimal Algorithms for Synchronous Communication of Information<\/h2>\n\n\n\n<p>Una-May O\u2019Reilly &amp; Nicola Santoro<\/p>\n\n\n\n<h3 id=\"abstract\" class=\"wp-block-heading\">Abstract<\/h3>\n\n\n\n<p>We establish a lower bound on the trade-off between time and bit complexity for two-party communication in synchronous networks. We prove that the bound is tight by presenting a protocol whose bit-time complexity matches the one expressed by the lower bound. The proposed algorithm is globally optimal (i.e., not only in the average and worst case). Similar results are derived when transmissions are subject to corruptions. Applications of the results to transforming an asynchronous distributed algorithm into a synchronous one are discussed.<\/p>\n\n\n\n<p><a href=\"https:\/\/carleton.ca\/scs\/wp-content\/uploads\/sites\/260\/TR-195.pdf\">TR-195.pdf<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"<p>Carleton UniversityTechnical Report&nbsp;TR-195October 1991 The Expressiveness of Silence: Optimal Algorithms for Synchronous Communication of Information Una-May O\u2019Reilly &amp; Nicola Santoro Abstract We establish a lower bound on the trade-off between time and bit complexity for two-party communication in synchronous networks. We prove that the bound is tight by presenting a protocol whose bit-time complexity matches [&hellip;]<\/p>\n","protected":false},"author":2,"featured_media":0,"parent":11908,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"_acf_changed":false,"_cu_dining_location_slug":"","footnotes":"","_links_to":"","_links_to_target":""},"cu_page_type":[],"class_list":["post-15002","page","type-page","status-publish","hentry"],"acf":{"cu_post_thumbnail":""},"_links":{"self":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/15002","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/comments?post=15002"}],"version-history":[{"count":2,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/15002\/revisions"}],"predecessor-version":[{"id":24515,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/15002\/revisions\/24515"}],"up":[{"embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/11908"}],"wp:attachment":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/media?parent=15002"}],"wp:term":[{"taxonomy":"cu_page_type","embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/cu_page_type?post=15002"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}