Delay Optimization in Quorum Consensus |
| |
Authors: | Email author" target="_blank">Xuemin?LinEmail author |
| |
Affiliation: | (1) School of Computer Science and Engineering, The University of New South Wales, Sydney, NSW 2052, Australia |
| |
Abstract: | The management of replicated data in distributed database systems is a classic problem with great
practical importance. Quorum consensus is one of the popular methods, combined with eager replication, for
managing replicated data. In this paper we investigate the problems of delay-optimal quorum consensus.
Firstly, we show that the problem of minimizing the total delay (or mean delay) restricted to a ring can be
solved in a constant time in contrast to the existing approximation results. Secondly, we show that the problem
of minimizing the total delay (or mean delay) is NP-hard. Thirdly, we present an approximate algorithm with
an approximate ratio 2; and the approximate algorithm can guarantee the exact solutions for some specific
network topology, such as trees and meshes. Finally, we present an improvement on the existing algorithm
to solve the problem of minimizing the maximal delay; this reduces the time complexity from O(n
3 log n) to
O(n
3) where n is the number of nodes. |
| |
Keywords: | Quorum consensus Replicated data management Optimizations |
本文献已被 SpringerLink 等数据库收录! |
|