{"id":12854,"date":"2021-11-22T18:40:42","date_gmt":"2021-11-22T23:40:42","guid":{"rendered":"https:\/\/carleton.ca\/scs\/?page_id=12854"},"modified":"2021-11-22T18:40:42","modified_gmt":"2021-11-22T23:40:42","slug":"tr-96-18-symmetry-and-computability-in-anonymous-networks-a-brief-survey","status":"publish","type":"page","link":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1996\/tr-96-18-symmetry-and-computability-in-anonymous-networks-a-brief-survey\/","title":{"rendered":"TR-96-18: Symmetry and Computability in Anonymous Networks: A Brief Survey"},"content":{"rendered":"

Carleton University
\nTechnical Report<\/a> TR-96-18
\nJuly 1996<\/p>\n

Symmetry and Computability in Anonymous Networks: A Brief Survey<\/h2>\n
\n
\n
\n
\n
\n
\n
Evangelos Kranakis<\/div>\n<\/div>\n<\/div>\n
\n

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

Processors in anonymous networks are as identical to each other as possible and possess “little” knowledge about the network. Anonymous networks are very useful in theoretical studies for testing “true distributivity”. In this paper we give a brief survey of results illuminating how symmetry influences computability in anonymous networks. Problems and issues considered include leader election, spanning tree construction, orientations, randomization, processor views, and computability problems on arbitrary as well as symmetric functions. Results mentioned are applicable to several topologies ranging from the rings, tori, hypercubes, and Cayley networks to arbitrary networks. We also propose several related open problems.<\/p>\n

Dedicated to the memory of my beloved father Konstantionos who passed away unexpectedly on June 17, 1996.<\/p>\n

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

Carleton University Technical Report TR-96-18 July 1996 Symmetry and Computability in Anonymous Networks: A Brief Survey Evangelos Kranakis Abstract Processors in anonymous networks are as identical to each other as possible and possess “little” knowledge about the network. Anonymous networks are very useful in theoretical studies for testing “true distributivity”. In this paper we give […]<\/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-18: Symmetry and Computability in Anonymous Networks: A Brief Survey - School of Computer Science<\/title>\n<meta name=\"description\" content=\"Carleton University Technical Report TR-96-18 July 1996 Symmetry and Computability in Anonymous Networks: A Brief Survey Evangelos Kranakis Abstract\" \/>\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-18-symmetry-and-computability-in-anonymous-networks-a-brief-survey\/\" \/>\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-18-symmetry-and-computability-in-anonymous-networks-a-brief-survey\/\",\"url\":\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1996\/tr-96-18-symmetry-and-computability-in-anonymous-networks-a-brief-survey\/\",\"name\":\"TR-96-18: Symmetry and Computability in Anonymous Networks: A Brief Survey - School of Computer Science\",\"isPartOf\":{\"@id\":\"https:\/\/carleton.ca\/scs\/#website\"},\"datePublished\":\"2021-11-22T23:40:42+00:00\",\"dateModified\":\"2021-11-22T23:40:42+00:00\",\"description\":\"Carleton University Technical Report TR-96-18 July 1996 Symmetry and Computability in Anonymous Networks: A Brief Survey Evangelos Kranakis Abstract\",\"breadcrumb\":{\"@id\":\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1996\/tr-96-18-symmetry-and-computability-in-anonymous-networks-a-brief-survey\/#breadcrumb\"},\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1996\/tr-96-18-symmetry-and-computability-in-anonymous-networks-a-brief-survey\/\"]}]},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1996\/tr-96-18-symmetry-and-computability-in-anonymous-networks-a-brief-survey\/#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-18: Symmetry and Computability in Anonymous Networks: A Brief Survey\"}]},{\"@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-18: Symmetry and Computability in Anonymous Networks: A Brief Survey - School of Computer Science","description":"Carleton University Technical Report TR-96-18 July 1996 Symmetry and Computability in Anonymous Networks: A Brief Survey Evangelos Kranakis Abstract","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-18-symmetry-and-computability-in-anonymous-networks-a-brief-survey\/","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-18-symmetry-and-computability-in-anonymous-networks-a-brief-survey\/","url":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1996\/tr-96-18-symmetry-and-computability-in-anonymous-networks-a-brief-survey\/","name":"TR-96-18: Symmetry and Computability in Anonymous Networks: A Brief Survey - School of Computer Science","isPartOf":{"@id":"https:\/\/carleton.ca\/scs\/#website"},"datePublished":"2021-11-22T23:40:42+00:00","dateModified":"2021-11-22T23:40:42+00:00","description":"Carleton University Technical Report TR-96-18 July 1996 Symmetry and Computability in Anonymous Networks: A Brief Survey Evangelos Kranakis Abstract","breadcrumb":{"@id":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1996\/tr-96-18-symmetry-and-computability-in-anonymous-networks-a-brief-survey\/#breadcrumb"},"inLanguage":"en-US","potentialAction":[{"@type":"ReadAction","target":["https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1996\/tr-96-18-symmetry-and-computability-in-anonymous-networks-a-brief-survey\/"]}]},{"@type":"BreadcrumbList","@id":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1996\/tr-96-18-symmetry-and-computability-in-anonymous-networks-a-brief-survey\/#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-18: Symmetry and Computability in Anonymous Networks: A Brief Survey"}]},{"@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\/12854"}],"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=12854"}],"version-history":[{"count":1,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/12854\/revisions"}],"predecessor-version":[{"id":12855,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/12854\/revisions\/12855"}],"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=12854"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}