---
_id: '16496'
abstract:
- lang: eng
  text: We present a general framework for the development of on-line algorithms for
    data management in networks with limited memory capacities. These algorithms dynamically
    create and delete copies of shared data objects that can be read and written by
    the nodes in the network. Our algorithms aim to minimize the congestion, i.e.,
    the maximum communication load over all network resources, so that that none of
    these resources become a communication bottleneck. We give several examples of
    networks for which our framework yields efficient algorithms, including meshes,
    fat-trees, hypercubic networks, and complete networks. For example, our framework
    yields an $O(d cdot log n)$-competitive caching algorithm for $d$-dimensional
    meshes of size $n$ with respect to the congestion on the communication links,
    and an $O(1)$-competitive algorithms for complete networks with respect to the
    congestion at the memory modules due to remote accesses. Previous work on data
    management in networks either neglects memory capacity constraints or minimizes
    only the total communication load, i.e., the sum of the communication load over
    all resources, which may produce congestion as some of the links become bottlenecks.
author:
- first_name: Friedhelm
  full_name: Meyer auf der Heide, Friedhelm
  id: '15523'
  last_name: Meyer auf der Heide
- first_name: Berthold
  full_name: Vöcking, Berthold
  last_name: Vöcking
- first_name: Matthias
  full_name: Westermann, Matthias
  last_name: Westermann
citation:
  ama: 'Meyer auf der Heide F, Vöcking B, Westermann M. Caching in networks. In: <i>SODA
    ’00: Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms</i>.
    ; 2000:430–439.'
  apa: 'Meyer auf der Heide, F., Vöcking, B., &#38; Westermann, M. (2000). Caching
    in networks. In <i>SODA ’00: Proceedings of the eleventh annual ACM-SIAM symposium
    on Discrete algorithms</i> (pp. 430–439).'
  bibtex: '@inproceedings{Meyer auf der Heide_Vöcking_Westermann_2000, title={Caching
    in networks}, booktitle={SODA ’00: Proceedings of the eleventh annual ACM-SIAM
    symposium on Discrete algorithms}, author={Meyer auf der Heide, Friedhelm and
    Vöcking, Berthold and Westermann, Matthias}, year={2000}, pages={430–439} }'
  chicago: 'Meyer auf der Heide, Friedhelm, Berthold Vöcking, and Matthias Westermann.
    “Caching in Networks.” In <i>SODA ’00: Proceedings of the Eleventh Annual ACM-SIAM
    Symposium on Discrete Algorithms</i>, 430–439, 2000.'
  ieee: 'F. Meyer auf der Heide, B. Vöcking, and M. Westermann, “Caching in networks,”
    in <i>SODA ’00: Proceedings of the eleventh annual ACM-SIAM symposium on Discrete
    algorithms</i>, 2000, pp. 430–439.'
  mla: 'Meyer auf der Heide, Friedhelm, et al. “Caching in Networks.” <i>SODA ’00:
    Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms</i>,
    2000, pp. 430–439.'
  short: 'F. Meyer auf der Heide, B. Vöcking, M. Westermann, in: SODA ’00: Proceedings
    of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2000, pp. 430–439.'
date_created: 2020-04-09T13:16:15Z
date_updated: 2022-01-06T06:52:51Z
department:
- _id: '63'
language:
- iso: eng
page: 430–439
publication: 'SODA ''00: Proceedings of the eleventh annual ACM-SIAM symposium on
  Discrete algorithms'
publication_identifier:
  isbn:
  - '0898714532'
status: public
title: Caching in networks
type: conference
user_id: '15415'
year: '2000'
...