Distributed Probabilistic Polling and Applications to Proportionate Agreement

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 propor...

Full description

Saved in:
Bibliographic Details
Published in:Information and computation 2001-12, Vol.171 (2), p.248-268
Main Authors: Hassin, Yehuda, Peleg, David
Format: Article
Language:English
Subjects:
Algorithmics. Computability. Computer arithmetics
Applied sciences
Computer science
control theory
systems
Exact sciences and technology
Flows in networks. Combinatorial problems
Operational research and scientific management
Operational research. Management science
Portfolio theory
Theoretical computing
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0890-5401
1090-2651
DOI:10.1006/inco.2001.3088