Personne

Rachid Guerraoui

Publications associées (292)

Towards Fair Event Dissemination

Event dissemination in large scale dynamic systems is typically claimed to be best achieved using decentralized peer-to-peer architectures. The rationale is to have every participant in the system act both as a client (information consumer) and as a server ...

2007

How robust are gossip-based communication protocols?

Rachid Guerraoui

Gossip-based communication protocols are often touted as being robust. Not surprisingly, such a claim relies on assumptions under which gossip protocols are supposed to operate. In this paper, we discuss and in some cases expose some of these assumptions a ...

2007

The Time-Complexity of Local Decision in Distributed Agreement

Rachid Guerraoui, Bastian Pochon, Partha Dutta

Agreement is at the heart of distributed computing. In its simple form, it requires a set of processes to decide on a common value out of the values they propose. The time-complexity of distributed agreement problems is generally measured in terms of the n ...

2007

Efficient Distributed Subtyping Tests

Patrick Eugster, Rachid Guerraoui, João Barreto

Subtyping tests are essential in typed publish/subscribe infrastructures, especially when the underlying programming language supports subtype conformance, as in Java or C#. These tests are particularly challenging when the publish/subscribe infrastructure ...

2007

Reflexes: Abstractions for Highly Responsive Systems

Rachid Guerraoui, Jesper Honig Spring

Commercial Java virtual machines are designed to maximize the performance of applications at the expense of predictability. High throughput garbage collection algorithms, for example, can introduce pauses of 100 milliseconds or more. We are interested in s ...

2007

The Perfectly-Synchronized Round-based Model of Distributed Computing

Rachid Guerraoui, Bastian Pochon

The perfectly-synchronized round-based model provides the powerful abstraction of crash-stop failures with atomic and synchronous message delivery. This abstraction makes distributed programming very easy.We describe a technique to automatically transform ...

2007

STMBench7: A Benchmark for Software Transactional Memory

Rachid Guerraoui, Michal Kapalka

Software transactional memory (STM) is a promising technique for controlling concurrency in modern multi-processor architectures. STM aims to be more scalable than explicit coarse-grained locking and easier to use than fine-grained locking. However, STM im ...

2007

A High Throughput Atomic Storage Algorithm

Rachid Guerraoui, Ron Levy, Dejan Kostic

This paper presents an algorithm to ensure the atomicity of a distributed storage that can be read and written by any number of clients. In failure-free and synchronous situations, and even if there is contention, our algorithm has a high write throughput ...

2007

StreamFlex - High-throughput Stream Programming in Java

Rachid Guerraoui, Jesper Honig Spring

2007

Amnesic Distributed Storage

Rachid Guerraoui

Distributed storage algorithms implement the abstraction of a shared register over distributed base objects. We study a specific class of storage algorithms, which we call amnesic: these have the pragmatic property that old values written in the implemente ...

2007

Secretive Birds: Privacy in Population Protocols

Rachid Guerraoui, Eric Ruppert

We study private computations in a system of tiny mobile agents. We consider the mobile population protocol model of Angluin et al. [2] and ask what can be computed without ever revealing any input to a curious adversary. We show that any computable predic ...

2007

The Alpha of Indulgent Consensus

Rachid Guerraoui

This paper presents a simple framework unifying a family of consensus algorithms that can tolerate process crash failures and asynchronous periods of the network, also called indulgent consensus algorithms. Key to the framework is a new abstraction we intr ...

2007

The Weight-Watcher Service and its Lightweight Implementation

Benoît Garbinato, Rachid Guerraoui, Maxime Monod, Alexei Kounine, Jesper Honig Spring

This paper presents the Weight-Watcher service. This service aims at providing resource consumption measurements and estimations for software executing on resource constrained devices. By using the Weight-Watcher, software components can continuously adapt ...

2007

On The Weakest Failure Detector Ever

Rachid Guerraoui

Many problems in distributed computing are impossible when no information about process failures is available. So what is the minimal yet non-trivial failure information? In other words, what is the minimal information about failures needed to circumvent a ...

2007

The Overhead of Consensus Failure Recovery

Rachid Guerraoui, Partha Dutta

Many reliable distributed systems are consensus-based and typically operate under two modes: a fast normal mode in failure-free synchronous periods, and a slower recovery mode following asynchrony and failures. A lot of work has been devoted to optimize th ...

2007

A Topological Treatment of Early-Deciding Set-Agreement

Rachid Guerraoui, Bastian Pochon

This paper considers the k-set-agreement problem in a synchronous message passing distributed system where up to t processes can fail by crashing. We determine the number of communication rounds needed for all correct processes to reach a decision in a giv ...

2006

Of Malicious Motes and Suspicious Sensors

Rachid Guerraoui, Seth Gilbert

How efficiently can a malicious device disrupt communication in a wireless network? Imagine a basic game involving two honest players, Alice and Bob, who want to exchange information, and an adversary, Collin, who can disrupt communication using a limited ...

2006

Of Malicious Motes and Suspicious Sensors: On the Efficiency of Malicious Interference in Wireless Networks

Rachid Guerraoui, Seth Gilbert

How efficiently can a malicious device disrupt a single-hop wireless network? Imagine two honest players attempting to exchange information in the presence of a malicious adversary that can disrupt communication by jamming or overwriting messages. Assume t ...

2006

Unconscious Eventual Consistency with Gossips

Rachid Guerraoui, Ron Levy

This paper combines various self-stabilization techniques within a replication protocol that ensures eventual consistency in large-scale distributed systems subject to network partitions and asynchrony. A simulation study shows that the resulting protocol ...

2006

Lucky Read/Write Access to Robust Atomic Storage

Rachid Guerraoui, Ron Levy, Marko Vukolic

This paper establishes tight bounds on the \emph{best-case} time-complexity of distributed atomic read/write storage implementations that tolerate \emph{worst-case} conditions. We study asynchronous robust implementations where a writer and a set of reader ...

2006