{"id":12888,"date":"2021-11-23T19:57:49","date_gmt":"2021-11-24T00:57:49","guid":{"rendered":"https:\/\/carleton.ca\/scs\/?page_id=12888"},"modified":"2021-11-23T19:57:49","modified_gmt":"2021-11-24T00:57:49","slug":"tr-96-25-on-the-impact-of-sense-of-direction-on-communication-complexity","status":"publish","type":"page","link":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1996\/tr-96-25-on-the-impact-of-sense-of-direction-on-communication-complexity\/","title":{"rendered":"TR-96-25: On the Impact of Sense of Direction on Communication Complexity"},"content":{"rendered":"

Carleton University
\nTechnical Report<\/a> TR-96-25
\nOctober\u00a01996<\/p>\n

On the Impact of Sense of Direction on Communication Complexity<\/h2>\n
\n
\n
\n
\n
\n
\n
\n
Paola Flocchini, Bernard Mans, Nicola Santoro<\/div>\n<\/div>\n<\/div>\n<\/div>\n
\n

Abstract<\/h3>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n
\n

In this paper, we prove a general result on the impact of Sense of Direction. We show that, in arbitrary graphs, any Sense of Direction has a dramatic e\u000bect on the communication complexity of several important distributed problems: Broadcast, Depth-First Traversal, Election, and Spanning Tree Construction. In systems with n nodes and e communication links, the solution for the the Depth First Traversal and the Broadcast problems require \u03a9(e) messages without labeling; we show that, with any Sense of Direction, they can be solved exchanging only \u0002\u0398(n) messages, even if the system is anonymous. The problems of Election and of Spanning-Tree Construction require \u03a9(e+n log n) messages in absence of labeling; on the other hand, with Sense of Direction we show that they can be solved with \u0398\u0002(n) messages.The results presented here completely explain and generalize the existing results which now follow as corollaries for speci\fc labelings.<\/p>\n

TR-96-25.pdf<\/a><\/p>\n<\/div>\n","protected":false},"excerpt":{"rendered":"

Carleton University Technical Report TR-96-25 October\u00a01996 On the Impact of Sense of Direction on Communication Complexity Paola Flocchini, Bernard Mans, Nicola Santoro Abstract In this paper, we prove a general result on the impact of Sense of Direction. We show that, in arbitrary graphs, any Sense of Direction has a dramatic e\u000bect on the communication […]<\/p>\n","protected":false},"author":49,"featured_media":0,"parent":12155,"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":"\nTR-96-25: On the Impact of Sense of Direction on Communication Complexity - School of Computer Science<\/title>\n<meta name=\"description\" content=\"Carleton University Technical Report TR-96-25 October\u00a01996 On the Impact of Sense of Direction on Communication Complexity Paola Flocchini, Bernard Mans,\" \/>\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-1996\/tr-96-25-on-the-impact-of-sense-of-direction-on-communication-complexity\/\" \/>\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-1996\/tr-96-25-on-the-impact-of-sense-of-direction-on-communication-complexity\/\",\"url\":\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1996\/tr-96-25-on-the-impact-of-sense-of-direction-on-communication-complexity\/\",\"name\":\"TR-96-25: On the Impact of Sense of Direction on Communication Complexity - School of Computer Science\",\"isPartOf\":{\"@id\":\"https:\/\/carleton.ca\/scs\/#website\"},\"datePublished\":\"2021-11-24T00:57:49+00:00\",\"dateModified\":\"2021-11-24T00:57:49+00:00\",\"description\":\"Carleton University Technical Report TR-96-25 October\u00a01996 On the Impact of Sense of Direction on Communication Complexity Paola Flocchini, Bernard Mans,\",\"breadcrumb\":{\"@id\":\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1996\/tr-96-25-on-the-impact-of-sense-of-direction-on-communication-complexity\/#breadcrumb\"},\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1996\/tr-96-25-on-the-impact-of-sense-of-direction-on-communication-complexity\/\"]}]},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1996\/tr-96-25-on-the-impact-of-sense-of-direction-on-communication-complexity\/#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 1996\",\"item\":\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1996\/\"},{\"@type\":\"ListItem\",\"position\":5,\"name\":\"TR-96-25: On the Impact of Sense of Direction on Communication Complexity\"}]},{\"@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-96-25: On the Impact of Sense of Direction on Communication Complexity - School of Computer Science","description":"Carleton University Technical Report TR-96-25 October\u00a01996 On the Impact of Sense of Direction on Communication Complexity Paola Flocchini, Bernard Mans,","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-1996\/tr-96-25-on-the-impact-of-sense-of-direction-on-communication-complexity\/","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-1996\/tr-96-25-on-the-impact-of-sense-of-direction-on-communication-complexity\/","url":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1996\/tr-96-25-on-the-impact-of-sense-of-direction-on-communication-complexity\/","name":"TR-96-25: On the Impact of Sense of Direction on Communication Complexity - School of Computer Science","isPartOf":{"@id":"https:\/\/carleton.ca\/scs\/#website"},"datePublished":"2021-11-24T00:57:49+00:00","dateModified":"2021-11-24T00:57:49+00:00","description":"Carleton University Technical Report TR-96-25 October\u00a01996 On the Impact of Sense of Direction on Communication Complexity Paola Flocchini, Bernard Mans,","breadcrumb":{"@id":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1996\/tr-96-25-on-the-impact-of-sense-of-direction-on-communication-complexity\/#breadcrumb"},"inLanguage":"en-US","potentialAction":[{"@type":"ReadAction","target":["https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1996\/tr-96-25-on-the-impact-of-sense-of-direction-on-communication-complexity\/"]}]},{"@type":"BreadcrumbList","@id":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1996\/tr-96-25-on-the-impact-of-sense-of-direction-on-communication-complexity\/#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 1996","item":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1996\/"},{"@type":"ListItem","position":5,"name":"TR-96-25: On the Impact of Sense of Direction on Communication Complexity"}]},{"@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\/12888"}],"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=12888"}],"version-history":[{"count":1,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/12888\/revisions"}],"predecessor-version":[{"id":12889,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/12888\/revisions\/12889"}],"up":[{"embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/12155"}],"wp:attachment":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/media?parent=12888"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}