Distributed random digraph transformations for peer-to-peer networks

P. Mahlmann, C. Schindelhauer, in: Proceedings of the Eighteenth Annual ACM Symposium on Parallelism in Algorithms and Architectures  - SPAA ’06, 2006, pp. 308--317.

Download
No fulltext has been uploaded.
Conference Paper | Published | English
Author
;
Abstract
We study the problem of designing an adaptive hash table for redundant data storage in a system of storage devices with arbitrary capacities. Ideally, such a hash table should make sure that (a) a storage device with x% of the available capacity should get x% of the data, (b) the copies of each data item are distributed among the storage devices so that no two copies are stored at the same device, and (c) only a near-minimum amount of data replacements is necessary to preserve (a) and (b) under any change in the system. Hash tables satisfying (a) and (c) are already known, and it is not difficult to construct hash tables satisfying (a) and (b). However, no hash table is known so far that can satisfy all three properties as long as this is in principle possible. We present a strategy called SPREAD that solves this problem for the first time. As long as (a) and (b) can in principle be satisfied, SPREAD preserves (a) for every storage device nearly optimal, with high probability, guarantees (b) for every data item, and only needs a constant factor more data replacements than minimum possible in order to preserve (a) and (b).
Publishing Year
Proceedings Title
Proceedings of the eighteenth annual ACM symposium on Parallelism in algorithms and architectures - SPAA '06
Page
308--317
ISBN
LibreCat-ID

Cite this

Mahlmann P, Schindelhauer C. Distributed random digraph transformations for peer-to-peer networks. In: Proceedings of the Eighteenth Annual ACM Symposium on Parallelism in Algorithms and Architectures  - SPAA ’06. ; 2006:308--317. doi:10.1145/1148109.1148162
Mahlmann, P., & Schindelhauer, C. (2006). Distributed random digraph transformations for peer-to-peer networks. In Proceedings of the eighteenth annual ACM symposium on Parallelism in algorithms and architectures  - SPAA ’06 (pp. 308--317). https://doi.org/10.1145/1148109.1148162
@inproceedings{Mahlmann_Schindelhauer_2006, title={Distributed random digraph transformations for peer-to-peer networks}, DOI={10.1145/1148109.1148162}, booktitle={Proceedings of the eighteenth annual ACM symposium on Parallelism in algorithms and architectures  - SPAA ’06}, author={Mahlmann, Peter and Schindelhauer, Christian}, year={2006}, pages={308--317} }
Mahlmann, Peter, and Christian Schindelhauer. “Distributed Random Digraph Transformations for Peer-to-Peer Networks.” In Proceedings of the Eighteenth Annual ACM Symposium on Parallelism in Algorithms and Architectures  - SPAA ’06, 308--317, 2006. https://doi.org/10.1145/1148109.1148162.
P. Mahlmann and C. Schindelhauer, “Distributed random digraph transformations for peer-to-peer networks,” in Proceedings of the eighteenth annual ACM symposium on Parallelism in algorithms and architectures  - SPAA ’06, 2006, pp. 308--317.
Mahlmann, Peter, and Christian Schindelhauer. “Distributed Random Digraph Transformations for Peer-to-Peer Networks.” Proceedings of the Eighteenth Annual ACM Symposium on Parallelism in Algorithms and Architectures  - SPAA ’06, 2006, pp. 308--317, doi:10.1145/1148109.1148162.

Export

Marked Publications

Open Data LibreCat

Search this title in

Google Scholar
ISBN Search