M.Sc Thesis
M.Sc Student Hershkovitz Arnon Extremal Problems for the Majority Action on Graphs Department of Applied Mathematics Professor Ron Holzman

Abstract

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.