An O (log 3/2 n ) Parallel Time Population Protocol for Majority with O (log n ) States
| العنوان: | An O (log 3/2 n ) Parallel Time Population Protocol for Majority with O (log n ) States |
|---|---|
| المؤلفون: | Stav Ben-Nun, Ely Porat, Matan Kraus, Tsvi Kopelowitz |
| المصدر: | PODC Proceedings of the 39th Symposium on Principles of Distributed Computing |
| بيانات النشر: | ACM, 2020. |
| سنة النشر: | 2020 |
| مصطلحات موضوعية: | Combinatorics, education.field_of_study, Computer science, Population, Node (computer science), Population protocol, education, Binary logarithm, Protocol (object-oriented programming), Time cost, Majority problem, State transition function |
| الوصف: | In population protocols, the underlying distributed network consists of n nodes (or agents), denoted by V, and a scheduler that continuously selects uniformly random pairs of nodes to interact. When two nodes interact, their states are updated by applying a state transition function that depends only on the states of the two nodes prior to the interaction. The efficiency of a population protocol is measured in terms of both time (which is the number of interactions until the nodes collectively have a valid output) and the number of possible states of nodes used by the protocol. By convention, we consider the parallel time cost, which is the time divided by n. In this paper we consider the majority problem, where each node receives as input a color that is either black or white, and the goal is to have all of the nodes output the color that is the majority of the input colors. We design a population protocol that solves the majority problem in O(log3/2 n) parallel time, both with high probability and in expectation, while using O(log n) states. Our protocol improves on a recent protocol of Berenbrink et al. that runs in O(log5/3 n) parallel time, both with high probability and in expectation, using O(log n) states. |
| ردمك: | 978-1-4503-7582-5 |
| URL الوصول: | https://explore.openaire.eu/search/publication?articleId=doi_dedup___::871f66aa774e6a454787291dde62585d https://doi.org/10.1145/3382734.3405747 |
| حقوق: | OPEN |
| رقم الأكسشن: | edsair.doi.dedup.....871f66aa774e6a454787291dde62585d |
| قاعدة البيانات: | OpenAIRE |
| ردمك: | 9781450375825 |
|---|