Publications de André Schiper

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

Consensus with Partial Synchrony

André Schiper

Springer New York2016

On the Performance of Delegation over Cache-Coherent Shared Memory

André Schiper, Darko Petrovic, Thomas Ropars

Delegation is a thread synchronization technique where access to shared data is performed through a dedicated server thread. When a client thread requires shared data access, it makes a request to a server and waits for a response. This paper studies deleg ...

2015

Leveraging Hardware Message Passing for Efficient Thread Synchronization

André Schiper, Darko Petrovic, Thomas Ropars

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

Tolerating permanent and transient value faults

André Schiper, Martin Hutle, Zarko Milosevic

Transmission faults allow us to reason about permanent and transient value faults in a uniform way. However, all existing solutions to consensus in this model are either in the synchronous system, or require strong conditions for termination, that exclude ...

Springer Verlag2014

High-Throughput Maps on Message-Passing Manycore Architectures: Partitioning versus Replication

André Schiper, Omid Shahmirzadi, Thomas Ropars

The advent of manycore architectures raises new scalability challenges for concurrent applications. Implementing scalable data structures is one of them. Several manycore architectures provide hardware message passing as a means to efficiently exchange dat ...

2014

Leveraging Hardware Message Passing for Efficient Thread Synchronization

André Schiper, Darko Petrovic, Thomas Ropars

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

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

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

SPBC: Leveraging the Characteristics of MPI HPC Applications for Scalable Checkpointing

André Schiper, Thomas Ropars

The high failure rate expected for future supercomputers requires the design of new fault tolerant solutions. Most checkpointing protocols are designed to work with any message-passing application but suffer from scalability issues at extreme scale. We tak ...

2013

Replication for Send-Deterministic MPI HPC Applications

André Schiper, Thomas Ropars, Arnaud Lefray

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

Tuning Paxos for high-throughput 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. Nevertheless, tuning these two optimizations to achieve high-throughput can be challenging, as th ...

2012

High-Performance RMA-Based Broadcast on the Intel SCC

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

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

Asynchronous Broadcast on the Intel SCC using Interrupts

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

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

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

Quantitative Analysis of Consensus Algorithms

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

Consensus is one of the key problems in fault-tolerant distributed computing. Although the solvability of consensus is now a well-understood problem, comparing different algorithms in terms of efficiency is still an open problem. In this paper, we address ...

2012

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

André Schiper, Zarko Milosevic, Nuno Filipe de Sousa Santos, 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

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

A Fault-Tolerant Token-Based Atomic Broadcast Algorithm

André Schiper, Nils Richard Ekwall

Many atomic broadcast algorithms have been published in the last 20 years. Token-based algorithms represent a large class of these algorithms. Interestingly, all the token-based atomic broadcast algorithms rely on a group membership service and none of the ...

2011

Structured Derivation of Semi-Synchronous Algorithms

André Schiper, Fatemeh Borran, Martin Hutle, Zarko Milosevic, Hagit Albo Attiya

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