The optimal location of replicas in a network using a READ-ONE-WRITE-ALL policy. (English) Zbl 1448.68040
Summary: We consider the problem of locating replicas in a network to minimize communications costs. Under the assumption that the read-one-write-all policy is used to ensure data consistency, an optimization problem is formulated in which the cost function estimates the total communications costs. The paper concentrates on the study of the optimal communications cost as a function of the ratio between the frequency of the read and write operations. The problem is reformulated as a zero-one linear programming problem, and its connection to the \(p\)-median problem is explained. The general problem is proved to be NP-complete. For path graphs a dynamic programming algorithm for the problem is presented.
MSC:
| 68M10 | Network design and communication in computer systems |
| 68Q17 | Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) |
| 90C90 | Applications of mathematical programming |
References:
| [1] | Dowdy LW, Foster DV: Comparative models ofthe file assignment problem. ACM Computing Surveys 14(2): 287-313 (1982) |
| [2] | Erkut E, Francis RL, Lowe TJ, TamirA: Equivalent mathematical programming formulations of monotonic tree network location problems. Oper. Res. (USA) 37(3): 447-461 (1989) · Zbl 0674.90020 |
| [3] | Fisher ML, Hochbaum DS: Database location in computer networks. Journal ofACM 27(4): 718-735 (1980) · Zbl 0445.68071 |
| [4] | Frederickson GN: Parametric search and locating supply centers in trees. Proc. WADS’91, Workshop on Algorithms and Data Structures (August 1991, Ottawa, ON), Lecture Notes in Computer Science, vol 519, Springer, 1991, pp 299-319 · Zbl 0764.68069 |
| [5] | Garcia-Molina H: The future of data replication. Proc. IEEE Symposium on Reliability in Distributed Software and Database Systems (January 1986, Los Angeles, CA), pp 13-19 |
| [6] | Garey MR, Johnson DS: Computers and intractability. W.H. Freeman and Company, 1979 · Zbl 0411.68039 |
| [7] | Gifford DK: Weighted voting for replicated data. Proc. ACM SOSP’79, Symposium on Operating Systems Principles |
| [8] | Hakimi SL, Schmeichel EF: Locating replicas ofa database on a network. Networks 30(1): 31-36 (1997) · Zbl 0878.90025 |
| [9] | Huang Y, Sistla P, Wolfson O: Data replication for mobile computers. Proc. ACM SIGMOD’94, International Conference on Management ofData (May 1994, Minneapolis, MN), pp 13-24 |
| [10] | Kariv O, Hakimi SL: An algorithmic approach to network location problems. I: The p-centers. SIAM J. Appl. Math. 37(3): 513-538 (1979) · Zbl 0432.90074 |
| [11] | Kariv O, Hakimi SL: An algorithmic approach to network location problems. II: The p-medians. SIAM J. Appl. Math. 37(3): 539-560 (1979) · Zbl 0432.90075 |
| [12] | Kemme B, Alonso G: A suite ofdatabase replication protocols based on group communication primitives. Proc. IEEE ICDCS’98, International Conference on Distributed Computing Systems (May 1998, Amsterdam, The Netherlands), pp 156-163 |
| [13] | Mahmoud S: Private communication. (January 2001) |
| [14] | Milo A, Wolfson O: Placement of replicated items in distributed databases. Proc. EDBT’88, International Conference on Extending Database Technology. Lecture Notes in Computer Science 303, pp 414-427, Berlin Heidelberg New York: Springer 1988 |
| [15] | Mirchandani PB, Francis RL (Eds): Discrete location theory. New York: Wiley 1990 · Zbl 0718.00021 |
| [16] | Pressman IS, Cook SA, Pachl J: The optimal placement ofreplicas in a network using a read any – write all policy. Proc. IBM CASCON’92 (November 1992, Toronto, ON), vol II, pp 189- 201 |
| [17] | Wolfson O, Jajodia S, Huang Y: An adaptive data replication algorithm. ACM Transactions on Database Systems 22(4): 255- 314 (1997) |
| [18] | Wolfson O, Jajodia S: Distributed algorithms for dynamic replication ofdata. Proc. ACM PODS’92, Symposium on Principles ofDatabase Systems (June 1992, San Diego, CA), pp 149-163 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
