Colloquium Mathematics - Irène Marcovici, Université de Rouen Normandie

As part of the Workshop On Randomness and Discrete Structures (WORDS2025) Irène Marcovici gives the following colloquium:

Title: A decentralised diagnosis method with probabilistic cellular automata

Abstract:

The decentralised diagnosis problem consists in the detection of a certain amount of defects in a distributed network. Here, we tackle this problem in the context of two-dimensional cellular automata with three states: neutral, alert and defect. When the density of defects is below a given threshold, we want the alert state to coexist with the neutral state, while when this density is above the threshold, we want the alert state to invade the whole grid. We present two probabilistic rules to answer this problem. The first one is isotropic and is studied with numerical simulations. The second one is defined on Toom’s neighbourhood and is examined with an analytical point of view. These solutions constitute a first step towards a broader study of the decentralised diagnosis problem on more general networks.

This is a joint work with Nazim Fatès and Régine Marchand.