An Optimal Voting Scheme for Minimizing the Overall Communication Cost in Replicated Data Management
✍ Scribed by Xuemin Lin; Maria E. Orlowska
- Publisher
- Elsevier Science
- Year
- 1996
- Tongue
- English
- Weight
- 248 KB
- Volume
- 35
- Category
- Article
- ISSN
- 0743-7315
No coin nor oath required. For personal study only.
✦ Synopsis
add sites one by one to S r i (S w i ) until the sum of votes in S r i (S w i ) not less than Q r (Q w ).
• Each read (write) operation should obtain permission from each site in S r i (S w i ).
If a two-phase locking mechanism is applied, a basic QC method will force, through the intersection invariants, the situation that a write and a read cannot take place simultaneously on different copies of the same data, and neither can two writes. Thus, mutual consistency can be maintained.
To resolve the limitations of a basic QC method, several other QC methods [1, 10, 3] have been proposed. Moreover, to make each site bear equal responsibility for a read and a write, a number of distributed QC approaches [14,15] have been proposed. Those distributed QC approaches are based on a technique of coteries [5,7,8]. A recent research trend in developing new distributed QC approaches is to couple high data availability [15,16,13] with a low ''communication'' cost (to be defined in Section 2). Consequently, in a very reliable network, we should put our emphasis on reducing communication costs.
In this paper, we discuss only a basic QC method. Further, we restrict our interests in a static environment, that is, votes and quorum sizes are fixed a priori. The interested readers may refer to [6,9] for detailed discussions about dynamic QC methods.
In the rest of the paper, a basic QC method will be referred to as a BSQC method. A BSQC method is also called majority voting method in the literature if all v i are the same. Otherwise, it is named a weighted voting method. A weighted voting method can potentially provide some benefits to matching the user requirements at each site, and then to reducing communication costs.
In a recent paper [11], Kumar and Segev show a tradeoff between overall communication costs and data availabilities. Several optimization problems have been proposed in [11], as well as various optimization algorithms. Further, the problem of finding a BSQC method to minimize the overall communication cost for processing typical demands of transactions has been taken into account. However, without forcing the output to meet those data availability