|
| | | | |
| | | |
| Stat |
Members: 3645
Articles: 2'504'928
Articles rated: 2609
25 April 2024 |
|
| | | | |
|
Article overview
| |
|
|
Towards Robust and Efficient Computation in Dynamic Peer-to-Peer Networks | | John Augustine
; Gopal Pandurangan
; Peter Robinson
; Eli Upfal
; | | Date: |
3 Aug 2011 | | Abstract: | Motivated by the need for robust and fast distributed computation in highly
dynamic Peer-to-Peer (P2P) networks, we study algorithms for the fundamental
distributed agreement problem. P2P networks are highly dynamic networks that
experience heavy node {em churn} (i.e., nodes join and leave the network
continuously over time). Our main contributions are randomized distributed
algorithms that guarantee {em stable almost-everywhere agreement} with high
probability even under high adversarial churn in polylogarithmic number of
rounds. In particular, we present the following results:
1. An $O(log^2 n)$-round ($n$ is the stable network size) randomized
algorithm that achieves almost-everywhere agreement with high probability under
up to {em linear} churn {em per round} (i.e., $epsilon n$, for some small
constant $epsilon > 0$), assuming that the churn is controlled by an oblivious
adversary (has complete knowledge and control of what nodes join and leave and
at what time and has unlimited computational power, but is oblivious to the
random choices made by the algorithm).
2. An $O(log mlog^3 n)$-round randomized algorithm that achieves
almost-everywhere agreement with high probability under up to $epsilon
sqrt{n}$ churn per round (for some small $epsilon > 0$), where $m$ is the
size of the input value domain, that works even under an adaptive adversary
(that also knows the past random choices made by the algorithm).
Our algorithms are the first-known, fully-distributed, agreement algorithms
that work under highly dynamic settings (i.e., high churn rates per step).
Furthermore, they are localized (i.e., do not require any global topological
knowledge), simple, and easy to implement. These algorithms can serve as
building blocks for implementing other non-trivial distributed computing tasks
in dynamic P2P networks. | | Source: | arXiv, 1108.0809 | | Services: | Forum | Review | PDF | Favorites | |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
browser Mozilla/5.0 AppleWebKit/537.36 (KHTML, like Gecko; compatible; ClaudeBot/1.0; +claudebot@anthropic.com)
|
| |
|
|
|
|
News, job offers and information for researchers and scientists:
| |
REGISTER