---
_id: '19808'
abstract:
- lang: eng
  text: 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).
author:
- first_name: Peter
  full_name: Mahlmann, Peter
  last_name: Mahlmann
- first_name: Christian
  full_name: Schindelhauer, Christian
  last_name: Schindelhauer
citation:
  ama: 'Mahlmann P, Schindelhauer C. Distributed random digraph transformations for
    peer-to-peer networks. In: <i>Proceedings of the Eighteenth Annual ACM Symposium
    on Parallelism in Algorithms and Architectures  - SPAA ’06</i>. ; 2006:308--317.
    doi:<a href="https://doi.org/10.1145/1148109.1148162">10.1145/1148109.1148162</a>'
  apa: Mahlmann, P., &#38; Schindelhauer, C. (2006). Distributed random digraph transformations
    for peer-to-peer networks. In <i>Proceedings of the eighteenth annual ACM symposium
    on Parallelism in algorithms and architectures  - SPAA ’06</i> (pp. 308--317).
    <a href="https://doi.org/10.1145/1148109.1148162">https://doi.org/10.1145/1148109.1148162</a>
  bibtex: '@inproceedings{Mahlmann_Schindelhauer_2006, title={Distributed random digraph
    transformations for peer-to-peer networks}, DOI={<a href="https://doi.org/10.1145/1148109.1148162">10.1145/1148109.1148162</a>},
    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} }'
  chicago: Mahlmann, Peter, and Christian Schindelhauer. “Distributed Random Digraph
    Transformations for Peer-to-Peer Networks.” In <i>Proceedings of the Eighteenth
    Annual ACM Symposium on Parallelism in Algorithms and Architectures  - SPAA ’06</i>,
    308--317, 2006. <a href="https://doi.org/10.1145/1148109.1148162">https://doi.org/10.1145/1148109.1148162</a>.
  ieee: P. Mahlmann and C. Schindelhauer, “Distributed random digraph transformations
    for peer-to-peer networks,” in <i>Proceedings of the eighteenth annual ACM symposium
    on Parallelism in algorithms and architectures  - SPAA ’06</i>, 2006, pp. 308--317.
  mla: Mahlmann, Peter, and Christian Schindelhauer. “Distributed Random Digraph Transformations
    for Peer-to-Peer Networks.” <i>Proceedings of the Eighteenth Annual ACM Symposium
    on Parallelism in Algorithms and Architectures  - SPAA ’06</i>, 2006, pp. 308--317,
    doi:<a href="https://doi.org/10.1145/1148109.1148162">10.1145/1148109.1148162</a>.
  short: 'P. Mahlmann, C. Schindelhauer, in: Proceedings of the Eighteenth Annual
    ACM Symposium on Parallelism in Algorithms and Architectures  - SPAA ’06, 2006,
    pp. 308--317.'
date_created: 2020-09-30T13:07:55Z
date_updated: 2022-01-06T06:54:13Z
department:
- _id: '63'
doi: 10.1145/1148109.1148162
language:
- iso: eng
page: 308--317
publication: Proceedings of the eighteenth annual ACM symposium on Parallelism in
  algorithms and architectures  - SPAA '06
publication_identifier:
  isbn:
  - '1595934529'
publication_status: published
status: public
title: Distributed random digraph transformations for peer-to-peer networks
type: conference
user_id: '15415'
year: '2006'
...