Distributed Probabilistic Polling and Applications to Proportionate Agreement |
| |
Authors: | Yehuda Hassin David Peleg |
| |
Affiliation: | Department of Computer Science and Applied Mathematics, The Weizmann Institute of Science, Rehovot, 76100, Israelf1;Department of Computer Science and Applied Mathematics, The Weizmann Institute of Science, Rehovot, 76100, Israel, f2 |
| |
Abstract: | This paper considers a probabilistic local polling process, examines its properties, and proposes its use in the context of distributed network protocols for achieving consensus. The resulting consensus algorithm is very simple and lightweight, yet it enjoys some desirable properties, such as proportionate agreement (namely, reaching a consensus value of one with probability proportional to the number of ones in the inputs), resilience against dynamic link failures and recoveries, and (weak) self-stabilization. The paper also investigates the maximum influence of small sets and establishes results analogous to those obtained for the problem in the deterministic polling model. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|