Personne

Rachid Guerraoui

Publications associées (292)

Scalable and Secure Polling in Dynamic Distributed Networks

Rachid Guerraoui, Anne-Marie Kermarrec, Hamza Harkous, Florian Huc

We consider the problem of securely conducting a poll in synchronous dynamic networks equipped with a Public Key Infrastructure (PKI). Whereas previous distributed solutions had a communication cost of O(n^2) in an n nodes system, we present SPP (Secure an ...

2012

The Weakest Failure Detectors To Solve Quittable Consensus And Nonblocking Atomic Commit

Rachid Guerraoui

We define quittable consensus, a natural variation of the consensus problem, where processes have the option to agree on "quit" if failures occur, and we relate this problem to the well-known problem of nonblocking atomic commit. We then determine the weak ...

Society for Industrial and Applied Mathematics2012

How to Allocate Tasks Asynchronously

Rachid Guerraoui, Seth Gilbert, Dan Alistarh

Asynchronous task allocation is a fundamental problem in distributed computing in which p asynchronous processes must execute a set of m tasks. Also known as write-all or do-all, this problem been studied extensively, both independently and as a key buildi ...

IEEE2012

Generating Fast Indulgent Algorithms

Rachid Guerraoui, Seth Gilbert, Dan Alistarh

Synchronous distributed algorithms are easier to design and prove correct than algorithms that tolerate asynchrony. Yet, in the real world, networks experience asynchrony and other timing anomalies. In this paper, we address the question of how to efficien ...

Springer Verlag2012

Speculative Linearizability

Rachid Guerraoui, Viktor Kuncak, Giuliano Losa

Linearizability is a key design methodology for reasoning about implementations of concurrent abstract data types in both shared memory and message passing systems. It provides the illusion that operations execute sequentially and fault-free, despite the a ...

Assoc Computing Machinery2012

Automated Vulnerability Discovery in Distributed Systems

Rachid Guerraoui, George Candea, Radu Banabic

In this paper we present a technique for automatically assessing the amount of damage a small number of participant nodes can inﬂict on the overall performance of a large distributed system. We propose a feedback-driven tool that synthesizes malicious node ...

2011

The Failure Detector Abstraction

Rachid Guerraoui

A failure detector is a fundamental abstraction in distributed computing. This paper surveys this abstraction through two dimensions. First we study failure detectors as building blocks to simplify the design of reliable distributed algorithms. In particul ...

2011

Why STM can be more than a Research Toy

Pascal Felber, Rachid Guerraoui, Aleksandar Dragojevic, Vincent Gramoli

Software Transactional Memory (STM) promises to simplify concurrent programming without requiring specific hardware support. Yet, STM’s credibility lies on the extent to which it enables to leverage multicores and outperform sequential code. A recent CACM ...

2011

The complexity of robust atomic storage

Rachid Guerraoui, Marko Vukolic

We study the time-complexity of robust atomic read/write storage from fault-prone storage components in asynchronous message-passing systems. Robustness here means wait-free tolerating the largest possible number t of Byzantine storage component failures ( ...

ACM Press2011

Verification of STM on relaxed memory models

Rachid Guerraoui, Vasu Singh

Software transactional memories (STM) are described in the literature with assumptions of sequentially consistent program execution and atomicity of high level operations like read, write, and abort. However, in a realistic setting, processors use relaxed ...

Springer Verlag2011

Generalized Universality

Rachid Guerraoui

State machine replication reduces distributed to centralized computing. Any sequential service, modeled by a state machine, can be replicated over any number of processes and made highly available to all of them. At the heart of this fundamental reduction ...

Springer Berlin Heidelberg2011

The Complexity of Renaming

Rachid Guerraoui, Seth Gilbert, Dan Alistarh

We study the complexity of renaming, a fundamental problem in distributed computing in which a set of processes need to pick distinct names from a given namespace. We prove an individual lower bound of Omega(k) process steps for deterministic renaming into ...

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

Brief Announcement: Transaction Polymorphism

Rachid Guerraoui, Vincent Gramoli

In this work, we present transaction polymorphism; a synchronization technique that provides more control to the programmer than traditional (i.e., monomorphic) transactions to achieve comparable performance to generic lock-based and lock-free solutions. ...

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

Collaborative Personalized Top-k Processing

Rachid Guerraoui, Anne-Marie Kermarrec

This article presents P4Q, a fully decentralized gossip-based protocol to personalize query processing in social tagging systems. P4Q dynamically associates each user with social acquaintances sharing similar tagging behaviors. Queries are gossiped among s ...

Association for Computing Machinery2011

The Complexity Of Early Deciding Set Agreement

Rachid Guerraoui, Bastian Pochon

In the k-set agreement problem, each processor starts with a private input value and eventually decides on an output value. At most k distinct output values may be chosen, and every processor's output value must be one of the proposed values. We consider a ...

Society for Industrial and Applied Mathematics2011

Democratizing Transactional Programming

Rachid Guerraoui, Vincent Gramoli

The Transaction abstraction is arguably one of the most appealing middleware paradigms. It lies typically between the programmer of a concurrent or distributed application on the one hand, and the operating system with the underlying network on the other h ...

Springer-Verlag Berlin2011

Generating Fast Indulgent Algorithms

Rachid Guerraoui, Seth Gilbert, Dan Alistarh

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

Leveraging Parallel Nesting in Transactional Memory

Rachid Guerraoui, Michal Kapalka, Aleksandar Dragojevic

Exploiting the emerging reality of affordable multi-core architectures goes through providing programmers with simple abstractions that would enable them to easily turn their sequential programs into concurrent ones that expose as much parallelism as possi ...

ACM2010

Fast Randomized Test-and-Set and Renaming

Rachid Guerraoui, Hagit Albo Attiya, Seth Gilbert, Dan Alistarh, Andrei Giurgiu

Most people believe that renaming is easy: simply choose a name \emph{at random}; if more than one process selects the same name, then try again. We highlight the issues that occur when trying to implement such a scheme and shed new light on the read-write ...

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

Boosting Gossip for Live Streaming

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

Gossip protocols are considered very effective to disseminate information in a large scale dynamic distributed system. Their inherent simplicity makes them easy to implement and deploy. However, whereas their probabilistic guarantees are often enough to di ...

2010