Mertzios, G.B. and Nikoletseas, S. and Raptopoulos, C. and Spirakis, P.G. (2014) 'Determining majority in networks with local interactions and very small local memory.', in Automata, languages, and programming : 41st international colloquium, ICALP 2014, Copenhagen, Denmark, July 8-11, 2014, proceedings, part I. Berlin, Heidelberg: Springer, pp. 871-882. Lecture notes in computer science. (8572).
We study here the problem of determining the majority type in an arbitrary connected network, each vertex of which has initially two possible types (states). 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, i.e. its output function must interpret the local state of each vertex so that each vertex outputs the initial majority type. We first provide a protocol with 4 states per vertex that always computes the initial majority value, under any fair scheduler. Under the uniform probabilistic scheduler of pairwise interactions, we prove that our protocol stabilizes in expected polynomial time for any network and is quite fast on the clique. As we prove, this protocol is optimal, in the sense that there does not exist any 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 (whp). To this end, we examine an elegant and very natural majority protocol with 3 states per vertex, introduced in  where its performance has been analyzed for the clique graph. In particular, it determines the correct initial majority type in the clique very fast and whp under the uniform probabilistic scheduler. 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, the protocol of  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 of  can fail, i.e. it can converge to the initial minority type whp, even when the difference between the initial majority and the initial minority is n − Θ(ln n). We also present another infinite family of graphs in which the protocol of  takes an expected exponential time to converge. These two negative results build upon a very positive result concerning the robustness of the protocol of  on the clique, namely that if the initial minority is at most n7, the protocol fails with exponentially small probability. 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:||Book chapter|
|Full text:||(AM) Accepted Manuscript|
Download PDF (181Kb)
|Publisher Web site:||http://dx.doi.org/10.1007/978-3-662-43948-7_72|
|Publisher statement:||The final publication is available at Springer via http://dx.doi.org/10.1007/978-3-662-43948-7_72|
|Date accepted:||No date available|
|Date deposited:||17 September 2014|
|Date of first online publication:||2014|
|Date first made open access:||No date available|
Save or Share this output
|Look up in GoogleScholar|