Publications by Fernando Pedone

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

Distributed computing is reshaping the way people think about and do daily life activities. On-line ticket reservation, electronic commerce, and telebanking are examples of services that would be hardly imaginable without distributed computing. Nevertheless, widespread use of computers has some implications. As we become more depend on computers, computer malfunction increases in importance. Until recently, discussions about fault tolerant computer systems were restricted to very specific contexts, but this

Atomic broadcast primitives are often proposed as a mechanism to allow fault-tolerant cooperation between sites in a distributed system. Unfortunately, the delay incurred before a message can be delivered makes it difficult to implement high performance, scalable applications on top of atomic broadcast primitives. Recently, a new approach has been proposed for atomic broadcast which, based on optimistic assumptions about the communication system, reduces the average delay for message delivery to the applica

Replication is an area of interest to both distributed systems and databases. The solutions developed from these two perspectives are conceptually similar but differ in many aspects: model, assumptions, mechanisms, guarantees provided, and implementation. In this paper, we provide an abstract and ``neutral'' framework to compare replication techniques from both communities in spite of the many subtle differences. The framework has been designed to emphasize the role played by different mechanisms and to fac

Replication is an area of interest to both distributed systems and databases. The solutions developed from these two perspectives are conceptually similar but differ in many aspects: model, assumptions, mechanisms, guarantees provided, and implementation. In this paper, we provide an abstract and ``neutral'' framework to compare replication techniques from both communities. The framework has been designed to emphasize the role played by different mechanisms and to facilitate comparisons. The paper describes

Database replication protocols have historically been built on top of distributed database systems, and have consequently been designed and implemented using distributed transactional mechanisms, such as atomic commitment. We present the Database State Machine approach, a new way to deal with database replication in a cluster of servers. This approach relies on a powerful atomic broadcast primitive to propagate transactions between database servers, and alleviates the need for atomic commitment. Transaction

Database replication protocols have historically been built on top of distributed database systems, and have consequently been designed and implemented using distributed transactional mechanisms, such as atomic commitment. We present the database state machine approach, a new way to deal with database replication in a cluster of servers. This approach relies on a powerful atomic broadcast primitive to propagate transactions between database servers, and no atomic commitment is necessary. Transaction commit

Transaction Reordering in Replicated Databases F.Pedone, R.Guerraoui and A.Schiper This paper presents a fault-tolerant lazy replication protocol that ensures 1-copy serializability at a relatively low cost. Unlike eager replication approaches, our protocol enables local transaction execution and does not lead to any deadlock situation. Compared to previous lazy replication approaches, we significantly reduce the abort rate of transactions and we do not require any reconciliation procedure. Our protocol fir

Agreement problems, such as consensus, atomic broadcast, and group membership, are central to the implementation of fault-tolerant distributed systems. Despite the diversity of algorithms that have been proposed for solving agreement problems in the past years, almost all solutions are crash detection based (CDB). We say that an algorithm is CDB if it uses some information about the status crashed/not crashed of processes. Randomized consensus algorithms are rare exceptions non-CDB algorithms. In this paper

Resource location is a fundamental problem for large-scale distributed applications. This paper discusses the problem from a probabilistic perspective. Contrary to deterministic approaches, which strive to produce a precise outcome, probabilistic approaches may sometimes expose users with incorrect results. The paper formalizes the probabilistic resource-location problem with the notion of probabilistic queries. A probabilistic query has a predicate as parameter and returns a set of sites where the predicat

Exploiting Atomic Broadcast in Replicated Databases F.Pedone, R.Guerraoui and A.Schiper Database replication protocols have historically been built on top of distributed database systems, and have consequently been designed and implemented using distributed transactional mechanisms, such as atomic commitment. We argue in this paper that this approach is not always adequate to efficiently support database replication and that more suitable alternatives, such as atomic broadcast primitives, should be employed

Atomic broadcast primitives allow fault-tolerant cooperation between sites in adistributed system. Unfortunately, the delay incurred before a message can be delivered makes it difficult to implement high performance, scalable applications on top of atomic broadcast primitives. Recently, a new approach has been proposed which, based on optimistic assumptions about the communication system, reduces the average delay for message delivery. In this paper, we develop this idea further and present a replicated dat

This paper establishes tight lower bounds on the time complexity of algorithms solving the generic broadcast problem. Generic broadcast assumes a symmetric, non-reflexive conflict relation on the set of messages, and requires ordered delivery only for conflicting messages. The lower bounds established in this paper relate the resilience of generic broadcast algorithms (i.e., the total number of failures f the algorithms can tolerate) to their time complexity in runs in which oracles are not used. The paper

Message ordering is a fundamental abstraction in distributed systems. However, usual ordering guarantees are purely syntactic'', that is, message semantics'' is not taken into consideration, despite the fact that in several cases semantic information about messages leads to more efficient message ordering protocols. In this paper we define the Generic Broadcast problem, which orders the delivery of messages only if needed, based on the semantics of the messages. Semantic information about the messages i

Data replication is an increasingly important topic as databases are more and more deployed over clusters of workstations. One of the challenges in database replication is to introduce replication without severely affecting performance. Because of this difficulty, current database products use lazy replication, which is very efficient but can compromise consistency. As an alternative, eager replication guarantees consistency but most existing protocols have a prohibitive cost. In order to clarify the curren

On Transaction Liveness in Replicated Databases F.Pedone and R.Guerraoui This paper makes a first attempt to give a precise characterisation of liveness in replicated database systems. We introduce the notion of liveness degrees, which express the expectation a database user might have about the termination of the transactions, despite concurrency and failures. Our liveness degrees are complementary to the traditional transactional safety degrees (e.g., serializability) and lead to a better characterisation

Database replication protocols based on group communication primitives have recently emerged as a promising technology to improve database fault-tolerance and performance. Roughly speaking, this approach consists in exploiting the order and atomicity properties provided by group communication primitives or, more specifically atomic broadcast, to guarantee transaction properties. This paper proposes a systematic classification of non voting database replication algorithms based on atomic broadcast.

Optimistic atomic broadcast: a pragmatic viewpoint F.Pedone and A.Schiper This paper presents the Optimistic Atomic Broadcast algorithm (OPT-ABcast) which exploits the spontaneous total-order property experienced in local-area networks in order to allow fast delivery of messages. The OPT-ABcast algorithm is based on a sequence of stages, and messages can be delivered during a stage or at the end of a stage. During a stage, processes deliver messages fast. Whenever the spontaneous total-order property does n

Fernando Pedone

Chat with Graph Search

The database state machine and group communication issues

Using Optimistic Atomic Broadcast in Transaction Processing Systems

Using Optimistic Atomic Broadcast in Transaction Processing Systems

Understanding Replication in Databases and Distributed Systems

Understanding replication in databases and distributed systems

The Database State Machine Approach

The Database State Machine Approach

Transaction Reordering in Replicated Databases

Solving Agreement Problems with Weak Ordering Oracles

Transaction Reordering in Replicated Databases

Probabilistic Queries in Large-Scale Networks

Exploiting Atomic Broadcast in Replicated Databases

Exploiting Atomic Broadcast in Replicated Databases

Processing Transactions over Optimistic Atomic Broadcast Protocols

Lower Bounds on Generic Broadcast Algorithms

Generic Broadcast

Database Replication Techniques: a three parameter classification

On Transaction Liveness in Replicated Databases

A Systematic Classification of Replicated Database Protocols based on Atomic Broadcast

Optimistic atomic broadcast: a pragmatic viewpoint