Checking Global Graph Properties by Means of Local Computations: the Majority Problem

From MaRDI portal





One of the main characteristics of distributed systems is the local nature of the computation. A set of processors, connected in some specific way, try to reach a common goal (e.g. computing some function) after a finite number of elementary steps, each involving solely a subset of ``near processors. In this framework, the main question is to characterize those functions, that is those global properties of the network, that can be computed by means of local transformations in the network. In this paper we investigate that question by using a computational model based on graph relabelling systems. We are mostly interested in the following paradigm, called the majority problem, which is an abstraction that underlies a variety of distributed computation problems on graphs : let \(A\) and \(B\) be any two labels, \(G\) be a graph whose vertices are labelled on \(\{A,B\}\), \(|G|_A\) (resp. \(|G|_B\)) be the number of vertices of \(G\) labelled with \(A\) (resp. with \(B\)). To what extent are we able to compare the quantities \(|G|_A\) and \(|G|_B\)? We prove that using such graph recognizers we can decide whether \(|G|_A>|G|_B\), \(|G|_B>|G|_A\) or \(|G|_A =|G|_B\). Then, using the notion of \(k\)-covering, we prove that it is not possible to decide whether \(|G|_A =|G|_B + m\) for any \(m>0\). For the entire collection see [Zbl 0903.00060].











This page was built for publication: Checking Global Graph Properties by Means of Local Computations: the Majority Problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4222809)