Weitere Kapitel dieses Buchs durch Wischen aufrufen
We study 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.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 Angluin et al. (Distrib Comput 21:87–102, 2008), where its performance has been analyzed for the clique graph. In particular, we study the performance of this protocol in arbitrary networks, under the probabilistic scheduler. We prove that, when the two initial states are put uniformly at random on the vertices, the protocol of Angluin et al. (Distrib Comput 21:87–102, 2008) converges to the initial majority with probability higher than the probability of converging to the initial minority. In contrast, we show that the resistance of the protocol to failure when the underlying graph is a clique causes the failure of the protocol in general graphs.
This abstract paper is based on our work which appeared in the Proceedings of the 41-st International Colloquium on Automata, Languages, and Programming (ICALP) in 2014.
Bitte loggen Sie sich ein, um Zugang zu diesem Inhalt zu erhalten
Sie möchten Zugang zu diesem Inhalt erhalten? Dann informieren Sie sich jetzt über unsere Produkte:
D. Angluin, J. Aspnes, Z. Diamadi, M.J. Fischer, and R. Peralta, “Computation in networks of passively mobile finite-state sensors”, Distributed Computing18 (2006), 235–253.
D. Angluin, J. Aspnes, and D. Eisenstat, “A simple population protocol for fast robust approximate majority”, Distributed Computing21 (2008), 87–102.
J. Aspnes and E. Ruppert, “An introduction to population protocols”, in B. Garbinato, H. Miranda, and L. Rodrigues, editors, “Middleware for network eccentric and mobile applications”, Springer-Verlag (2009), 97–120.
M. Cook, D. Soloveichik, E. Winfree, and J. Bruck, “Programmability ofchemical reaction networks”, in A. Condon, D. Harel, J.N. Kok, A. Salomaa, and E. Winfree, editors, “Algorithmic Bioprocesses”, Natural Computing Series, Springer Berlin Heidelberg (2009), 543–584.
M.H. DeGroot, “Reaching a consensus”, Journal of the American Statistical Association69 (345) (1974), 118–121.
G. DeMarco and A. Pelc, “Randomized algorithms for determining the majority on graphs”, Combinatorics, Probability and Computing15 (6) (2006), 823–834.
M. Draief and M. Vojnovic, “Convergence speed of binary interval consensus”, SIAM Journal on control and Optimization50 (3) (2012), 1087–1109.
M. Fischer and H. Jiang, “Self-stabilizing leader election in networks of finite-state anonymous agents”, in “Proceedings of the 10-th International Conference on Principles of Distributed Systems (OPODIS)” (2006).
R.A. Holley and T.M. Liggett, “Ergodic theorems for weakly interacting infinite systems and the voter model”, The Annals of Probability3 (1975), 643–663.
M. Kearns and J. Tan, “Biased voting and the democratic primary problem”, in “Proceedings of the 4-th International Workshop on Internet and Network Economics (WINE)” (2008), 639–652.
T.G. Kurtz, “Approximation of population processes”, Society for Industrial and Applied Mathematics, Philadelphia, PA, USA (1987).
L. Lamport, R. Shostak, and M. Pease, “The byzantine generals problem”, ACM Trans. Program. Lang. Syst.4 (3) (1982), 382–401.
T.M. Liggett, “Interacting particle systems”, Springer-Verlag, New York/Berlin/Heidelberg/ Tokyo (2004).
G.B. Merzios, S.E. Nikoletseas, C.L. Raptopoulos, and P.G. Spirakis, “Determining majority in networks with local interactions and very small local memory”, in “Proceedings of the 41-st International Colloquium on Automata, Languages, and Programming” 1 (2014), 871–882.
A. Mizrachi, “Majority vote and monopolies in social networks”, Master’s thesis, Department of Communication Systems Engineering, Faculty of Engineering, Ben-Gurion University of the Negev (2013).
P.A.P. Moran, “Random processes in genetics”, Mathematical Proceedings of the Cambridge Philosophical Society54 (1) (1958), 60–71.
E. Mossel, J. Neeman, and O. Tamuz, “Majority dynamics and aggregation of information in social networks”, Autonomous Agents and Multi-Agent Systems28 (3) (2014), 408–429.
E. Perron, D. Vasudevan, and M. Vojnovic, “Using three states for binary consensus on complete graphs”, in “Proceedings of the 28-th IEEE International Conference on Computer Communications (INFOCOM)” (2009), 2527–2535.
F.P. Preparata, G. Metze, and R.T. Chien, “On the connection assignment problem of diagnosable systems”, IEEE Transactions on Electronic Computers16 (1967), 848–854.
M. Saks and M. Werman, “On computing majority by comparisons”, Combinatorica11 (4) (1991), 383–387.
- Population Protocols for Majority in Arbitrary Networks
George B. Mertzios
Sotiris E. Nikoletseas
Christoforos L. Raptopoulos
Paul G. Spirakis
Neuer Inhalt/© ITandMEDIA, Product Lifecycle Management/© Eisenhans | vege | Fotolia