Dr George Mertzios george.mertzios@durham.ac.uk
Associate Professor
Determining majority in networks with local interactions and very small local memory
Mertzios, G.B.; Nikoletseas, S.E.; Raptopoulos, C.L.; Spirakis, P.G.
Authors
S.E. Nikoletseas
C.L. Raptopoulos
P.G. Spirakis
Abstract
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 later change into other types, out of a set of a few additional possible types, and can interact in pairs only if they share an edge. Any (population) protocol is required to stabilize in the initial majority. First we prove that there does not exist any population protocol that always computes majority in any interaction graph by using at most 3 types per vertex. However this does not rule out the existence of a protocol with 3 types per vertex that is correct with high probability (whp). To this end, we examine an elegant and very natural majority protocol with 3 types per vertex, introduced in Angluin et al. (Distrib. Computing 21(2):87–102, 2008), whose 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, if the initial assignement of types to vertices is random, the protocol of Angluin et al. (Distrib. Computing 21(2):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.
Citation
Mertzios, G., Nikoletseas, S., Raptopoulos, C., & Spirakis, P. (2017). Determining majority in networks with local interactions and very small local memory. Distributed Computing, 30(1), 1-16. https://doi.org/10.1007/s00446-016-0277-8
Journal Article Type | Article |
---|---|
Acceptance Date | May 27, 2016 |
Online Publication Date | Jul 4, 2016 |
Publication Date | Feb 1, 2017 |
Deposit Date | Jun 12, 2016 |
Publicly Available Date | Mar 28, 2024 |
Journal | Distributed Computing |
Print ISSN | 0178-2770 |
Electronic ISSN | 1432-0452 |
Publisher | Springer |
Peer Reviewed | Peer Reviewed |
Volume | 30 |
Issue | 1 |
Pages | 1-16 |
DOI | https://doi.org/10.1007/s00446-016-0277-8 |
Files
Accepted Journal Article
(410 Kb)
PDF
Copyright Statement
The final publication is available at Springer via https://doi.org/10.1007/s00446-016-0277-8
You might also like
Graphs with minimum fractional domatic number
(2023)
Journal Article
Approximate and Randomized algorithms for Computing a Second Hamiltonian Cycle
(2023)
Journal Article
Sliding into the Future: Investigating Sliding Windows in Temporal Graphs
(2023)
Conference Proceeding
Fast parameterized preprocessing for polynomial-time solvable graph problems
(2023)
Journal Article
The complexity of computing optimum labelings for temporal connectivity
(2022)
Conference Proceeding
Downloadable Citations
About Durham Research Online (DRO)
Administrator e-mail: dro.admin@durham.ac.uk
This application uses the following open-source libraries:
SheetJS Community Edition
Apache License Version 2.0 (http://www.apache.org/licenses/)
PDF.js
Apache License Version 2.0 (http://www.apache.org/licenses/)
Font Awesome
SIL OFL 1.1 (http://scripts.sil.org/OFL)
MIT License (http://opensource.org/licenses/mit-license.html)
CC BY 3.0 ( http://creativecommons.org/licenses/by/3.0/)
Powered by Worktribe © 2024
Advanced Search