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

From MaRDI portal

!

This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:

scientific article; zbMATH DE number 1231499
Language Label Description Also known as
default for all languages
No label defined
    English
    Checking Global Graph Properties by Means of Local Computations: the Majority Problem
    scientific article; zbMATH DE number 1231499

      Statements

      Checking Global Graph Properties by Means of Local Computations: the Majority Problem (English)
      0 references
      0 references
      0 references
      0 references
      13 December 1998
      0 references
      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].
      0 references

      Identifiers