Object Allocation in Distributed Databases and Mobile Computers.

@inproceedings{DBLP:conf/icde/HuangW94,
  author    = {Yixiu Huang and
               Ouri Wolfson},
  title     = {Object Allocation in Distributed Databases and Mobile Computers},
  booktitle = {Proceedings of the Tenth International Conference on Data Engineering,
               February 14-18, 1994, Houston, Texas, USA},
  publisher = {IEEE Computer Society},
  year      = {1994},
  isbn      = {0-8186-5400-7},
  pages     = {20-29},
  ee        = {db/conf/icde/HuangW94.html},
  crossref  = {DBLP:conf/icde/94},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

This paper makes two contributions. First, we introduce a model for evaluating the performance of data allocation and replication algorithms in distributed databases. The model is comprehensive in the sense that it accounts for I/O cost, for communication cost, and for limits on the minimum number of copies of the object (to ensure availability).

The second contribution of this paper is the introduction and analysis of an algorithm for automatic dynamic allocation of replicas to processors. Using the new model, we compare the performance of the traditional read-one-write-all static allocation algorithm, to the performance of the dynamic allocation algorithm. As a result, we obtain the relationship between the communication cost and I/O cost for which static allocation is superior to dynamic allocation, and the relationships for which dynamic allocation is superior.

Keywords: object allocation, distributed database, mobile computing, wireless communication, competitiveness, caching.

Copyright © 1994 by The Institute of Electrical and Electronic Engineers, Inc. (IEEE). Abstract used with permission.

ACM SIGMOD Anthology

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• Mac: Click here
• UNIX/LINUX: mount the CD and click on the path of your mount point:
  /Anthology/An2-6 or /cdrom

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• Mac: Click here
• UNIX/LINUX: mount the DVD and click on the path of your mount point:
  /Anthology/aDVD1 or /dvd

Printed Edition

References

[1]

Anant Agarwal, Richard Simoni, John L. Hennessy, Mark Horowitz: An Evaluation of Directory Schemes for Cache Coherence. ISCA 1988: 280-289

[2]

James K. Archibald, Jean-Loup Baer: Cache Coherence Protocols: Evaluation Using a Multiprocessor Simulation Model. ACM Trans. Comput. Syst. 4(4): 273-298(1986)

[3]

Yair Bartal, Amos Fiat, Yuval Rabani: Competitive Algorithms for Distributed Data Management (Extended Abstract). STOC 1992: 39-50

[4]

John K. Bennett, John B. Carter, Willy Zwaenepoel: Adaptive Software Cache Management for Distributed Shared Memory Architectures. ISCA 1990: 125-134

[5]

John K. Bennett, John B. Carter, Willy Zwaenepoel: Munin: Distributed Shared Memory Based on Type-Specific Memory Coherence. PPOPP 1990: 168-176

[6]

Philip A. Bernstein, Vassos Hadzilacos, Nathan Goodman: Concurrency Control and Recovery in Database Systems. Addison-Wesley 1987, ISBN 0-201-10715-5
Contents

[7]

B. R. Badrinath, Tomasz Imielinski: Replication and Mobility. Workshop on the Management of Replicated Data 1992: 9-12

[8]

Michael J. Carey, Michael J. Franklin, Miron Livny, Eugene J. Shekita: Data Caching Tradeoffs in Client-Server DBMS Architectures. SIGMOD Conference 1991: 357-366

[9]

Lawrence W. Dowdy, Derrell V. Foster: Comparative Models of the File Assignment Problem. ACM Comput. Surv. 14(2): 287-313(1982)

[10]

Susan J. Eggers, Randy H. Katz: A Characterization of Sharing in Parallel Programs and Its Application to Coherency Protocol Evaluation. ISCA 1988: 373-382

[11]

Susan J. Eggers, Randy H. Katz: Evaluating the Performance of Four Snooping Cache Coherency Protocols. ISCA 1989: 2-15

[12]

Derek L. Eager, Kenneth C. Sevcik: Achieving Robustness in Distributed Database Systems. ACM Trans. Database Syst. 8(3): 354-381(1983)

[13]

Amos Fiat, Richard M. Karp, Michael Luby, Lyle A. McGeoch, Daniel Dominic Sleator, Neal E. Young: Competitive Paging Algorithms. J. Algorithms 12(4): 685-699(1991)

[14]

David K. Gifford: Weighted Voting for Replicated Data. SOSP 1979: 150-162

[15]

Tomasz Imielinski, B. R. Badrinath: Querying in Highly Mobile Distributed Environments. VLDB 1992: 41-52

[16]

Anna R. Karlin, Mark S. Manasse, Larry Rudolph, Daniel Dominic Sleator: Competitive Snoopy Caching. Algorithmica 3: 77-119(1988)

[17]

Yixiu Huang, Ouri Wolfson: A Competitive Dynamic Data Replication Algorithm. ICDE 1993: 310-317

[18]

James J. Kistler, Mahadev Satyanarayanan: Disconnected Operation in the Coda File System. ACM Trans. Comput. Syst. 10(1): 3-25(1992)

[19]

...

[20]

Kai Li, Paul Hudak: Memory Coherence in Shared Virtual Memory Systems. ACM Trans. Comput. Syst. 7(4): 321-359(1989)

[21]

Joonwon Lee, Umakishore Ramachandran: Synchronization with Multiprocessor Caches. ISCA 1990: 27-37

[22]

...

[23]

Mark S. Manasse, Lyle A. McGeoch, Daniel Dominic Sleator: Competitive Algorithms for On-line Problems. STOC 1988: 322-333

[24]

Mahadev Satyanarayanan, James J. Kistler, Puneet Kumar, Maria E. Okasaki, Ellen H. Siegel, David C. Steere: Coda: A Highly Available File System for a Distributed Workstation Environment. IEEE Trans. Computers 39(4): 447-459(1990)

[25]

Robert H. Thomas: A Majority Consensus Approach to Concurrency Control for Multiple Copy Databases. ACM Trans. Database Syst. 4(2): 180-209(1979)

[26]

Ouri Wolfson, Amir Milo: The Multicast Policy and Its Relationship to Replicated Data Placement. ACM Trans. Database Syst. 16(1): 181-205(1991)

[27]

Ouri Wolfson, Sushil Jajodia: Distributed Algorithms for Dynamic Replication of Data. PODS 1992: 149-163

[28]

Ouri Wolfson, Sushil Jajodia: An Algorithm for Dynamic Data Distribution. Workshop on the Management of Replicated Data 1992: 62-65

[29]

Yongdong Wang, Lawrence A. Rowe: Cache Consistency and Concurrency Control in a Client/Server DBMS Architecture. SIGMOD Conference 1991: 367-376