{"id":12776,"date":"2021-11-20T18:58:23","date_gmt":"2021-11-20T23:58:23","guid":{"rendered":"https:\/\/carleton.ca\/scs\/?page_id=12776"},"modified":"2021-11-20T18:59:47","modified_gmt":"2021-11-20T23:59:47","slug":"tr-95-10-sense-of-direction-definitions-properties-and-classes","status":"publish","type":"page","link":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1995\/tr-95-10-sense-of-direction-definitions-properties-and-classes\/","title":{"rendered":"TR-95-10: Sense of Direction: Definitions, Properties, and Classes"},"content":{"rendered":"

Carleton University
\nTechnical Report<\/a> TR-95-10
\nApril 1995<\/p>\n

Sense of Direction: Definitions, Properties, and Classes<\/h2>\n
\n
\n
\n
\n
Paola Flocchini, Bernard Mans, Nicola Santoro<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n
\n

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

An extensive body of evidence exists of the impact that speci\fc edge labelings have on the communication complexity of distributed problems. It has been long suspected that these very di\u000berent labelings share a common property, named a long time ago Sense of Direction. In spite of the large amount of investigations, and of the obvious practical importance, a formal characterization of this property did not exist.In this paper, we \fnally provide a formal de\fnition of Sense of Direction. We show that in Sense of Direction there is a very speci\fc link between three factors: the labeling, the topological structure, and the local view that an entity has of the system. In a way, Sense of Direction is the capacity of a node in the system to use the labeling to translate the local view of its neighbors into its own. Using the formal de\fnition as an observational platform, we describe several properties which allow the translation process to be possible beyond the immediate neighborhood. Finally, we identify four general classes of labelings and analyzed their properties; these classes include all the labelings used in the literature.<\/p>\n

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

Carleton University Technical Report TR-95-10 April 1995 Sense of Direction: Definitions, Properties, and Classes Paola Flocchini, Bernard Mans, Nicola Santoro Abstract An extensive body of evidence exists of the impact that speci\fc edge labelings have on the communication complexity of distributed problems. It has been long suspected that these very di\u000berent labelings share a common […]<\/p>\n","protected":false},"author":49,"featured_media":0,"parent":11736,"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-95-10: Sense of Direction: Definitions, Properties, and Classes - School of Computer Science<\/title>\n<meta name=\"description\" content=\"Carleton University Technical Report TR-95-10 April 1995 Sense of Direction: Definitions, Properties, and Classes Paola Flocchini, Bernard Mans, Nicola\" \/>\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-1995\/tr-95-10-sense-of-direction-definitions-properties-and-classes\/\" \/>\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-1995\/tr-95-10-sense-of-direction-definitions-properties-and-classes\/\",\"url\":\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1995\/tr-95-10-sense-of-direction-definitions-properties-and-classes\/\",\"name\":\"TR-95-10: Sense of Direction: Definitions, Properties, and Classes - School of Computer Science\",\"isPartOf\":{\"@id\":\"https:\/\/carleton.ca\/scs\/#website\"},\"datePublished\":\"2021-11-20T23:58:23+00:00\",\"dateModified\":\"2021-11-20T23:59:47+00:00\",\"description\":\"Carleton University Technical Report TR-95-10 April 1995 Sense of Direction: Definitions, Properties, and Classes Paola Flocchini, Bernard Mans, Nicola\",\"breadcrumb\":{\"@id\":\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1995\/tr-95-10-sense-of-direction-definitions-properties-and-classes\/#breadcrumb\"},\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1995\/tr-95-10-sense-of-direction-definitions-properties-and-classes\/\"]}]},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1995\/tr-95-10-sense-of-direction-definitions-properties-and-classes\/#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 1995\",\"item\":\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1995\/\"},{\"@type\":\"ListItem\",\"position\":5,\"name\":\"TR-95-10: Sense of Direction: Definitions, Properties, and Classes\"}]},{\"@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-95-10: Sense of Direction: Definitions, Properties, and Classes - School of Computer Science","description":"Carleton University Technical Report TR-95-10 April 1995 Sense of Direction: Definitions, Properties, and Classes Paola Flocchini, Bernard Mans, Nicola","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-1995\/tr-95-10-sense-of-direction-definitions-properties-and-classes\/","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-1995\/tr-95-10-sense-of-direction-definitions-properties-and-classes\/","url":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1995\/tr-95-10-sense-of-direction-definitions-properties-and-classes\/","name":"TR-95-10: Sense of Direction: Definitions, Properties, and Classes - School of Computer Science","isPartOf":{"@id":"https:\/\/carleton.ca\/scs\/#website"},"datePublished":"2021-11-20T23:58:23+00:00","dateModified":"2021-11-20T23:59:47+00:00","description":"Carleton University Technical Report TR-95-10 April 1995 Sense of Direction: Definitions, Properties, and Classes Paola Flocchini, Bernard Mans, Nicola","breadcrumb":{"@id":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1995\/tr-95-10-sense-of-direction-definitions-properties-and-classes\/#breadcrumb"},"inLanguage":"en-US","potentialAction":[{"@type":"ReadAction","target":["https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1995\/tr-95-10-sense-of-direction-definitions-properties-and-classes\/"]}]},{"@type":"BreadcrumbList","@id":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1995\/tr-95-10-sense-of-direction-definitions-properties-and-classes\/#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 1995","item":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1995\/"},{"@type":"ListItem","position":5,"name":"TR-95-10: Sense of Direction: Definitions, Properties, and Classes"}]},{"@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_image_type":"none","banner_button":"no"},"_links":{"self":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/12776"}],"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=12776"}],"version-history":[{"count":2,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/12776\/revisions"}],"predecessor-version":[{"id":12778,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/12776\/revisions\/12778"}],"up":[{"embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/11736"}],"wp:attachment":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/media?parent=12776"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}