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.

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

Protocols that solve agreement problems are essential building blocks for fault tolerant distributed systems. While many protocols have been published, little has been done to analyze their performance, especially the performance of their fault tolerance mechanisms. In this paper, we present a performance evaluation methodology that can be generalized to analyze many kinds of fault-tolerant algorithms. We use the methodology to compare two atomic broadcast algorithms with different fault tolerance mechanism

In this paper, we present a performance comparison of database replication techniques based on total order broadcast. While the performance of total order broadcast-based replication techniques has been studied in previous papers, this paper presents many ...

While group communication system have been proposed for some time, they are still not used much in actual systems. We believe that one reason for this is the lack of standardisation of group communication system interfaces. The paper proposes an architecture, using the standard decomposition into services, were services are based on standard interfaces: both interactions between services and interactions with the application use existing, open standards. A decomposition of the group communication into servi

The increased interest in protocols that provide a total order on message delivery has led to several different definitions of total order. In this paper we investigate these different definitions and propose a hierarchy that helps to better understand the implications of the different possibilities in terms of guarantees and communication cost. We identify two definitions: {\em weak total order} and {\em strong total order}, which are at the extremes of the proposed hierarchy, and incorporate them into a c

Simulation and emulation are popular means for evaluating wireless Mobile Ad hoc Networks (MANETs) protocols. Since MANETs are highly dependant on their physical environment, these techniques offer only a partial understanding of factors that may influence performance. Deploying real-life MANETs is therefore an indispensable complementary step for the advancement of MANETs. This paper presents FRANC, a dedicated extensible Java framework for the development, deployment and evaluation of applications and alg

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

This paper addresses the problem of atomic multicasting messages in asynchronous distributed systems. Firstly, we give a characterization of the notion of "genuine atomic multicast''. This characterization leads to a better understanding of the difference between atomic multicast and atomic broadcast, and to make a clear distinction between genuine atomic multicast algorithms and non-genuine atomic multicast algorithms. Secondly, we consider a system with at least two processes among which one can crash, an

Fault tolerance is fundamental to the further development of mobile agent applications. In the context of mobile agents, fault-tolerance prevents a partial or complete loss of the agent, i.e., it ensures that the agent arrives at its destination. In this paper, we present FATOMAS, a Java-based fault-tolerant mobile agent system based on an algorithm presented in an earlier paper. In contrary to the standard place-dependent'' architectural approach, FATOMAS uses the novel agent-dependent'' approach intro

We study the time complexity for deterministic broadcasting algorithms in mobile radio networks. The broadcast operation consists of a source node successfully communicating its message to every other node. In multi-hop radio networks such as MANETs, the m ...

This paper brings the following three main contributions: a hierarchy of specifications for replication techniques, semi-passive replication, and Lazy Consensus. Based on the definition of the Generic Replication problem, we difine two families of replication techniques: replication with parsimonious processing (e.g., passive replication), and replication with redundant processing (e.g., active replication). This helps relate replication techniques to each other. We define a novel replication technique with

In this paper we propose a novel approach for multicasting in Mobile Ad-hoc Networks (MANETs). Since no fixed infrastructure of servers is assumed in MANETs, efficient location management schemes are necessary in order to store and provide information about various services offered throughout the network. MDLM is the first multicast algorithm relying on a location management service. We thus avoid fragile data structures such as trees or DAGs to manage multicast groups, without reverting to more reliable, y

We consider the consensus problem in self-organized networks such as MANETs. Consensus oﬀers a means for reliably solving agreement related problems, which in a self-organized setting can help bring enhanced structure and reliability to the highly dynamic and disorganized environment of MANETs. We consider asynchronous networks with reliable communications channels. Neither the identity nor the number of nodes is initially known to the participants. This captures the self-organized nature of the network, wh

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

This paper investigates the two main and seemingly antagonistic approaches to broadcasting messages in fault-tolerant distributed systems: the approach based on Reliable Broadcast, and the one based on View Synchronous Communication (or VSC for short). We discuss both communication primitives in a system model with fair-lossy channel, which leads us to introduce the "time-bounded buffering" problem: VSC addresses this problem, but not Reliable Broadcast. Moreover, we show that VSC solves Reliable Broadcast

Total order broadcast and multicast (also called atomic broadcast/multicast) present an important problem in distributed systems, especially with respect to fault-tolerance. In short, the primitive ensures that messages sent to a set of processes are, in turn, delivered by all those processes in the same total order.

The deployment of wireless applications or protocols in the context of Mobile Ad-hoc NETwork (MANET), often requires to step through a simulation phase. For the results of the simulation to be meaningful, it is important that the model on which is based the simulator matches as closely as possible the reality. In this paper we present the results of the simulation of an algorithm using several popular simulators (OPNET Modeler, NS-2, GloMoSim). The results tend to show that significant divergences exist bet

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.

Consensus is one of the key problems in fault tolerant distributed computing. A very popular model for solving consensus is the failure detector model defined by Chandra and Toueg. However, the failure detector model has limitations. The paper points out these limitations, and suggests instead a model based on communication predicates, called HO model. The advantage of the HO model over failure detectors is shown, and the implementation of the HO model is discussed in the context of a system that alternates

André Schiper

Chat with Graph Search

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

Comparison of Failure Detectors and Group Membership: Performance Study of Two Atomic Broadcast Algorithms

Comparison of Failure Detectors and Group Membership: Performance Study of Two Atomic Broadcast Algorithms (extended version)

Comparison of Database Replication Techniques Based on Total Order Broadcast

Group communication based on standard interfaces

A Hierarchy of Totally Ordered Multicasts

FRANC: A Lightweight Java Framework for Wireless Multihop Communication

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

Genuine atomic multicast in asynchronous distributed systems

FATOMAS - A Fault-Tolerant Mobile Agent System Based on the Agent-Dependent Approach

The impact of mobility on the time complexity for deterministic broadcasting in radio networks

Specification of Replication Techniques, Semi-Passive Replication, and Lazy consensus*

From a Location Service to a Multicast Service for Wireless Mobile Adhoc Networks

Reaching Agreement with Unknown Participants in Mobile Self-Organized Networks in Spite of Process Crashes

Tolerating permanent and transient value faults

Broadcasting Messages in Fault-Tolerant Distributed Systems: the benefit of handling input-triggered and output-triggered suspicions differently

Total Order Broadcast and Multicast Algorithms: Taxonomy and Survey

On the Accuracy of MANET Simulators

A Systematic Classification of Replicated Database Protocols based on Atomic Broadcast

Communication Predicates: A high-level abstraction for coping with transient and dynamic faults