Determining majority in networks with local interactions and very small local memory

Mertzios, George B, Nikoletseas, Sotiris E, Raptopoulos, Christoforos L and Spirakis, Paul G ORCID: 0000-0001-5396-3749 (2017) Determining majority in networks with local interactions and very small local memory. Distributed Computing, 30 (1). pp. 1-16.

Text Majority_19-03-15.pdf - Author Accepted Manuscript Download (453kB)

Abstract

We study here the problem of determining the majority type in an arbitrary connected network, each vertex of which has initially two possible types. The vertices may have a few additional possible states and can interact in pairs only if they share an edge. Any (population) protocol is required to stabilize in the initial majority. We first present and analyze a protocol with 4 states per vertex that always computes the initial majority value, under any fair scheduler. As we prove, this protocol is optimal, in the sense that there is no population protocol that always computes majority with fewer than 4 states per vertex. However this does not rule out the existence of a protocol with 3 states per vertex that is correct with high probability. To this end, we examine a very natural majority protocol with 3 states per vertex, introduced in [Angluin et al. 2008] where its performance has been analyzed for the clique graph. We study the performance of this protocol in arbitrary networks. We prove that, when the two initial states are put uniformly at random on the vertices, this protocol converges to the initial majority with probability higher than the probability of converging to the initial minority. In contrast, we present an infinite family of graphs, on which the protocol can fail whp, even when the difference between the initial majority and the initial minority is n−Θ(lnn). We also present another infinite family of graphs in which the protocol of Angluin et al. takes an expected exponential time to converge. These two negative results build upon a very positive result concerning the robustness of the protocol on the clique. Surprisingly, the resistance of the clique to failure causes the failure in general graphs. Our techniques use new domination and coupling arguments for suitably defined processes whose dynamics capture the antagonism between the states involved.

Item Type:	Article
Uncontrolled Keywords:	majority in networks, population protocol, probabilistic scheduler, coupling
Depositing User:	Symplectic Admin
Date Deposited:	09 Feb 2017 14:06
Last Modified:	19 Jan 2023 07:19
DOI:	10.1007/s00446-016-0277-8
Related URLs:	Author Publisher
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3005678

Available Versions of this Item

• Determining Majority in Networks with Local Interactions and very Small Local Memory. (deposited 09 Jun 2016 09:23)
  • Determining majority in networks with local interactions and very small local memory. (deposited 09 Feb 2017 14:06) [Currently Displayed]