{"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":"2022-06-16T19:42:00","modified_gmt":"2022-06-16T23:42:00","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":"<p>Carleton University<br \/>\n<a href=\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1991\/\">Technical Report<\/a> <strong>TR-195<\/strong><br \/>\nOctober 1991<\/p>\n<h2 class=\"tr_t1\">The Expressiveness of Silence: Optimal Algorithms for Synchronous Communication of Information<\/h2>\n<div class=\"tr_t3\">Una-May O&#8217;Reilly &amp; Nicola Santoro<\/div>\n<div>\n<h3>Abstract<\/h3>\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<\/div>\n<p><a href=\"https:\/\/carleton.ca\/scs\/wp-content\/uploads\/TR-195.pdf\">TR-195.pdf<\/a><\/p>\n<p><script src=\"moz-extension:\/\/c5a13a0c-07c2-4cc2-a1b8-4c3d783074b0\/js\/app.js\" type=\"text\/javascript\"><\/script><\/p>\n","protected":false},"excerpt":{"rendered":"<p>Carleton University Technical Report TR-195 October 1991 The Expressiveness of Silence: Optimal Algorithms for Synchronous Communication of Information Una-May O&#8217;Reilly &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 [&hellip;]<\/p>\n","protected":false},"author":49,"featured_media":0,"parent":11908,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"_relevanssi_hide_post":"","_relevanssi_hide_content":"","_relevanssi_pin_for_all":"","_relevanssi_pin_keywords":"","_relevanssi_unpin_keywords":"","_relevanssi_related_keywords":"","_relevanssi_related_include_ids":"","_relevanssi_related_exclude_ids":"","_relevanssi_related_no_append":"","_relevanssi_related_not_related":"","_relevanssi_related_posts":"","_relevanssi_noindex_reason":"","_mi_skip_tracking":false,"_exactmetrics_sitenote_active":false,"_exactmetrics_sitenote_note":"","_exactmetrics_sitenote_category":0,"footnotes":"","_links_to":"","_links_to_target":""},"yoast_head":"<!-- This site is optimized with the Yoast SEO plugin v21.2 - https:\/\/yoast.com\/wordpress\/plugins\/seo\/ -->\n<title>TR-195: The Expressiveness of Silence: Optimal Algorithms for Synchronous Communication of Information - School of Computer Science<\/title>\n<meta name=\"description\" content=\"Carleton University Technical Report TR-195 October 1991 The Expressiveness of Silence: Optimal Algorithms for Synchronous Communication of Information\" \/>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1991\/tr-195-the-expressiveness-of-silence-optimal-algorithms-for-synchronous-communication-of-information\/\" \/>\n<meta name=\"twitter:label1\" content=\"Est. reading time\" \/>\n\t<meta name=\"twitter:data1\" content=\"1 minute\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\/\/schema.org\",\"@graph\":[{\"@type\":\"WebPage\",\"@id\":\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1991\/tr-195-the-expressiveness-of-silence-optimal-algorithms-for-synchronous-communication-of-information\/\",\"url\":\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1991\/tr-195-the-expressiveness-of-silence-optimal-algorithms-for-synchronous-communication-of-information\/\",\"name\":\"TR-195: The Expressiveness of Silence: Optimal Algorithms for Synchronous Communication of Information - School of Computer Science\",\"isPartOf\":{\"@id\":\"https:\/\/carleton.ca\/scs\/#website\"},\"datePublished\":\"2022-06-16T23:42:00+00:00\",\"dateModified\":\"2022-06-16T23:42:00+00:00\",\"description\":\"Carleton University Technical Report TR-195 October 1991 The Expressiveness of Silence: Optimal Algorithms for Synchronous Communication of Information\",\"breadcrumb\":{\"@id\":\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1991\/tr-195-the-expressiveness-of-silence-optimal-algorithms-for-synchronous-communication-of-information\/#breadcrumb\"},\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1991\/tr-195-the-expressiveness-of-silence-optimal-algorithms-for-synchronous-communication-of-information\/\"]}]},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1991\/tr-195-the-expressiveness-of-silence-optimal-algorithms-for-synchronous-communication-of-information\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"Home\",\"item\":\"https:\/\/carleton.ca\/scs\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"Research\",\"item\":\"https:\/\/carleton.ca\/scs\/research\/\"},{\"@type\":\"ListItem\",\"position\":3,\"name\":\"SCS Technical Reports\",\"item\":\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/\"},{\"@type\":\"ListItem\",\"position\":4,\"name\":\"Technical Reports 1991\",\"item\":\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1991\/\"},{\"@type\":\"ListItem\",\"position\":5,\"name\":\"TR-195: The Expressiveness of Silence: Optimal Algorithms for Synchronous Communication of Information\"}]},{\"@type\":\"WebSite\",\"@id\":\"https:\/\/carleton.ca\/scs\/#website\",\"url\":\"https:\/\/carleton.ca\/scs\/\",\"name\":\"School of Computer Science\",\"description\":\"Carleton University\",\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":{\"@type\":\"EntryPoint\",\"urlTemplate\":\"https:\/\/carleton.ca\/scs\/?s={search_term_string}\"},\"query-input\":\"required name=search_term_string\"}],\"inLanguage\":\"en-US\"}]}<\/script>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"TR-195: The Expressiveness of Silence: Optimal Algorithms for Synchronous Communication of Information - School of Computer Science","description":"Carleton University Technical Report TR-195 October 1991 The Expressiveness of Silence: Optimal Algorithms for Synchronous Communication of Information","robots":{"index":"index","follow":"follow","max-snippet":"max-snippet:-1","max-image-preview":"max-image-preview:large","max-video-preview":"max-video-preview:-1"},"canonical":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1991\/tr-195-the-expressiveness-of-silence-optimal-algorithms-for-synchronous-communication-of-information\/","twitter_misc":{"Est. reading time":"1 minute"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"WebPage","@id":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1991\/tr-195-the-expressiveness-of-silence-optimal-algorithms-for-synchronous-communication-of-information\/","url":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1991\/tr-195-the-expressiveness-of-silence-optimal-algorithms-for-synchronous-communication-of-information\/","name":"TR-195: The Expressiveness of Silence: Optimal Algorithms for Synchronous Communication of Information - School of Computer Science","isPartOf":{"@id":"https:\/\/carleton.ca\/scs\/#website"},"datePublished":"2022-06-16T23:42:00+00:00","dateModified":"2022-06-16T23:42:00+00:00","description":"Carleton University Technical Report TR-195 October 1991 The Expressiveness of Silence: Optimal Algorithms for Synchronous Communication of Information","breadcrumb":{"@id":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1991\/tr-195-the-expressiveness-of-silence-optimal-algorithms-for-synchronous-communication-of-information\/#breadcrumb"},"inLanguage":"en-US","potentialAction":[{"@type":"ReadAction","target":["https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1991\/tr-195-the-expressiveness-of-silence-optimal-algorithms-for-synchronous-communication-of-information\/"]}]},{"@type":"BreadcrumbList","@id":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1991\/tr-195-the-expressiveness-of-silence-optimal-algorithms-for-synchronous-communication-of-information\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"Home","item":"https:\/\/carleton.ca\/scs\/"},{"@type":"ListItem","position":2,"name":"Research","item":"https:\/\/carleton.ca\/scs\/research\/"},{"@type":"ListItem","position":3,"name":"SCS Technical Reports","item":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/"},{"@type":"ListItem","position":4,"name":"Technical Reports 1991","item":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1991\/"},{"@type":"ListItem","position":5,"name":"TR-195: The Expressiveness of Silence: Optimal Algorithms for Synchronous Communication of Information"}]},{"@type":"WebSite","@id":"https:\/\/carleton.ca\/scs\/#website","url":"https:\/\/carleton.ca\/scs\/","name":"School of Computer Science","description":"Carleton University","potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/carleton.ca\/scs\/?s={search_term_string}"},"query-input":"required name=search_term_string"}],"inLanguage":"en-US"}]}},"acf":{"banner_button":"no","banner_image_type":"none"},"_links":{"self":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/15002"}],"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\/49"}],"replies":[{"embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/comments?post=15002"}],"version-history":[{"count":1,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/15002\/revisions"}],"predecessor-version":[{"id":15003,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/15002\/revisions\/15003"}],"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"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}