Dynamic hybrid replication effectively combining tree and grid topology
Tóm tắt
Effective data management is an important issue in a large-scale distributed environment such as distributed DBMS, Peer-to-Peer System (P2P), data grid, and World Wide Web (WWW). This can be achieved by using a replication protocol, which efficiently decrease the communication cost and increase the data availability. The Tree Quorum protocol is one of the representative replication protocols allowing low read cost in the best case but it has some drawbacks such as that the number of replicas grows rapidly as the level increases and root replica is a bottleneck. The Grid protocol requires fixed operation cost regardless of failure condition. In this paper we propose a new replication protocol called Dynamic Hybrid protocol, which efficiently improves the existing protocols. The proposed protocol effectively combines the grid and tree structure so that the overall topology can be flexibly adjusted using three configuration parameters; tree height, number of descendants and grid depth. For high read availability, the height of tree and number of descendants are decreased and depth of grid is increased. For high write availability, the height of tree and the depth of grid are decreased, while the number of descendant is increased. We present an analytical model of read/write availability and the average number of nodes accessed for each operation. We also employ computer simulation to estimate the throughput and communication overhead. The proposed protocol always allows much smaller communication and operation cost than earlier protocols.
Tài liệu tham khảo
Amza C, Cox AL, Zwaenepoel W (2000) Data replication strategies for fault tolerance and availability on commodity clusters. In: Proc int’l conf on dependable systems and networks (DSN), pp 459–467
Goel S, Buyya R (2006) Data replication strategies in wide area distributed systems. In: Qiu RG (ed) Enterprise service computing: from concept to deployment. Idea Group Inc, Hershey, pp 211–241. ISBN 1-599044181-2
Arai K, Tanaka K, Takizawa M (2000) Group protocol for quorum-based replication. In: Proc int’l conf on parallel and distributed systems, pp 57–64
Alonso G (1997) Partial database replication and group communication primitives. In: Proc the 2nd European research seminar on advances in distributed systems (ERSADS’97), pp 171–176
Ahmad N, Abdalla AN, Sidek RM (2010) Data replication using read-one-write-all monitoring synchronization transaction system in distributed environment. J Comput Sci 6(10):1066–1069
Saha D, Rangarajan S, Tripathi SK (1996) An analysis of the average message overhead in replica control protocols. IEEE Trans Parallel Distrib Syst 7(10):1026–1034
Storm C, Warns T (2008) Deriving highly available quorum systems from structural failure models. In: Proc int’l conf on European dependable computing conference (EDCC), pp 56–65
Osrael J, Froihofer L, Chlaupek N, Goeschka KM (2007) Availability and performance of the adaptive voting replication. In: Proc int’l conf on availability, reliability and security (ARES), pp 53–60
Oprea F, Reiter MK (2007) Minimizing response time for quorum-system protocols over wide-area networks. In: Proc int’l conf on dependable systems and networks (DSN), pp 409–418
Sawai Y, Shinohara M, Kanzaki A, Hara T, Nishio S (2006) Consistency management among replicas using a quorum system in ad hoc networks. In: Proc int’l conf on mobile data management (MDM), pp 128–132
Frain I, M’zoughi A, Bahsoun JP (2006) How to achieve high throughput with dynamic tree-structured coterie. In: Proc int’l symposium on parallel and distributed computing (ISPDC), pp 82–89
Latip R, Ibrahim H, Othman M, Sulaiman MN, Abdullah A (2008) Quorum based data replication in grid environment, rough sets and knowledge technology. Lecture notes in computer science, pp 379–386
Liskov B, Rodrigues R (2006) Tolerating byzantine faulty clients in a quorum system. In: Proc int’l conf on distributed computing systems (ICDCS), pp 34–43
Sawai Y, Shinohara M, Kanzaki A, Hara T, Nishio S (2007) Quorum based consistency management among replicas in ad hoc networks with data update. In: Proc int’l symposium on applied computing (SAC) of ACM, pp 955–956
Baldoni R, Jimenez-Peris R, Patino-Martinez M, Querzoni L, Virgil-lito A (2005) Dynamic quorums for DHT-based P2P networks. In: Proc int’l symposium on network computing and applications (NCA), pp 91–100
Zhou W, Holmes R (1999) The design and simulation of a hybrid replication control protocol. In: Proc int’l symposium on parallel architectures, algorithms, and networks (I-SPAN), pp 210–215
McNab R, Howell FW (1996) Using java for discrete event simulation. In: Proc on twelfth UK computer and telecommunications performance engineering workshop (UKPEW), pp 219–228
Howell F, McNab R (1998) simjava: a discrete event simulation package for Java with applications in computer systems modeling. In: Proc int’l conf on web-based modelling and simulation, pp 55–64
Lee YJ, Kim HY, Lee CH (2009) Cell approximation method in quorum systems for minimizing access time. Cluster Comput 12(4):378–398
Arai M, Suzuki T, Ohara M, Fukumoto S, Iwasaki K, Youn HY (2004) Analysis of read and write availability for generalized hybrid data replication protocol. In: Proc int’l symposium on Pacific Rim dependable computing (PRDC), pp 143–150
Jiménez-peris R, Patiño-martínez M, Alonso G, Kemme B (2003) Are quorums an alternative for data replication. ACM Trans Database Syst 28(3):257–294
Bhagwan R, Moore D, Savage S, Voelker G (2003) Replication strategies for highly available peer-to-peer storage. In: Proc int’l conf on future directions in distributed computing (FuDiCo), pp 153–158
Saito Y, Shapiro M (2005) Optimistic replication. Comput Surv 37(1):42–81
Klan D, Sattler K, Hose K, Karnstedt M (2008) Decentralized managing of replication objects in massively distributed systems. In: Proc int’l workshop on data management in peer-to-peer systems, pp 19–26
Storm C, Theel O (2009) A general approach to analyzing quorum-based heterogeneous dynamic data replication schemes. In: Proc int’l conf on distributed computing and networking, pp 349–361
Henry K, Swanson C, Xie Q, Daudjee K (2009) Efficient hierarchical quorums in unstructured peer-to-peer networks. In: Proc int’l conf on cooperative information systems (CoopIS), pp 183–200
Iakab KK, Storm C, Theel O (2010) Consistency-driven probabilistic quorum system construction for improving operation availability. In: Proc int’l conf on distributed computing and networking, pp 446–458