{"id":12842,"date":"2021-11-22T18:30:29","date_gmt":"2021-11-22T23:30:29","guid":{"rendered":"https:\/\/carleton.ca\/scs\/?page_id=12842"},"modified":"2021-11-22T18:30:29","modified_gmt":"2021-11-22T23:30:29","slug":"tr-96-13-computing-on-anonymous-networks-with-sense-of-direction","status":"publish","type":"page","link":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1996\/tr-96-13-computing-on-anonymous-networks-with-sense-of-direction\/","title":{"rendered":"TR-96-13: Computing on Anonymous Networks with Sense of Direction"},"content":{"rendered":"

Carleton University
\nTechnical Report<\/a> TR-96-13
\nApril\u00a01996<\/p>\n

Computing on Anonymous Networks with Sense of Direction<\/h2>\n
\n
\n
\n
\n
\n
Paola Flocchini, Alessandro Roncato, Nicola Santoro<\/div>\n<\/div>\n
\n

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

Sense of direction refers to a set of global consistency constraints of the lo- cal labeling of the edges of a network. Sense of direction has a large impact on the communication complexity of many distributed problems. In this paper, we study the impact that sense of direction has on computability and we focus on anonymous networks. We establish several results. In particular, we prove that with weak sense of direction, the intuitive knowledge-computability hierarchy be- tween levels of a priori structural knowledge collapses. A powerful implication is the formal proof that shortest path routing is possible in anonymous networks with sense of direction. We prove that weak sense of direction is computationally stronger than topological awareness. We also consider several fundamental prob- lems; for each, we provide a complete characterization of the anonymous networks on which it is computable with sense of direction.<\/p>\n<\/div>\n

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

Carleton University Technical Report TR-96-13 April\u00a01996 Computing on Anonymous Networks with Sense of Direction Paola Flocchini, Alessandro Roncato, Nicola Santoro Abstract Sense of direction refers to a set of global consistency constraints of the lo- cal labeling of the edges of a network. Sense of direction has a large impact on the communication complexity of […]<\/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-13: Computing on Anonymous Networks with Sense of Direction - School of Computer Science<\/title>\n<meta name=\"description\" content=\"Carleton University Technical Report TR-96-13 April\u00a01996 Computing on Anonymous Networks with Sense of Direction Paola Flocchini, Alessandro Roncato,\" \/>\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-13-computing-on-anonymous-networks-with-sense-of-direction\/\" \/>\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-13-computing-on-anonymous-networks-with-sense-of-direction\/\",\"url\":\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1996\/tr-96-13-computing-on-anonymous-networks-with-sense-of-direction\/\",\"name\":\"TR-96-13: Computing on Anonymous Networks with Sense of Direction - School of Computer Science\",\"isPartOf\":{\"@id\":\"https:\/\/carleton.ca\/scs\/#website\"},\"datePublished\":\"2021-11-22T23:30:29+00:00\",\"dateModified\":\"2021-11-22T23:30:29+00:00\",\"description\":\"Carleton University Technical Report TR-96-13 April\u00a01996 Computing on Anonymous Networks with Sense of Direction Paola Flocchini, Alessandro Roncato,\",\"breadcrumb\":{\"@id\":\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1996\/tr-96-13-computing-on-anonymous-networks-with-sense-of-direction\/#breadcrumb\"},\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1996\/tr-96-13-computing-on-anonymous-networks-with-sense-of-direction\/\"]}]},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1996\/tr-96-13-computing-on-anonymous-networks-with-sense-of-direction\/#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-13: Computing on Anonymous Networks with Sense of Direction\"}]},{\"@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-13: Computing on Anonymous Networks with Sense of Direction - School of Computer Science","description":"Carleton University Technical Report TR-96-13 April\u00a01996 Computing on Anonymous Networks with Sense of Direction Paola Flocchini, Alessandro Roncato,","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-13-computing-on-anonymous-networks-with-sense-of-direction\/","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-13-computing-on-anonymous-networks-with-sense-of-direction\/","url":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1996\/tr-96-13-computing-on-anonymous-networks-with-sense-of-direction\/","name":"TR-96-13: Computing on Anonymous Networks with Sense of Direction - School of Computer Science","isPartOf":{"@id":"https:\/\/carleton.ca\/scs\/#website"},"datePublished":"2021-11-22T23:30:29+00:00","dateModified":"2021-11-22T23:30:29+00:00","description":"Carleton University Technical Report TR-96-13 April\u00a01996 Computing on Anonymous Networks with Sense of Direction Paola Flocchini, Alessandro Roncato,","breadcrumb":{"@id":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1996\/tr-96-13-computing-on-anonymous-networks-with-sense-of-direction\/#breadcrumb"},"inLanguage":"en-US","potentialAction":[{"@type":"ReadAction","target":["https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1996\/tr-96-13-computing-on-anonymous-networks-with-sense-of-direction\/"]}]},{"@type":"BreadcrumbList","@id":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1996\/tr-96-13-computing-on-anonymous-networks-with-sense-of-direction\/#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-13: Computing on Anonymous Networks with Sense of Direction"}]},{"@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\/12842"}],"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=12842"}],"version-history":[{"count":1,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/12842\/revisions"}],"predecessor-version":[{"id":12843,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/12842\/revisions\/12843"}],"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=12842"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}