Personne

Rachid Guerraoui

Publications associées (292)

PaxosInside

Amodernmanycore architecture can be viewed as a distributed system with explicit message passing to communicate between cores. Ensuring the consistency of shared state replicated over several cores is the key to the well functioning of such a system. Yet, ...

2010

Reﬂexes: Abstractions for Integrating Highly Responsive Tasks into Java Applications

Rachid Guerraoui, Jesper Honig Spring

Achieving submillisecond response times in a managed language environment such as Java or C# requires overcoming signiﬁcant challenges. In this article, we propose Reﬂexes, a programming model and runtime system infrastructure that lets developers seamless ...

2010

Tight Failure Detection Bounds on Atomic Object Implementations

Rachid Guerraoui

This article determines the weakest failure detectors to implement shared atomic objects in a distributed system with crash-prone processes. We first determine the weakest failure detector for the basic register object. We then use that to determine the we ...

2010

Transactions in the Jungle

Rachid Guerraoui, Vasu Singh, Michal Kapalka

Transactional memory (TM) has shown potential to simplify the task of writing concurrent programs. Inspired by classical work on databases, formal definitions of the semantics of TM executions have been proposed. Many of these definitions assumed that acce ...

Acm Order Department2010

Model checking transactional memories

Rachid Guerraoui, Vasu Singh

Model checking transactional memories (TMs) is difficult because of the unbounded number, length, and delay of concurrent transactions, as well as the unbounded size of the memory. We show that, under certain conditions satisfied by most TMs we know of, th ...

Springer Verlag2010

Securing Every Bit: Authenticated Broadcast in Radio Networks

Rachid Guerraoui, Zarko Milosevic, Seth Gilbert, Dan Alistarh

This paper studies non-cryptographic authenticated broad- cast in radio networks subject to malicious failures. We in- troduce two protocols that address this problem. The first, NeighborWatchRB, makes use of a novel strategy in which honest devices monito ...

Acm Order Department, P O Box 64145, Baltimore, Md 21264 Usa2010

Collaborative Scoring with Dishonest Participants

Rachid Guerraoui, Seth Gilbert, Faezeh Malakouti

Consider a set of players that are interested in collectively evaluating a set of objects. We develop a collaborative scori ng protocol in which each player evaluates a subset of the objects, after which we can accurately predict each players’ individual o ...

Acm Order Department, P O Box 64145, Baltimore, Md 21264 Usa2010

The Next 700 BFT Protocols

Rachid Guerraoui, Marko Vukolic, Nikola Knezevic

Modern Byzantine fault-tolerant state machine replication (BFT) protocols involve about 20,000 lines of challenging C++ code encompassing synchronization, networking and cryptography. They are notoriously difficult to develop, test and prove. We present a ...

2010

Refined quorum systems

Rachid Guerraoui, Marko Vukolic

It is considered good distributed computing practice to devise object implementations that tolerate contention, periods of asynchrony and a large number of failures, but perform fast if few failures occur, the system is synchronous and there is no contenti ...

2010

Of Choices, Failures and Asynchrony: The Many Faces of Set Agreement

Rachid Guerraoui, Seth Gilbert, Dan Alistarh

Set agreement is a fundamental problem in distributed computing in which processes collectively choose a small subset of values from a larger set of proposals. The impossibility of fault-tolerant set agreement in asynchronous networks is one of the seminal ...

Springer2009

Elastic Transactions

Pascal Felber, Rachid Guerraoui, Vincent Gramoli

This paper presents elastic transactions, a variant of the transactional model. Upon conflict detection, an elastic transaction might drop what it did so far within a separate transaction that immediately commits, and initiate a new transaction which might ...

Springer2009

The Disagreement Power of an Adversary

Rachid Guerraoui

At the heart of distributed computing lies the fundamental result that the level of agreement that can be obtained in an asynchronous shared memory model where t processes can crash is exactly t + 1. In other words, an adversary that can crash any subset o ...

2009

The Wireless Synchronization Problem

Rachid Guerraoui, Seth Gilbert

In this paper, we study the wireless synchronization prob- lem which requires devices activated at different times on a congested single-hop radio network to synchronize their round numbering. We assume a collection of n synchronous devices with access to ...

2009

High-Performance Transactional Event Processing

Rachid Guerraoui, Jesper Honig Spring, Antonio Cunei

This paper presents a transactional framework for low-latency, high-performance, concurrent event processing in Java. At the heart of our framework lies Reﬂexes, a restricted programming model for highly responsive systems. A Reﬂex task is an event process ...

Springer-Verlag New York, Ms Ingrid Cunningham, 175 Fifth Ave, New York, Ny 10010 Usa2009

The Complexity of Obstruction-Free Implementations

Rachid Guerraoui, Hagit Albo Attiya

Obstruction-free implementations of concurrent ob jects are optimized for the common case where there is no step contention, and were recently advocated as a solution to the costs associated with synchronization without locks. In this paper, we study this ...

2009

Heterogeneous Gossip

Rachid Guerraoui, Maxime Monod, Anne-Marie Kermarrec, Davide Frey

Gossip-based information dissemination protocols are considered easy to deploy, scalable and resilient to network dynamics. Load-balancing is inherent in these protocols as the dissemination work is evenly spread among all nodes. Yet, large-scale distribut ...

Springer2009

The Semantics of Progress in Lock-Based Transactional Memory

Rachid Guerraoui, Michal Kapalka

Transactional memory (TM) is a promising paradigm for concurrent programming. Whereas the number of TM implementations is growing, however, little research has been conducted to precisely define TM semantics, especially their progress guarantees. This pape ...

ACM2009

Transactional Memory: Glimmer of a Theory

Rachid Guerraoui, Michal Kapalka

Transactional memory (TM) is a promising paradigm for concurrent programming. This paper is an overview of our recent theoretical work on defining a theory of TM. We first recall some TM correctness properties and then overview results on the inherent powe ...

Springer2009

Brief Announcement: Towards Secured Distributed Polling in Social Networks

Rachid Guerraoui, Maxime Monod, Anne-Marie Kermarrec, Kévin Clément Huguenin

Springer-Verlag New York, Ms Ingrid Cunningham, 175 Fifth Ave, New York, Ny 10010 Usa2009

Decentralized Polling with Respectable Participants

Rachid Guerraoui, Maxime Monod, Anne-Marie Kermarrec, Kévin Clément Huguenin

We consider the polling problem in a social network where participants care about their reputation: they do not want their vote to be disclosed nor their misbehaving, if any, to be publicly exposed. Assuming this reputation concern, we show that a simple s ...

2009