Abstract
This paper deals with the on-line allocation of shared data objects to the local memory modules of the nodes in a network. We assume that the data is organized in indivisible objects such as files, pages, or global variables. The data objects can be replicated and discarded over time in order to minimize the communication load for read and write accesses done by the nodes in the network. Non-uniform data management is characterized by a different communication load for accesses to small pieces of the data objects and migrations of whole data objects.
We introduce on-line algorithms that minimize the congestion, i.e., the maximum communication load over all links. Our algorithms are evaluated in a competitive analysis comparing the congestion produced by an on-line algorithm with the congestion produced by an optimal off-line algorithm.We present the first deterministic and distributed algorithm that achieves a constant competitive ratio on trees. Our algorithm minimizes not only the congestion but minimizes simultaneously the load on each individual edge up to a optimal factor of 3.
Algorithms for trees are of special interest as they can be used as a subroutine in algorithms for other networks. For example, using our tree algorithm as a subroutine in the recently introduced “access tree strategy” yields an algorithm that is O(d · logn)-competitive for d-dimensional meshes with n nodes. This competitive ratio is known to be optimal for meshes of constant dimension.
F. Meyer auf der Heide and M. Westermann are supported in part by DFG-Sonderforschungsbereich 376 and EU ESPRIT Long Term Research Project 20244 (ALCOM-IT). B. Vöcking is supported by a grant of the “Gemeinsames Hochschulsonderprogramm III von Bund und Ländern” through the DAAD.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Y. Bartal, A. Fiat, and Y. Rabani. Competitive algorithms for distributed data management. In Proc. of the 24th ACM Symp. on Theory of Computing (STOC), pages 39–50, 1992.
S. Ben-David, A. Borodin, R. M. Karp, G. Tardos, and A. Widgerson. On the power of randomization in online algorithms. In Proc. of the 22th ACM Symp. on Theory of Computing (STOC), pages 386–379, 1992.
D. L. Black and D. D. Sleator. Competitive algorithms for replication and migration problems. Technical Report CMU-CS-89-201, Department of Computer Science, Carnegie-Mellon University, 1989.
C. Krick, F. Meyer auf der Heide, H. Räcke, B. Vöcking, and M. Westermann. Data management in networks: Experimental evaluation of a provably good strategy. In Proc. of the 11th ACM Symp. on Parallel Algorithms and Architectures (SPAA), 1999.
C. Krick, H. Räcke, B. Vöcking, and M. Westermann. The DIVA (Distributed Variables) Library. University of Paderborn, http://www.uni-paderborn.de/sfb376/a2/diva.html, 1998.
C. Lund, N. Reingold, J. Westbrook, and D. Yan. On-line distributed data management. In Proc. of the 2nd European Symposium on Algorithms (ESA), 1996.
B. M. Maggs, F. Meyer auf der Heide, B. Vöcking, and M. Westermann. Exploiting locality for networks of limited bandwidth. In Proc. of the 38th IEEE Symp. on Foundations of Computer Science (FOCS), pages 284–293, 1997.
D. D. Sleator and R. E. Tarjan. Amortized efficiency of list update and paging rules. Communication of the ACM, 28(2):202–208, 1985.
B. Vöcking. Static and Dynamic Data Management in Networks. PhD thesis, University of Paderborn, Germany, 1998.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1999 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
auf der Heide, F.M., Vöcking, B., Westermann, M. (1999). Provably Good and Practical Strategies for Non-uniform Data Management in Networks. In: Nešetřil, J. (eds) Algorithms - ESA’ 99. ESA 1999. Lecture Notes in Computer Science, vol 1643. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-48481-7_9
Download citation
DOI: https://doi.org/10.1007/3-540-48481-7_9
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-66251-8
Online ISBN: 978-3-540-48481-3
eBook Packages: Springer Book Archive