Publications by André Schiper

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.

We consider the problem of bootstrapping self-organized mobile ad hoc networks (MANET), i.e. reliably determining in a distributed and self- organized manner the services to be offered by each node when neither the identity nor the number of the nodes in the network is initially available. To this means we define a variant of the traditional consensus problem, by relaxing the requirement for the set of participating processes to be known by all at the beginning of the computation. This assumption captures t

The Swiss Exchange system (SWX system) was the first stock exchange system in service to be fully computerised. For high availability, the trading system is built as a replicated service based on Isis. For portability reasons, the SWX team has considered basing the next version of the trading system on CORBA. Despite the numerous advantages of a CORBA based solution, it was necessary not only to meet the functionality requirements of the system, but also to evaluate the performance of the chosen middleware.

The traditional architecture used by implementations of Replicated State Machines (RSM) does not fully exploit modern multi-core CPUs. This is increasingly the limiting factor in their performance, because network speeds are increasing much faster than the ...

Distributed computing is one of the major trends in the computer industry. As systems become more distributed, they also become more complex and have to deal with new kinds of problems, such as partial crashes and link failures. While many middleware architectures have emerged to answer the growing demand in distributed technologies, most of them do not provide any kind of fault tolerance mechanisms. In this paper, we discuss the addition of object group support to CORBA. We describe three approaches: integ

State machine replication is becoming an increasingly popular technique among online services to ensure fault-tolerance using commodity hardware. This has led to a renewed interest in its throughput, as these services have typically a large number of users. Recent work has shown how to improve the throughput of the replication protocol, using techniques like Ring-topologies, IP multicast, and rotating leaders. When deployed in modern fast networks, the resulting systems achieve unprecedented levels of throu

Consensus is at the heart of fault-tolerant distributed computing systems. Much research has been devoted to developing algorithms for this particular problem. This paper presents a semi-automatic verification approach for asynchronous consensus algorithms ...

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

Control in distributed systems is mainly introduced to reduce nondeterminism. This nondeterminism is due on the one hand to the asynchronous execution of the processes located on the various sites of the system, and on the other hand to the asynchronous nature of the communication channels. In order to limit the asynchronism due to communication channels, a new message ordering relation, known as causal ordering, has been introduced by Birman and Joseph. After giving some examples of this causal ordering, w

This paper focuses on the design of an asynchronous broadcast primitive on the Intel SCC. Our solution is based on OC-Bcast, a state-of-the-art k-ary tree synchronous broadcast algorithm that leverages the parallelism provided by on-chip Remote Memory Acce ...

Problems in fault-tolerant distributed computing have been studied in a variety of models. These models are structured around two central ideas: Degree of synchrony and failure model are two independent parameters that determine a particular type of system. The notion of faulty component is helpful and even necessary for the analysis of distributed computations when failures occur. In this work, we question these two basic principles of fault-tolerant distributed computing, and show that it is both possible

Due to their nature, distributed systems are vulnerable to failures of some of their parts. Conversely, distribution also provides a way to increase the fault tolerance of the overall system. However, achieving fault tolerance is not a simple problem and requires complex techniques. An agreement problem known as the problem of consensus is at the heart of most problems encountered during the design of a fault tolerant system. This problem is however not solvable in the asynchronous system model, unless the

In previous work, it has been shown how to solve atomic broadcast by reduction to consensus on messages. While this solution is theoretically correct, it has its limitations in practice, since executing consensus on large messages can quickly saturate the system. The problem can be addressed by executing consensus on message identifiers instead of the full messages, in order to decouple the size of the messages from the size of the data sent by the consensus algorithm. In this paper, we study the impact of

Group communication is a programming abstraction that allows a distributed group of processes to provide a reliable service in spite of the possibility of failures within the group. The goal of the project was to improve the state of the art of group communication in several directions: protocol frameworks, group communication stacks, specification, verification and robustness. The paper discusses the results obtained.

Fault tolerance can be achieved in distributed systems by replication. However, Fischer, Lynch and Paterson have proven an impossibility result about consensus in the asynchronous system model. Similar impossibility results have been established for atomic broadcast and group membership, and should be as such relevant for implementations of a replicated service. However, the practical impact of these impossibility results is unclear. For instance, do they set limits to the robustness of a replicated server

We compare the consensus and uniform consensus problems in synchronous systems. In contrast to consensus, uniform consensus is not solvable with byzantine failures. This still holds for the omission failure model if a majority of processes may be faulty. For the crash failure model, both consensus and uniform consensus are solvable, no matter how many processes are faulty. In this failure model, we examine the number of rounds required to reach a decision in the consensus and uniform consensus algorithms. W

In this paper, we study dynamic protocol update (DPU). Contrary to local code updates on-the-fly, DPU requires global coordination of local code replacements. We propose a novel solution to DPU. The key idea is to add a level of indirection between the ser ...

As the level of parallelism in manycore processors keeps increasing, providing efficient mechanisms for thread synchronization in concurrent programs is becoming a major concern. On cache-coherent shared-memory processors, synchronization efficiency is ult ...

Replication is a powerful technique for increasing availability of a distributed service. Algorithms for replicating distributed services do however face a dilemma: they should be (1) efficient (low latency), while (2) ensuring consistency of the replicas, which are two contradictory goals. The paper concentrates on active replication, where all the replicas handle the clients' requests. Active replication is usually implemented using the Atomic Broadcast primitive. To be efficient, some Atomic Broadcast al

André Schiper

Chat with Graph Search

Consensus with Unknown Participants or Fundamental Self-Organization

Highly Available Trading System: Experiments with CORBA

Achieving high-throughput State Machine Replication in multi-core systems

Replication of CORBA Objects

Achieving high-throughput State Machine Replication in multi-core systems

Verification of consensus algorithms using satisfiability solving

Using Optimistic Atomic Broadcast in Transaction Processing Systems

Using Optimistic Atomic Broadcast in Transaction Processing Systems

The causal ordering abstraction and a simple way to implement it

Asynchronous Broadcast on the Intel SCC using Interrupts

The Heard-Of Model: Computing in Distributed Systems with Benign Failures

Failure Detectors: implementation issues and impact on consensus performance

Solving Atomic Broadcast with Indirect Consensus

Advances in the Design and Implementation of Group Communication Middleware

Chasing the FLP Impossibility Result in a LAN or How Robust Can a Fault Tolerant Server Be?

Uniform consensus is harder than consensus

Structural and Algorithmic Issues of Dynamic Protocol Update

Leveraging Hardware Message Passing for Efficient Thread Synchronization

Optimistic Active Replication

Optimistic active replication