M.Sc Thesis | |

M.Sc Student | Arnon Hershkovitz |
---|---|

Subject | Extremal Problems for the Majority Action on Graphs |

Department | Department of Applied Mathematics |

Supervisor | Full Professors Holzman Ron |

The problem presented in this research is motivated by the common theme of overcoming failures in distributed networks. The main idea is to hold multiple copies of crucial data, polling the adjacent copies when an error occurred and taking the value held by most of them. This method is based on two main principles:

1. Locality - It is virtually impossible to poll the entire network, as networks enormously grow.

2. Rule of Majority - The assumption is that at today's technology level, the error probability is getting lower, so most of the copies will hold the correct value.

In this research, we
concentrate on the following question: what is the **minimal** size of a set
of components which, when holding the correct information - will distribute it
to the entire network? We look for a size that is independent of the structure
of the network, being a function of its size only.

Modeling the problem with graphs is straightforward: the components of the network are the vertices
and they are connected according to the network structure. A 0-1 coloring of
the vertices will denote the correctness of the data. The majority action M, is
then an operator on these colorings. If when a set of vertices U is initially
colored 1 and the rest of the vertices are colored 0, the majority action
results in the whole graph being colored 1 in one step - we say that U is a **static
monopoly**. If the majority action will color the whole graph 1 after some
finite number of steps - when the graph is colored in the beginning as
described above - we say that U is a **dynamic monopoly**.

We investigate the maximal size of minimal monopolies (both static and dynamic), where the maximum is taken over all connected graphs with a fixed number of vertices, as well as over certain families of graphs (trees, 3-regular graphs), and give upper and lower bounds. For that, we apply various techniques to handle the different families, and use the probabilistic method to handle the general case.