{"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":"2026-06-02T14:59:25","modified_gmt":"2026-06-02T18:59:25","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":"\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-96-18: Symmetry and Computability in Anonymous Networks: A Brief Survey\n                    <\/h1>\n                \n                                \n                            <\/header>\n\n                    <\/div>\n\n            <\/div>\n\n    <\/div>\n<\/section>\n\n<p>Carleton University<br>\n<a href=\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1996\/\">Technical Report<\/a> TR-96-18<br>\nJuly 1996<\/p>\n\n\n\n<h2 id=\"symmetry-and-computability-in-anonymous-networks-a-brief-survey\" class=\"wp-block-heading tr_t1\">Symmetry and Computability in Anonymous Networks: A Brief Survey<\/h2>\n\n\n\n<div class=\"tr_t3\">\n<div class=\"tr_t3\">\n<div class=\"tr_t3\">\n<div class=\"tr_t3\">\n<div class=\"tr_t3\">\n<div class=\"tr_t3\">\n<div class=\"tr_t3\">Evangelos Kranakis<\/div>\n<\/div>\n<\/div>\n<div>\n<h3>Abstract<\/h3>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n\n\n\n<div class=\"tr_abstract\">\n<p class=\"tr_abstract\">Processors in anonymous networks are as identical to each other as possible and possess &#8220;little&#8221; knowledge about the network. Anonymous networks are very useful in theoretical studies for testing &#8220;true distributivity&#8221;. 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<p class=\"tr_abstract\">Dedicated to the memory of my beloved father Konstantionos who passed away unexpectedly on June 17, 1996.<\/p>\n<p><a href=\"https:\/\/carleton.ca\/scs\/wp-content\/uploads\/sites\/260\/TR-96-18.pdf\">TR-96-18.pdf<\/a><\/p>\n<\/div>\n","protected":false},"excerpt":{"rendered":"<p>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 &#8220;little&#8221; knowledge about the network. Anonymous networks are very useful in theoretical studies for testing &#8220;true distributivity&#8221;. In this paper we give [&hellip;]<\/p>\n","protected":false},"author":2,"featured_media":0,"parent":12155,"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-12854","page","type-page","status-publish","hentry"],"acf":{"cu_post_thumbnail":false},"_links":{"self":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/12854","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=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"}],"wp:term":[{"taxonomy":"cu_page_type","embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/cu_page_type?post=12854"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}