Some Publications of Rachid Guerraoui



The Complexity of Distributed Algorithms
The Time-Complexity of Local Decision in Distributed Agreement
. with Dutta P and Pochon B. SIAM Journal on Computing. 2007.  An extension of our DISC 2003 paper.
The Perfectly-Synchronized Round-based Model of Distributed Computing. with C. Delporte, H. Fauconnier and B. Pochon. Information & Computation, 2007.
Synchronizing without Locks is Inherently Expensive. with Attiya, H., Hendler, D. and Kouznetsov, P., ACM PODC 2006.
How Fast Can a Very Robust Read Be? with Vukolic, M.,ACM  PODC 2006.
A Topological Treatment of Early Deciding Set-Agreement. with Herlihy M and Pochon ., OPODIS 2006.
Lucky Read/Write Access to Robust Atomic Storage. with Levy, R. and Vukolic, M., IEEE DSN 2006.
From a Static Impossibility to an Adaptive Lower Bound: The Complexity of Early Deciding Set Agreement with E. Gafni and B. Pochon, ACM STOC 2005.

Computing with Reads and Writes in the absence of contention with H. Attiya and P. Kouznetsov, DISC 2005.

How Fast Can Eventual Synchrony Lead to Consensus? with P. Dutta and L. Lamport,  IEEE DSN 2005.
Best-Case Complexity of Asynchronous Byzantine Consensus, with P. Dutta and M. Vukolic, EPFL I&C Technical Report ID 200499, (revised version February 2005)
Reliable and Total Order Broadcast in the Crash-Recovery Model with R. Boichat, Journal of Parallel and Distributed Computing, 2005
How Fast can a Distributed Read be? with P. Dutta, R. Levy and A. Chakraborty,  ACM PODC 2004

Fast Non-Blocking Atomic Commit: an Inherent Tradeoff  with P. Dutta and B. Pochon;  IPL, 2004


The Weakest Failure Detection Question
On The Weakest Failure Detector Ever
. with Herlihy M, Kouznetsov P, Lynch N and Newport C. ACM  PODC 2007.
The Weakest Failure Detectors to Boost Obstruction-Freedom. with Kapalka, M. and Kouznetsov, P., DISC 2006.
Almost all Objects are Universal in Message Passing Systems with C. Delporte and H. Fauconnier, DISC 2006
Mutual Exclusion in Asynchronous Systems with Failure Detectors with C. Delporte, H. Fauconnier and P. Kouznetsov, Journal of Parallel and Distributed Computing 2005
On the impossibility of boosting the resilience of distributed services  with P. Attie, P. Kouznetsov, N. Lynch and S. Rasjbaum, IEEE ICDCS 2005.
The Weakest Failure Detectors to solve certain Fundamental Problems in Distributed Computing with Delporte, Fauconnier, Hadzilacos, Kouznetsov, S. Toueg; ACM  PODC  2004
On Failure Detectors and Type Boosters with Petr Kouznetsov; DISC 2003
The Weakest Failure Detector for Non-Blocking Atomic Commit with P. Kouznetsov; IC Tech Report ID: 200347
Failure Detection Lower Bounds on Registers and Consensus with C. Delporte, and H. Fauconnier; DISC 2002
Non-Blocking Atomic Commitment in Asynchronous Systems with Failure Detectors
ACM-Springer Verlag, Distributed Computing, 15(1), 2002.
On the Weakest Failure Detector for Non-Blocking Atomic Commit
  with P. Kouznetsov; International Conference on Theoretical Computer Science, 2002
Revisiting the relationship between Non Blocking Atomic Commitment and Consensus problems
WDAG 1995; Springer Verlag (LNCS)
Failure Detection: From Crash-Stop to Byzantine Failures with A. Doudou and B. Garbinato; Invited paper at AE 2002


Event-Based Distributed Programming

Towards Safe Distributed Application Development with P. Eugster and C Dam, ACM/IEEE  ICSE 2004
Distributed Programming with Typed Events with P. Eugster, IEEE Software, March 2004
The Many Faces of Publish/Subscribe with P. Th. Eugster, P. Felber, and A.-M. Kermarrec; ACM Computing Surveys,  2003
On Objects and Events with P. Eugster and C. Damm; ACM OOPSLA 2001
Pragmatic Type Interoperabilitywith S. Baehni,  P. Th. Eugster and P. Altherr,  IEEE ICDCS 2003
OS Support for P2P Programming: a Case for TPS with S. Baehni and P. Eugster; IEEE ICDCS 2002
Distributed Asynchronous Collections: Abstractions for Publish/Subscribe Interaction with P. Eugster and J. Sventek; ECOOP 2000

Gossip-Based Algorithms
Gossip-Based Peer Sampling
. with Jelasity M, Voulgaris S, Kermarrec A-M and Van Steen M. ACM Transactions on Computer Systems. 2007.  Ax extended version of our Middleware 2004 paper.
GosSkip. with Handurukande, S., Huguenin, K., Kermarrec, A.-M., Le Fessant, F. and Riviere, E.,
From Epidemics to Distributed Computing  with P. Th. Eugster, R. Guerraoui, A.-M. Kermarrec and L. Massoulie;  IEEE Computer, May 2004
Data Aware Multicast with Baehni and P. Eugster; IEEE DSN 2004

Probabilistic Multicast with P. Eugster;  IEEE DSN 2002
Lightweight Probabilistic Broadcast
with P. Eugster, S. Handurukande, A.-M. Kerrmarec and P. Kouznetsov; ACM Transactions on Computer Systems (TOCS) 2003; an extended version of our DSN 2001 paper
Adaptive Gossip-Based Broadcast with L. Rodrigues, S. Handurukande, J. Pereira, and A-M Kermarrec; IEEE  DSN 2003

Delta-Reliability: A Probabilistic Measure of Broadcast Reliability with P. Th. Eugster and P. Kouznetsov ICDCS 2004
Genuine Atomic Multicast in Asynchronous Distributed Systems with A. Schiper; Theoretical Computer Science, 2001


Indulgent (Consensus) Algorithms
Refined Quorum Systems
. with M. Vukolic. ACM  PODC 07.
On the Message Complexity of Indulgent Consensus. with Gilbert S and Kowalski D. DISC 2007.
A General Characterization of Indulgence (Invited Paper). with Lynch, N.  SSS 2006.
The Alpha of Indulgent Consensus. with Raynal, M., Computer Journal 2006.
The Overhead of Indulgent Failure Recovery. with Dutta P and Keidar I., ACM-Springer Distributed Computing 2006.
The Inherent Price of Indulgence with P. Dutta; ACM PODC 2002
Fast Indulgent Consensus with Zero-Degradation
with P. Dutta; EDCC 2002

Tolerating Arbitrary Failures with State Machine Replication  with A. Doudou and B. Garbinato, chapter 2 in Dependable Computing Systems Paradigms, Performance Issues, and Applications. Wiley, 2005.
Gracefully Degrading Fair Exchange with Security Modules (Extended Abstract)
with G. Avoine, F. Gartner and M. Vukolic, EDCC 2005.
Deconstucting Paxos with R. Boichat, P. Dutta, and S. Frolund; Distributed Computing Column of ACM SIGACT News, Volume 34, Issue 1, March 2003
Reconstructing Paxos with R. Boichat, P. Dutta, and S. Frolund; Distributed Computing Column of ACM SIGACT News, Volume 34, Issue 2, June 2003
A Lightweight Universal Construction for a Message Passing System with P. Dutta, S. Frolund,and B. Pochon; DISC 2002
The Information Structure of Indulgent Consensus with M. Raynal; IEEE Transactions on Computers, 2004
Indulgent Algorithms ACM PODC 2000
On the Hardness of Failure Sensitive Agreement  IPL 2001
The Generic Consensus Service with A. Schiper; IEEE Transactions on Software Engineering, 2001
Consensus: the Big Misunderstanding
with A. Schiper; IEEE FTDCS'97
The Transaction Model vs The Virtual Synchrony Model: Bridging the gap
with A. Schiper; In Distributed Systems: From Theory to Practice, Springer Verlag, LNCS (938), 1994

Transaction-Based Programming
STMBench7: A Benchmark for Software Transactional Memory with M. Kapalka and I. Vitek, Eurosys 2007
Toward a Theory of Transactional Contention Managers with M. Herlihy and B. Pochon, ACM PODC 2005
Polymorphic Contention Management with M. Herlihy and B. Pochon, DISC 2005
An Equational Theory for Transactions with A. Black, V. Cremet and M. Odersky; FSTTCS 2003
Nesting Actions Through Asynchronous Message Passing
with R. Capobianchi, A. Lanusse and P. Roux; ECOOP 92
CORBA Fault-Tolerance: Why it does not add up with S. Frolund; IEEE FTDCS 1999
Experiences with Object Group Systems with P. Eugster, P. Felber, B. Garbinato and K. Mazouni; Software: Practice & Experience - An Extension of our OOPSLA 1998 paper
Programming with Object Groups in CORBA
with P. Felber; IEEE Concurrency, 2000; Revisits our IEEE SRDS'95 paper
The GARF System: Overview, Design and Implementation
with B. Garbinato and K. Mazouni; IEEE Concurrency, November 1997
Protocol Classes for Designing Reliable Distributed Environments
with B. Garbinato and P. Felber; ECOOP 1996
Implementation of the GARF Replicated Object Plateform with B. Garbinato and K. Mazouni; Distributed Systems Engineering Journal, 1 (1), March 1995;


Fault-Tolerance by Software Replication

Anonymous and Fault-Tolerant Shared-Memory Computing
. with Ruppert R. ACM-Springer Distributed Computing. 2007. An extension of our DISC 2005 paper.
Amnesic Distributed Storage
. with Chockler and Keidar I.  DISC 2007. 
The Collective Memory of Amnesic Processes
. with Levy R, Pochon B and Pugh J. ACM Transactions on Algorithms. 2007 .
X-Ability: A Theory of Replication
with S. Frolund; ACM-Springer Verlag, Distributed Computing, 14(4), 2001. An extended version of our PODC 2000 paper
Software Based Replication for Fault Tolerance
with A. Schiper; IEEE Computer , 30 (4), April 1997
Implementing e-Transactions with Asynchronous Replication
with S. Frolund; IEEE TPDS, 2001. An extended version of our DSN 2000 paper
Exactly-Once Transactions
with S. Frolund; IEEE Transactions on Software Engineering. 2002

Mobile Computing
Gossiping in a Multi-Channel Radio Network, An Oblivious Approach to Coping with Malicious Interference.
with Dolev S, Gilbert S and Newport C. DISC 2007.
On Malicious Motes and Suspicious Sensors. with Gilbert S and Newport C. OPODIS 2006.
When Birds Die: Making Population Protocols Fault-tolerant. with Delporte-Gallet, C., Fauconnier, H. and Ruppert, E, ACM DCOSS 2006.
Frugal Event Dissemination in a Mobile Environment with S. Baehni and C. Chhabra, ACM Middleware 2005
The Driving Philosophers with S. Baehni, R. Baldoni, R. Guerraoui and B. Pochon, International Conference on Theoretical Computer Science (TCS 2004), 181-194.
On the Consistency Problem in Mobile Distributed Computing with C. Hari; ACM Proceedings of the Workshop on Principles of Mobile Computing (POMC 2002), Toulouse, October 2002
Mobile Databases: A Report on Open Issues and Research Directions with Bernard, G. et al. .ACM SIGMOD Record, 33 (2), 78-83.
Mobile Computing with Frugal Objects with B. Garbinato, J. Hulaas, O. Madsen, M. Monod and J. Spring, EPFL I&C Technical Report

Object-Based Distributed Programming
A Smooth Concurrency Revolution with Free Objects
. Internet Computing, 2007.
What object-oriented distributed programming does not have to be, and what it may be Informatik, 2 1999;  Parts of this paper were revisited in series of Columns of CACM with P. Felber and M. Fayad
AOP does it make sense? The Case of Concurrency and Failures with J. Kienzle; ECOOP 2002.
Concurrency and Distribution in Object Oriented Programming
with J-P Briot and K. Lohr; ACM Computing Surveys , September 1998
Strategic Research Directions in Object Oriented Programming
(editorial) ACM Computing Surveys, December 1997