---
_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: SODA
’00: Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms.
; 2000:430–439.'
apa: 'Meyer auf der Heide, F., Vöcking, B., & Westermann, M. (2000). Caching
in networks. In SODA ’00: Proceedings of the eleventh annual ACM-SIAM symposium
on Discrete algorithms (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 SODA ’00: Proceedings of the Eleventh Annual ACM-SIAM
Symposium on Discrete Algorithms, 430–439, 2000.'
ieee: 'F. Meyer auf der Heide, B. Vöcking, and M. Westermann, “Caching in networks,”
in SODA ’00: Proceedings of the eleventh annual ACM-SIAM symposium on Discrete
algorithms, 2000, pp. 430–439.'
mla: 'Meyer auf der Heide, Friedhelm, et al. “Caching in Networks.” SODA ’00:
Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms,
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'
...