--- _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' ...