We consider the problem of decontaminating a network where all nodes are infected by a virus. The decontamination strategy is performed using a Cellular Automata (CA) model in which each node of the network is represented by the automata cell and thus, the network host status is also mapped to the CA state (contaminated, decontaminating, decontaminated). All hosts are assumed to be initially contaminated and the status of each cell is synchronously updated according to a set of local rules, based on the state of its neighbourhood. Our goal is to find the set of local rules that will accomplish the decontamination in an optimal way. The metrics used to define optimality is the minimization of three metrics: the maximum number of decontaminating cells at each step, the required value of the immunity time of each cell and the number of steps to complete the sanitization algorithm. In our research, we explore the designing of these local decontamination rules by refining the concept of the neighbourhood radius of CA with the addition of two new dimensions: Visibility Hop and Contamination Distance. Additionally, a research tool that help us manage our study have been developed.

Network decontamination is a well known mobile agent problem with many applications. We assume that all nodes of a network are contaminated (e.g., by a virus) and a set of agents is deployed to decontaminate them. An agent passing by a node decontaminates it, however a decontaminated node can be recontaminated if any of its neighbours is contaminated. In the vast literature a variety of models are considered and different assumptions are made on the power of the agents. In this thesis we study variation of the decontamination problem in mesh and tori topologies, under the assumption that when a node is decontaminated, it is immune to recontamination for a predefined amount of time t (called immunity time). After the immunity time is elapsed, recontamination can occur. We focus on three different models: mobile agents (MA), cellular automata (CA), and mobile cellular automata (MCA). The first two models are commonly studied and employed in several other contexts, the third model is introduced in this thesis for the first time. In each model we study the temporal decontamination problem (adapted to the particular setting) under a variety of assumptions on the capabilities of the decontaminating elements (agents for MA and MCA, decontaminating cells for CA). Some of the parameters we consider in this study are: visibility of the active elements, their ability to make copies of themselves, their ability to communicate, and the possibility to remember their past actions (memory). We describe several solutions in the various scenarios and we analyze their complexity. Efficiency is evaluated slightly differently in each model, but essentially the effort is in the minimization of the number of simultaneous decontaminating elements active in the system while performing the decontamination with a given immunity time.

Network decontamination is a well known mobile agent problem with many applications. We assume that all nodes of a network are contaminated (e.g., by a virus) and a set of agents is deployed to decontaminate them. An agent passing by a node decontaminates it, however a decontaminated node can be recontaminated if any of its neighbours is contaminated. In the vast literature a variety of models are considered and different assumptions are made on the power of the agents. In this thesis we study variation of the decontamination problem in mesh and tori topologies, under the assumption that when a node is decontaminated, it is immune to recontamination for a predefined amount of time t (called immunity time). After the immunity time is elapsed, recontamination can occur. We focus on three different models: mobile agents (MA), cellular automata (CA), and mobile cellular automata (MCA). The first two models are commonly studied and employed in several other contexts, the third model is introduced in this thesis for the first time. In each model we study the temporal decontamination problem (adapted to the particular setting) under a variety of assumptions on the capabilities of the decontaminating elements (agents for MA and MCA, decontaminating cells for CA). Some of the parameters we consider in this study are: visibility of the active elements, their ability to make copies of themselves, their ability to communicate, and the possibility to remember their past actions (memory). We describe several solutions in the various scenarios and we analyze their complexity. Efficiency is evaluated slightly differently in each model, but essentially the effort is in the minimization of the number of simultaneous decontaminating elements active in the system while performing the decontamination with a given immunity time.

Network decontamination is a well known mobile agent problem with many applications. We assume that all nodes of a network are contaminated (e.g., by a virus) and a set of agents is deployed to decontaminate them. An agent passing by a node decontaminates it, however a decontaminated node can be recontaminated if any of its neighbours is contaminated. In the vast literature a variety of models are considered and different assumptions are made on the power of the agents. In this thesis we study variation of the decontamination problem in mesh and tori topologies, under the assumption that when a node is decontaminated, it is immune to recontamination for a predefined amount of time t (called immunity time). After the immunity time is elapsed, recontamination can occur. We focus on three different models: mobile agents (MA), cellular automata (CA), and mobile cellular automata (MCA). The first two models are commonly studied and employed in several other contexts, the third model is introduced in this thesis for the first time. In each model we study the temporal decontamination problem (adapted to the particular setting) under a variety of assumptions on the capabilities of the decontaminating elements (agents for MA and MCA, decontaminating cells for CA). Some of the parameters we consider in this study are: visibility of the active elements, their ability to make copies of themselves, their ability to communicate, and the possibility to remember their past actions (memory). We describe several solutions in the various scenarios and we analyze their complexity. Efficiency is evaluated slightly differently in each model, but essentially the effort is in the minimization of the number of simultaneous decontaminating elements active in the system while performing the decontamination with a given immunity time.

Network decontamination is a well known mobile agent problem with many applications. We assume that all nodes of a network are contaminated (e.g., by a virus) and a set of agents is deployed to decontaminate them. An agent passing by a node decontaminates it, however a decontaminated node can be recontaminated if any of its neighbours is contaminated. In the vast literature a variety of models are considered and different assumptions are made on the power of the agents. In this thesis we study variation of the decontamination problem in mesh and tori topologies, under the assumption that when a node is decontaminated, it is immune to recontamination for a predefined amount of time t (called immunity time). After the immunity time is elapsed, recontamination can occur. We focus on three different models: mobile agents (MA), cellular automata (CA), and mobile cellular automata (MCA). The first two models are commonly studied and employed in several other contexts, the third model is introduced in this thesis for the first time. In each model we study the temporal decontamination problem (adapted to the particular setting) under a variety of assumptions on the capabilities of the decontaminating elements (agents for MA and MCA, decontaminating cells for CA). Some of the parameters we consider in this study are: visibility of the active elements, their ability to make copies of themselves, their ability to communicate, and the possibility to remember their past actions (memory). We describe several solutions in the various scenarios and we analyze their complexity. Efficiency is evaluated slightly differently in each model, but essentially the effort is in the minimization of the number of simultaneous decontaminating elements active in the system while performing the decontamination with a given immunity time.

Made available in DSpace on 2016-03-15T19:37:48Z (GMT). No. of bitstreams: 1 Marcelo Arbori Nogueira.pdf: 904606 bytes, checksum: 186b7d2c9f1c91d2dc019d673ecdf983 (MD5) Previous issue date: 2013-12-12 / Cellular automata are models where, out of the application of a local rule to the cells of their regular lattice, global behaviour emerges. Depending on the rule applied, the emergent behaviour may be interpreted as a computation, or used to simulate various types of phenomena, such as physical, biological or social. Cellular automata can be used to simulate population growth, spread of disease, tumor growth, decontamination, among other applications. This paper seeks to expand the theoretical limits on the process of decontamination of a two-dimensional lattice using cellular automata, as established by Daadaa (2012). Here we relax premises assumed therein and seek a better understanding of the characteristics of the rules involved as well as of the behaviour of the immunity time of the decontaminated cells. In order to do so, but since the initial conditions correspond to a very large space, massively parallel programming was employed using GPU, which allowed to evaluate a large number of possibilities. It was possible to identify two decontamination rules linked to each type of neighborhood studied (von Neumann and Moore), that generalise previous rules defined in the work we relied upon. In experiments made with the new rules, their superior efficacy became apparent for random initial conditions; it was also possible to assertain their effectiveness for uniform distribution of states. The general rules allow we developed allowed for a better understanding of the immunity time required to decontaminate a lattice. It was observed that the ratio between the immunity time and the lattice size is not linear, as suggested by Daadaa. / Autômatos celulares são modelos onde, a partir da aplicação de regras locais às células de seu reticulado, emerge um comportamento global. Dependendo da regra aplicada o comportamento emergente pode ser entendido como uma computação, ou utilizado para simular fenômenos físicos, biológicos, sociais, etc. Pode-se usar autômatos celulares para simular crescimento populacional, propagação de doenças, crescimento de tumores, descontaminação, entre outras aplicações. O presente trabalho procura expandir limites teóricos a respeito do processo de descontaminação de reticulados bidimensionais por autômatos celulares, apresentado por Daadaa (2012). Flexibiliza-se aqui premissas lá assumidas e procura-se uma melhor compreensão sobre as características das regras envolvidas bem como do comportamento do tempo de imunidade de células recuperadas. Para tanto, uma vez que as possíveis condições iniciais configuram um espaço muito grande, foi empregada programação massivamente paralela utilizando GPU, permitindo avaliar um grande número de possibilidades. Foi possível identificar duas regras de descontaminação, específicas para cada tipo de vizinhança estudada (vizinhanças de von Neumann e de Moore), que generalizam as regras anteriormente definidas no mesmo contexto do trabalho aqui tratado. Nos experimentos realizados, foi possível comparar a eficácia das regras propostas com as que lhes deram origem, e ficou evidente a eficácia superior das novas regras para condições iniciais aleatória; também foi possível constatar a eficácia das regras para distribuições uniformes de estados. As regras gerais desenvolvidas permitiram melhor compreensão do tempo de imunidade necessário para descontaminar um reticulado. Foi possível observar que a relação do tempo de imunidade com o tamanho do reticulado não é linear como sugerido no trabalho de Daadaa.