Publications de André Schiper

Publications associées (57)

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

André Schiper, Nuno Filipe de Sousa Santos

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 ...

Ieee2013

Verification of consensus algorithms using satisfiability solving

André Schiper

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 ...

Springer Verlag2011

Asynchronous Broadcast on the Intel SCC using Interrupts

André Schiper, Thomas Ropars, Omid Shahmirzadi, Darko Petrovic

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 ...

2012

Structural and Algorithmic Issues of Dynamic Protocol Update

André Schiper, Olivier Rütti

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 ...

2006

Leveraging Hardware Message Passing for Efficient Thread Synchronization

André Schiper, Thomas Ropars, Darko Petrovic

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 ...

2014

High-Performance RMA-Based Broadcast on the Intel SCC

André Schiper, Thomas Ropars, Omid Shahmirzadi, Darko Petrovic

Many-core chips with more than 1000 cores are expected by the end of the decade. To overcome scalability issues related to cache coherence at such a scale, one of the main research directions is to leverage the message-passing programming model. The Intel ...

2012

Implementing Virtual Machine Replication: A Case Study using Xen and KVM

André Schiper, Darko Petrovic

Virtual machine (VM) replication has been recognized as an inexpensive way of providing high availability on commodity hardware. Unfortunately, its impact on system performance is far from negligible and strategies have been proposed to mitigate this probl ...

IEEE Computer Society Press2012

From Set Membership to Group Membership: A Separation of Concerns

André Schiper

We revisit the well-known group membership problem and show how it can be considered a special case of a simple problem, the set membership problem. In the set membership problem, processes maintain a set whose elements are drawn from an arbitrary universe ...

2006

Structured Derivation of Semi-Synchronous Algorithms

André Schiper, Martin Hutle, Zarko Milosevic, Fatemeh Borran

The semi-synchronous model is an important middle ground between the synchronous and the asynchronous models of distributed computing. In this model, processes can detect (timeout) when other processes fail. However, since detection is done by timing out, ...

2011

Assessing the Crash-Failure Assumption of Group Communication Protocols

André Schiper, Sergio Mena

Designing and correctly implementing Group Communication Systems (GCSs) is notoriously difficult. Assuming that processes fail only by crashing provides a powerful means to simplify the theoretical development of these systems. When making this assumption, ...

2005

Leveraging Hardware Message Passing for Efficient Thread Synchronization

André Schiper, Thomas Ropars, Darko Petrovic

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 ...

Assoc Computing Machinery2014

A Predicate-Based Approach to Dynamic Protocol Update in Group Communication

André Schiper, Olivier Rütti

In this paper we study dynamic protocol updates (DPU), which consist in replacing, without interruption, a given protocol during execution. We focus especially on group communication protocols. The paper proposes a methodology to conveniently describe whic ...

2008

Recovery Algorithms for Paxos-Based State Machine Replication

André Schiper, Nuno Filipe de Sousa Santos

In this article, we propose and evaluate three different state recovery algorithms aimed for Paxos-one of the most popular distributed agreement protocols. Paxos is commonly used to maintain consistency among state machine replicas despite of failures of p ...

IEEE COMPUTER SOC2021

Swift Algorithms for Repeated Consensus

André Schiper, Martin Hutle, Nuno Filipe de Sousa Santos, Fatemeh Borran

We introduce the notion of a swift algorithm. Informally, an algorithm that solves the repeated consensus is swift if, in a partial synchronous run of this algorithm, eventually no timeout expires, i.e., the algorithm execution proceeds with the actual spe ...

Ieee Computer Soc Press, Customer Service Center, Po Box 3014, 10662 Los Vaqueros Circle, Los Alamitos, Ca 90720-1264 Usa2010

Replication for Send-Deterministic MPI HPC Applications

André Schiper, Thomas Ropars

Replication has recently gained attention in the context of fault tolerance for large scale MPI HPC applications. Existing implementations try to cover all MPI codes and to be independent from the underlying library. In this paper, we evaluate the advantag ...

2013

Optimizing Paxos with batching and pipelining

André Schiper, Nuno Filipe de Sousa Santos

Paxos is probably the most popular state machine replication protocol. Two optimizations that can greatly improve its performance are batching and pipelining. However, tuning these two optimizations to achieve high-throughput can be challenging, as their e ...

Elsevier2013

The Heard-Of model: computing in distributed systems with benign faults

André Schiper

Problems in fault-tolerant distributed computing have been studied in a variety of models. These models are structured around two central ideas: (1) degree of synchrony and failure model are two independent parameters that determine a particular type of sy ...

Springer Verlag2009

S-Paxos: Offloading the Leader for High Throughput State Machine Replication

André Schiper, Nuno Filipe de Sousa Santos, Zarko Milosevic, Martin Biely

Implementations of state machine replication are prevalently using variants of Paxos or other leader-based protocols. Typically these protocols are also leader-centric, in the sense that the leader performs more work than the non-leader replicas. Such prot ...

2012

Modeling and validating the performance of atomic broadcast algorithms in high-latency networks

André Schiper, Nils Richard Ekwall

The performance of consensus and atomic broadcast algorithms using failure detectors is often affected by a trade-off between the number of communication steps and the number of messages needed to reach a decision. In this paper, we model the performance o ...

Springer2007

Timing Analysis of Leader-Based and Decentralized Byzantine Consensus Algorithms

André Schiper, Martin Hutle, Fatemeh Borran

We compare in an analytical way two leader-based and decentralized algorithms (that is, algorithms that do not use a leader) for Byzantine consensus with strong validity. We show that for \emph{the algorithms we analyzed}, in most cases, the decentralized ...

IEEE2011