|
| | | | |
| | | |
| Stat |
Members: 3645
Articles: 2'504'928
Articles rated: 2609
25 April 2024 |
|
| | | | |
|
Article overview
| |
|
|
Storage and Search in Dynamic Peer-to-Peer Networks | | John Augustine
; Anisur Rahaman Molla
; Ehab Morsy
; Gopal Pandurangan
; Peter Robinson
; Eli Upfal
; | | Date: |
6 May 2013 | | Abstract: | We study robust and efficient distributed algorithms for searching, storing,
and maintaining data in dynamic Peer-to-Peer (P2P) networks. P2P networks are
highly dynamic networks that experience heavy node churn (i.e., nodes join and
leave the network continuously over time). Our goal is to guarantee, despite
high node churn rate, that a large number of nodes in the network can store,
retrieve, and maintain a large number of data items. Our main contributions are
fast randomized distributed algorithms that guarantee the above with high
probability (whp) even under high adversarial churn:
1. A randomized distributed search algorithm that (whp) guarantees that
searches from as many as $n - o(n)$ nodes ($n$ is the stable network size)
succeed in ${O}(log n)$-rounds despite ${O}(n/log^{1+delta} n)$ churn, for
any small constant $delta > 0$, per round. We assume that the churn is
controlled by an oblivious adversary (that has complete knowledge and control
of what nodes join and leave and at what time, but is oblivious to the random
choices made by the algorithm).
2. A storage and maintenance algorithm that guarantees (whp) data items can
be efficiently stored (with only $Theta(log{n})$ copies of each data item)
and maintained in a dynamic P2P network with churn rate up to
${O}(n/log^{1+delta} n)$ per round. Our search algorithm together with our
storage and maintenance algorithm guarantees that as many as $n - o(n)$ nodes
can efficiently store, maintain, and search even under ${O}(n/log^{1+delta}
n)$ churn per round. Our algorithms require only polylogarithmic in $n$ bits to
be processed and sent (per round) by each node.
To the best of our knowledge, our algorithms are the first-known,
fully-distributed storage and search algorithms that provably work under highly
dynamic settings (i.e., high churn rates per step). | | Source: | arXiv, 1305.1121 | | 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