{"id":13019,"date":"2021-12-02T20:56:12","date_gmt":"2021-12-03T01:56:12","guid":{"rendered":"https:\/\/carleton.ca\/scs\/?page_id=13019"},"modified":"2026-06-02T14:59:24","modified_gmt":"2026-06-02T18:59:24","slug":"tr-00-02-dynamic-monopolies-in-tori","status":"publish","type":"page","link":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-2000\/tr-00-02-dynamic-monopolies-in-tori\/","title":{"rendered":"TR-00-02: Dynamic Monopolies in Tori"},"content":{"rendered":"\n
\n
\n\n
\n
\n
\n

\n TR-00-02: Dynamic Monopolies in Tori\n <\/h1>\n \n \n <\/header>\n\n <\/div>\n\n <\/div>\n\n <\/div>\n<\/section>\n\n

Carleton University
\nTechnical Report<\/a> TR-00-02
\nFebruary 2000<\/p>\n\n\n\n

Dynamic Monopolies in Tori<\/h2>\n\n\n\n
\n
\n
\n
\n
\n
\n
\n
\n
Paola Flocchini, Elena Lodi, Fabrizio Luccio, Linda Pagli, Nicola Santoro<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n
\n

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

Let G be a simple connected graph where every node is colored either black or white. Consider now the following repetitive process on G: each node recolors itself, at each local time step, with the color held by the majority of its neighbors. Depending on the initial assignment of colors to the nodes and on the de\fnition of majority, di\u000berent dynamics can occur. We are interested in dynamos; i.e., initial assignments of colours which lead the system to a monocromatic con\fgu- ration in a \fnite number of steps. In the context of distributed computing and communication networks, this repetitive process is particularly important in that it describes the impact that a set of initial faults can have in majority-based sys- tems (where black nodes correspond to faulty elements and white to non-faulty ones). In this paper we study two particular forms of dynamos (irreversible and monotone) in tori, focusing on the minimum number of initial black elements needed to reach the \fxed point. We derive lower and upper bounds on the size of dynamos for three types of tori, under di\u000berent assumptions on the majority rule (simple and strong). These bounds are tight within an additive constant. The upper bounds are constructive: for each topology and each majority rule, we exhibit a dynamo of the claimed size. For the constructed dynamos, we also analyze their time complexity, i.e. the number of steps necessary to reach the monocromatic con\fguration when the process is synchronous.<\/p>\n\n\n\n

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

Carleton University Technical Report TR-00-02 February 2000 Dynamic Monopolies in Tori Paola Flocchini, Elena Lodi, Fabrizio Luccio, Linda Pagli, Nicola Santoro Abstract Let G be a simple connected graph where every node is colored either black or white. Consider now the following repetitive process on G: each node recolors itself, at each local time step, […]<\/p>\n","protected":false},"author":2,"featured_media":0,"parent":12258,"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-13019","page","type-page","status-publish","hentry"],"acf":{"cu_post_thumbnail":false},"_links":{"self":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/13019","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=13019"}],"version-history":[{"count":1,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/13019\/revisions"}],"predecessor-version":[{"id":13021,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/13019\/revisions\/13021"}],"up":[{"embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/12258"}],"wp:attachment":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/media?parent=13019"}],"wp:term":[{"taxonomy":"cu_page_type","embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/cu_page_type?post=13019"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}