research-article

Distributed Paging for General Networks

Authors:

Baruch Awerbuch,

Amos FiatAuthors Info & Claims

Journal of Algorithms, Volume 28, Issue 1

Pages 67 - 104

https://doi.org/10.1006/jagm.1998.0924

Published: 01 July 1998 Publication History

Abstract

Distributed pagingdeals with the dynamic allocation of copies of files in a distributed network as to minimize the total communication cost over a sequence of read and write requests.Most previous work deals with thefile allocationproblem, where infinite nodal memory capacity is assumed. In contrast the distributed paging problem makes the more realistic assumption that nodal memory capacity is limited. Former work on distributed paging deals with the problem only in the case of a uniform network topology.This paper gives the first distributed paging algorithm forgeneralnetworks. The algorithm is competitive in storage and communication. The competitive rates are poly-logarithmic in the total number of network nodes and the diameter of the network.

References

[1]

M. Ajtai, J. Aspnes, C. Dwork, O. Waarts, A theory of competitive analysis for distributed algorithms, October 1994.

[2]

B. Awerbuch, Y. Bartal, A. Fiat, Competitive distributed file allocation, May 1993.

[3]

B. Awerbuch, Y. Bartal, A. Fiat, Heat & dump: Randomized competitive distributed paging, IEEE, 1993.

[4]

Agarwal, Chaken, Johnson, Kranz, Kubiatowicz, Kurihara, Lim, Maa, Nussbaum, The mit-alewife machine: A large-scale distributed memory multiprocessor, Mit/lcs/tm 454, MIT, 1991

[5]

S. Albers, H. Koga, New on-line algorithms for the page replication problem, Aarhus, July 1994.

[6]

S. Albers, H. Koga, Page migration with limited local memory capacity, August 1995.

[7]

B. Awerbuch, D. Peleg, On-line tracking of mobile users, TM-410, Laboratory for Computer Science, MIT, August 1989

[8]

B. Awerbuch, D. Peleg, Sparse partitions, 1990.

[9]

B. Awerbuch, D. Peleg, Concurrent online tracking of mobile users, September 1991.

[10]

Y. Bartal, A. Fiat, Y. Rabani, Competitive algorithms for distributed data management, 1992.

[11]

A. Borodin, N. Linial, M. Saks, An optimal on-line algorithm for metrical task systems, May 1987.

[12]

D. L. Black, D. D. Sleator, Competitive algorithms for replication and migration problems, CMU-CS-89-201, Department of Computer Science, Carnegie-Mellon University, 1989

[13]

M. Chrobak, L. Larmore, N. Reingold, J. Westbrook, Optimal multiprocessor migration algorithms using work functions, Springer-Verlag, Hong Kong, 1993.

[14]

K.D. Cooper, Using compiler technology to drive advanced microprocessors, April 1992.

[15]

W.J. Dally, The J-machine: A fine-grain concurrent computer, North-Holland, Amsterdam, 1989.

[16]

D. Dowdy, D. Foster, Comparative models of the file assignment problem, Computing Surveys, 14 (1982).

[17]

A. Fiat, R. M. Karp, M. Luby, L. A. McGeoch, D. D. Sleator, N. E. Young, Competitive paging algorithms, Carnegie Mellon University, 1988

[18]

B. Gavish, O.R.L. Sheng, Dynamic file migration in distributed computer systems, Comm. ACM, 33 (1990) 177-189.

Digital Library

[19]

K. Johnson, The impact of communication locality on large-scale multiprocessor performance, IEEE, May 1992.

[20]

A. Karlin, M. Manasse, L. Rudolph, D. Sleator, Competitive snoopy caching, Algorithmica, 3 (1988) 77-119.

Digital Library

[21]

H. Koga, Randomized on-line algorithms for the page replication problem, Springer-Verlag, Hong Kong, 1993.

[22]

B. Liskov, Preliminary design of the thor object-oriented database system, April 1992.

[23]

L. Lenoski, J. Laundo, K. Gharachorloo, A. Gupta, J. Hennessy, The directory-based cache coherence protocol for the dash multiprocessor, 1990.

[24]

M. Lam, T.G. Moher, P. Wilson, Effective “static-graph” reorganization to improve locality in garbage-collected systems, June 1991.

[25]

C. Lund, N. Reingold, J. Westbrook, D. Yan, On-line distributed data management, 1994.

[26]

M.S. Lam, M.E. Wolf, Loop transformation theory and algorithm to maximize parallelism, IEEE Trans. Parallel and Distributed Systems (1991).

[27]

M.S. Lam, M.E. Wolf, Compilation techniques to achieve parallelism and locality, April 1992.

[28]

H.L. Morgan, K.D. Levin, Optimal program and data locations in computer networks, CACM, 20 (1988) 124-130.

[29]

M.S. Manasse, L.A. McGeoch, D.D. Sleator, Competitive algorithms for on-line problems, May 1988.

[30]

M. Palmer, S.B. Zdonik, Fodi: a cache that learns to fetch, Sept. 1991.

[31]

J.T. Robinson, M.V. Devarankonda, Data cache management using frequency-based replacement, May 1990.

[32]

P. Raghavan, M. Snir, Memory versus randomization in on-line algorithms, Springer-Verlag, Berlin/New York, 1989.

[33]

D.D. Sleator, R.E. Tarjan, Amortized efficiency of list update and paging rules, 1985.

[34]

J.W. Stamos, Static grouping of small objects to enhance performance of a paged virtual memory, ACM Trans. Computer Systems, 2 (1984) 155-180.

Digital Library

[35]

T. Kilburn, D. Edwards, M. Lanigan, F. Summer, One-level storage system, IRE Trans. Electronic Computers, 2 (1962) 223-235.

[36]

J. Westbrook, Randomized algorithms for multiprocessor page migration, Amer. Math. Soc, Providence, February 1991.

[37]

J. Westbrook, D.K. Yan, Greedy on-line Steiner tree and generalized Steiner problems, Springer-Verlag, Montréal, 1993.

[38]

N.E. Young, Competitive paging as cache size varies, January 1991.

[39]

W. Yongdong, L.A. Rowe, 1991.

Cited By

Qin TEtesami S(2021)Optimal Online Algorithms for File-Bundle Caching and Generalization to Distributed CachingACM Transactions on Modeling and Performance Evaluation of Computing Systems10.1145/34450286:1(1-23)Online publication date: 27-Mar-2021
https://dl.acm.org/doi/10.1145/3445028
Bienkowski MByrka JMucha M(2019)Dynamic Beats FixedACM Transactions on Algorithms10.1145/334029615:4(1-21)Online publication date: 25-Jul-2019
https://dl.acm.org/doi/10.1145/3340296
Matsubayashi A(2015)Asymptotically Optimal Online Page Migration on Three PointsAlgorithmica10.1007/s00453-013-9841-971:4(1035-1064)Online publication date: 1-Apr-2015
https://dl.acm.org/doi/10.1007/s00453-013-9841-9
Show More Cited By

Index Terms

Distributed Paging for General Networks
1. Software and its engineering
  1. Software organization and properties
    1. Contextual software domains
      1. Operating systems
        Communications management
2. Theory of computation
  1. Design and analysis of algorithms

Recommendations

Distributed paging and registration in wireless networks

The success of current and future wireless networks depends on their ability to provide connections to mobile terminals anywhere and at any time. It is therefore of crucial importance that wireless networks are able to quickly and efficiently locate ...
Analysis of paging in distributed architectures for 4G systems
IWCMC '07: Proceedings of the 2007 international conference on Wireless communications and mobile computing

As 3G wireless systems evolve towards 4G, various wireless network technology organizations looking at network architectures for 4G are considering a redesign of the network away from the traditional centralized, hierarchical design towards a more ...
IP Paging for Mobile Hosts in Distributed and Fixed Hierarchical Mobile IP

The concept of Paging has been found useful in existing cellular networks for mobile users with low call-to-mobility ratio CMR. It is necessary for fast mobility users to minimize the signaling burden on the network. Reduced signaling, also, conserves ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Journal of Algorithms

Journal of Algorithms Volume 28, Issue 1

July 1, 1998

196 pages

ISSN:0196-6774

Editors:
Zvi Galil
Columbia Univ., New York, NY
,
David S. Johnson
AT&T Bell Laboratories, Florham Park, NJ
,
Donald E. Knuth
Stanford Univ, Stanford, CA

Issue’s Table of Contents

Copyright © Academic Press.

Publisher

Academic Press, Inc.

United States

Publication History

Published: 01 July 1998

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

19
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 23 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Qin TEtesami S(2021)Optimal Online Algorithms for File-Bundle Caching and Generalization to Distributed CachingACM Transactions on Modeling and Performance Evaluation of Computing Systems10.1145/34450286:1(1-23)Online publication date: 27-Mar-2021
https://dl.acm.org/doi/10.1145/3445028
Bienkowski MByrka JMucha M(2019)Dynamic Beats FixedACM Transactions on Algorithms10.1145/334029615:4(1-21)Online publication date: 25-Jul-2019
https://dl.acm.org/doi/10.1145/3340296
Matsubayashi A(2015)Asymptotically Optimal Online Page Migration on Three PointsAlgorithmica10.1007/s00453-013-9841-971:4(1035-1064)Online publication date: 1-Apr-2015
https://dl.acm.org/doi/10.1007/s00453-013-9841-9
Borst SGupta VWalid A(2010)Distributed caching algorithms for content distribution networksProceedings of the 29th conference on Information communications10.5555/1833515.1833726(1478-1486)Online publication date: 14-Mar-2010
https://dl.acm.org/doi/10.5555/1833515.1833726
Li KShen YLin KQu W(2010)Coordinated multimedia object replacement in transcoding proxiesThe Journal of Supercomputing10.1007/s11227-009-0291-852:3(284-302)Online publication date: 1-Jun-2010
https://dl.acm.org/doi/10.1007/s11227-009-0291-8
Bienkowski MByrka JKorzeniowski MMeyer auf der Heide F(2009)Optimal algorithms for page migration in dynamic networksJournal of Discrete Algorithms10.1016/j.jda.2008.07.0067:4(545-569)Online publication date: 1-Dec-2009
https://dl.acm.org/doi/10.1016/j.jda.2008.07.006
Plaxton CSun YTiwari MVin H(2008)Online Compression CachingProceedings of the 11th Scandinavian workshop on Algorithm Theory10.1007/978-3-540-69903-3_37(414-425)Online publication date: 2-Jul-2008
https://dl.acm.org/doi/10.1007/978-3-540-69903-3_37
Li KShen HChin FZheng S(2005)Optimal methods for coordinated enroute web caching for tree networksACM Transactions on Internet Technology10.1145/1084772.10847745:3(480-507)Online publication date: 1-Aug-2005
https://dl.acm.org/doi/10.1145/1084772.1084774
Bienkowski MGibbons PSpirakis P(2005)Dynamic page migration with stochastic requestsProceedings of the seventeenth annual ACM symposium on Parallelism in algorithms and architectures10.1145/1073970.1074016(270-278)Online publication date: 18-Jul-2005
https://dl.acm.org/doi/10.1145/1073970.1074016
Bienkowski Mauf der Heide F(2005)Page migration in dynamic networksProceedings of the 30th international conference on Mathematical Foundations of Computer Science10.1007/11549345_1(1-14)Online publication date: 29-Aug-2005
https://dl.acm.org/doi/10.1007/11549345_1
Show More Cited By

View Options

View options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents