Boss-Free Decisions
Photo © Softpedia
[ C H R O N I C L E ]
When leaving the cinema, your group of friends hesitates; are you going to assuage your hunger in a pizzeria or a Japanese restaurant? Solving this problem doesn’t need complicated mathematics; it just needs one member of the group to take things in hand and count the number in favour of one option or the other to decide how the evening pans out. Let us imagine that no one wants the role (“boss-free”) and that it is forbidden to count up the votes. In these conditions, can the majority choice be decided? The situation is probably a little strange for deciding where to eat, but it exists concretely in distributed IT systems; the network has no centre and each actor in the network can only really perceive its immediate neighbour. A way of getting global information about the network using only local information is needed. In a relatively simple context, there are solutions, one of which is based on Toom’s cellular automata.
What exactly is it?The starting point is a square lattice; each small square, called a cell, is coloured either white or blue initially. At each step, each cell will take the majority colour from the group of three cells it forms with its neighbour immediately to the right and above it. This very simple rule, proposed by the Soviet mathematician Andrei Toom in 1978, changes our original colouring instant by instant. You could take a sheet of squared paper, colour in a first configuration and simulate the process - except at the edge of the sheet, because in your experiment, it is not infinite. This type of process where the state of one cell changes according to its neighbours is known as a cellular automaton; the most famous example is the fascinating Game of Life, developed by the British mathematician John Horton Conway. Cellular automata can be found in numerous models: the formation of patterns on shells, the composition of a flock of birds, the evolution of road traffic, etc. Each time, the actors all change according to information from their immediate neighbours. So it is not surprising to find them in the situation we are studying here.
Why use Toom’s cellular automata? Because it has interesting properties to obtain global information. Let us colour in each cell randomly in blue or white; more concretely, each cell is coloured blue with the same probability of 0.49 (so there should be as many blue cells as white) and let the automate run. At some moment, the configuration where all cells are white will occur. Similarly, if the probability to be coloured blue was strictly greater than 1/2, at some moment we would have obtained a uniform blue configuration. The automaton solves the density classification problem: if, in your original colouring, one colour is slighty preferred, this will lead to a monochromatic configuration of the dominant colour.
This simple result was proven in 2013 by Ana Bušic, Nazim Fatès, Jean Mairesse and Irène Marcovici. The demonstration is based on the property, known as erosion, of Toom’s process; if initially there is only a finite number of cells of one colour, these will ultimately disppear. Indeed, from the first step on, the cells of this minority colour located at the top right-hand edge will disappear, because their neighbours to the right and above are the other colour. In the next step, the edge has moved back, and other cells disappear for the same reason. We see that the cells of the minority colour are gradually eclipsed until they disappear completely. The information can be obtained without centralising the data or doing a global count. This result is essential for designing the IT networks of today and tomorrow!
> AUTHOR
Roger Mansuy
Mathematician
Roger Mansuy teaches at Louis-Grand Lycée in Paris, and is a member of the French Committee for Maths Teaching (CFEM).
