Informatics Seminar on Wednesday, April 30 at 14.00 - Dr. Rodrigo Schmidt
Decanato - Facoltà di scienze informatiche
Data d'inizio: 30 Aprile 2008
Data di fine: 1 Maggio 2008
The Faculty of Informatics is pleased to announce a seminar given by Dr. Rodrigo Schmidt
TITLE: Deferred-Update Database Replication: Theory and Algorithms
SPEAKER: Dr. Rodrigo Schmidt
DATE: Wednesday, April 30th, 2008
PLACE: USI Università della Svizzera italiana, room SI-006, Informatics building (Via G. Buffi 13)
TIME: 14.00-15.00
ABSTRACT:
This work 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. We study how we can 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.
We make 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.
BIOGRAPHY:
Dr. Rodrigo Schmidt has recently finished his Ph.D. in Computer and Communication Sciences at EPFL, Switzerland. His research focuses on distributed algorithms for distributed transactions, state-machine replication, and group communication.
