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 definition of majority, different dynamics can occur. We are interested in dynamos; i.e., initial assignments of colors which lead the system to a monochromatic configuration in a finite 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 systems (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 fixed point. We derive lower and upper bounds on the size of dynamos for three types of tori, under different 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.

Flocchini, P., Lodi, E., Luccio, F., Pagli, L., & Santoro, N. (2004). Dynamic monopolies in Tori. DISCRETE APPLIED MATHEMATICS, 137(2), 197-212 [10.1016/S0166-218X(03)00261-0].

Dynamic monopolies in Tori

LODI, ELENA;
2004

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, with the color held by the majority of its neighbors. Depending on the initial assignment of colors to the nodes and on the definition of majority, different dynamics can occur. We are interested in dynamos; i.e., initial assignments of colors which lead the system to a monochromatic configuration in a finite 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 systems (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 fixed point. We derive lower and upper bounds on the size of dynamos for three types of tori, under different 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.
Flocchini, P., Lodi, E., Luccio, F., Pagli, L., & Santoro, N. (2004). Dynamic monopolies in Tori. DISCRETE APPLIED MATHEMATICS, 137(2), 197-212 [10.1016/S0166-218X(03)00261-0].
File in questo prodotto:
File Dimensione Formato  
DynamicMonopoliesInTori.pdf

non disponibili

Tipologia: Post-print
Licenza: NON PUBBLICO - Accesso privato/ristretto
Dimensione 494.44 kB
Formato Adobe PDF
494.44 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11365/25009
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo