{"id":15079,"date":"2022-06-16T20:44:05","date_gmt":"2022-06-17T00:44:05","guid":{"rendered":"https:\/\/carleton.ca\/scs\/?page_id=15079"},"modified":"2026-06-08T15:04:08","modified_gmt":"2026-06-08T19:04:08","slug":"tr-222-time-message-trade-offs-for-the-weak-unison-problem","status":"publish","type":"page","link":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1993\/tr-222-time-message-trade-offs-for-the-weak-unison-problem\/","title":{"rendered":"TR-222: Time-Message Trade-Offs for the Weak Unison Problem"},"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-222: Time-Message Trade-Offs for the Weak Unison Problem\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-1993\/\">Technical Report<\/a>&nbsp;<strong>TR-222<\/strong><br>March 1993<\/p>\n\n\n\n<h2 id=\"time-message-trade-offs-for-the-weak-unison-problem\" class=\"wp-block-heading\">Time-Message Trade-Offs for the Weak Unison Problem<\/h2>\n\n\n\n<p>Amos Israeli, Evangelos Kranakis, Danny Krizanc, Nicola Santoro<\/p>\n\n\n\n<h3 id=\"abstract\" class=\"wp-block-heading\">Abstract<\/h3>\n\n\n\n<p>A set of anonymous processors is interconnected forming a complete synchronous network with sense of direction. Weak unison is the problem where all processors want to enter the same state (in our case \u201cwakeup\u201d state) in the absence of a global start-up signal. As measure of complexity of the protocols considered we use the \u201cbits\u201d times \u201clag\u201d measure, i.e. the total number of (wakeup) messages transmitted throughout the execution of the protocol times the num\u00adber of steps which are sufficient in order for all the processors to wakeup. We study trade-offs in the complexity of such algorithms under several conditions on the behavior of the processors (oblivious, non-oblivious, balanced, etc) and provide tight upper and lower bounds on the time x #messages measure.<\/p>\n\n\n\n<p><a href=\"https:\/\/carleton.ca\/scs\/wp-content\/uploads\/sites\/260\/TR-222.pdf\">TR-222.pdf<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"<p>Carleton UniversityTechnical Report&nbsp;TR-222March 1993 Time-Message Trade-Offs for the Weak Unison Problem Amos Israeli, Evangelos Kranakis, Danny Krizanc, Nicola Santoro Abstract A set of anonymous processors is interconnected forming a complete synchronous network with sense of direction. Weak unison is the problem where all processors want to enter the same state (in our case \u201cwakeup\u201d state) [&hellip;]<\/p>\n","protected":false},"author":2,"featured_media":0,"parent":11912,"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-15079","page","type-page","status-publish","hentry"],"acf":{"cu_post_thumbnail":""},"_links":{"self":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/15079","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=15079"}],"version-history":[{"count":2,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/15079\/revisions"}],"predecessor-version":[{"id":24456,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/15079\/revisions\/24456"}],"up":[{"embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/11912"}],"wp:attachment":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/media?parent=15079"}],"wp:term":[{"taxonomy":"cu_page_type","embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/cu_page_type?post=15079"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}