000114790 001__ 114790
000114790 005__ 20190509132157.0
000114790 0247_ $$2doi$$a10.5075/epfl-thesis-4022
000114790 02470 $$2urn$$aurn:nbn:ch:bel-epfl-thesis4022-9
000114790 02471 $$2nebis$$a5498781
000114790 037__ $$aTHESIS
000114790 041__ $$aeng
000114790 088__ $$a4022
000114790 245__ $$btheory and algorithms$$aDeferred-update database replication
000114790 269__ $$a2008
000114790 260__ $$bEPFL$$c2008$$aLausanne
000114790 300__ $$a227
000114790 336__ $$aTheses
000114790 502__ $$aMarcos Aguilera, Benoît Garbinato, André Schiper
000114790 520__ $$aThis thesis is about the design of high-performance fault-tolerant computer systems. More specifically, it focuses on how to develop database systems that behave correctly and with good performance even in the event of failures. Both performance and dependability can be improved by means of the same technique, namely replication. If several database replicas are available, performance can be improved by distributing the load among them. Moreover, if one of the replicas cannot be accessed due to failures, users can still rely on the other ones. However, providing the interface of a single database system out of several replicas is not an easy task since one has to ensure they are always consistent with each other. Allowing replicas to diverge would easily break the illusion of having a single high-performance fault-tolerant database system. Although we would like to have replicas as independent of each other as possible for performance and dependability reasons, we must keep them synchronized if we want to provide a consistent interface to users. In this work, we study how we can balance this trade-off to provide good performance and fault-tolerance without compromising consistency. Our basis is a widely used technique for database replication known as the deferred update technique. In this technique, transactions are initially executed in a single replica. Passive transactions, which do not change the state of the database, can commit locally to the replica they execute. Active transactions, which change the database state, must be synchronized with the transactions running on other replicas. This thesis makes four major contributions. First, we introduce an abstract specification that generalizes the deferred update technique. This specification provides a strong model to prove lower bounds on replication algorithms, design new correct-by-construction protocols tailor-made for specific settings, and prove existing protocols correct more easily, in a standard way. Using this model, we show that the problem of termination of active transactions in deferred-update protocols is highly related to the problem of sequence agreement among a set of processes. In this context, we study the problem of implementing latency-optimal fault-tolerant solutions to sequence agreement and present a novel, highly-dynamic, algorithm that can quickly adapt to system changes in order to preserve its optimal latency. Our algorithm is based on a new agreement problem we introduce that seems to be more suitable to solve problems like sequence agreement than previously used abstractions. Our last two contributions are in the context of specific deferred-update algorithms, where we present two new fault-tolerant protocols derived from our general abstraction. The first algorithm uses no extra assumptions about database replicas. Yet, it has very little overhead associated with the termination of active transactions, propagating only strictly necessary information to replicas. Our second protocol uses strong assumptions about the concurrency control mechanism used by database replicas to reduce even more the latency and the burden associated with transaction termination. These algorithms are good examples of how our general abstraction can be extended to create new protocols and prove them correct.
000114790 6531_ $$adistributed systems
000114790 6531_ $$afault tolerance
000114790 6531_ $$acrash-recovery
000114790 6531_ $$adeferred-update replication
000114790 6531_ $$aserializability
000114790 6531_ $$asequence agreement
000114790 6531_ $$aconsensus
000114790 6531_ $$aPaxos
000114790 6531_ $$acollision-fast
000114790 6531_ $$ain-memory databases
000114790 6531_ $$atransaction termination
000114790 6531_ $$asystèmes distribués
000114790 6531_ $$atolérance aux fautes
000114790 6531_ $$atechnique de mise à jour différée
000114790 6531_ $$aconsistance
000114790 6531_ $$aaccord de séquence
000114790 6531_ $$aconsensus
000114790 6531_ $$aPaxos
000114790 6531_ $$acollision
000114790 6531_ $$abase des données en mémoire
000114790 6531_ $$aterminaison de transactions
000114790 700__ $$0(EPFLAUTH)163030$$g163030$$aMalta Schmidt, Rodrigo
000114790 720_2 $$aZwaenepoel, Willy$$edir.$$g155705$$0243160
000114790 720_2 $$aPedone, Fernando$$edir.
000114790 8564_ $$uhttps://infoscience.epfl.ch/record/114790/files/EPFL_TH4022.pdf$$zTexte intégral / Full text$$s1120525$$yTexte intégral / Full text
000114790 909C0 $$xU10700$$0252226$$pLABOS
000114790 909CO $$pthesis-bn2018$$pDOI$$pIC$$ooai:infoscience.tind.io:114790$$qDOI2$$qGLOBAL_SET$$pthesis
000114790 918__ $$dEDIC2005-2015$$bIC-SIN$$cIIF$$aIC
000114790 919__ $$aLABOS
000114790 920__ $$b2008$$a2008-3-7
000114790 970__ $$a4022/THESES
000114790 973__ $$sPUBLISHED$$aEPFL
000114790 980__ $$aTHESIS