Publications de Rachid Guerraoui

Chattez avec Graph Search

Posez n’importe quelle question sur les cours, conférences, exercices, recherches, actualités, etc. de l’EPFL ou essayez les exemples de questions ci-dessous.

AVERTISSEMENT : Le chatbot Graph n'est pas programmé pour fournir des réponses explicites ou catégoriques à vos questions. Il transforme plutôt vos questions en demandes API qui sont distribuées aux différents services informatiques officiellement administrés par l'EPFL. Son but est uniquement de collecter et de recommander des références pertinentes à des contenus que vous pouvez explorer pour vous aider à répondre à vos questions.

This paper studies obstruction-free software transactional memory systems (OFTMs). These systems are appealing, for they combine the atomicity property of transactions with a liveness property that ensures the commitment of every transaction that eventuall ...

This paper compares, for the rst time, the computational power of linearizable objects with that of eventually linearizable ones. We present the following paradox. We show that, unsurprisingly, no set of eventually linearizable objects can (1) implement an ...

Asynchronous distributed machine learning solutions have proven very effective so far, but always assuming perfectly functioning workers. In practice, some of the workers can however exhibit Byzantine behavior, caused by hardware failures, software bugs, c ...

We introduce the notion of permissiveness in transactional memories (TM). Intuitively, a TM is permissive if it never aborts a transaction when it need not. More specifically, a TM is permissive with respect to a safety property p if the TM accepts every h ...

An indulgent algorithm is a distributed algorithm that, besides tolerating process failures, also tolerates unreliable information about the interleaving of the processes. This article presents a general characterization of indulgence in an abstract comput ...

The problem of Byzantine resilience in distributed machine learning, a.k.a., Byzantine machine learning, consists in designing distributed algorithms that can train an accurate model despite the presence of Byzantine nodes, i.e., nodes with corrupt data or ...

We show that no deterministic algorithm can solve consensus in the presence of t+1 process crash failures, in a system of n processes that communicate in a reliable way and synchronize their activities using any number of t-resilient services. These base services can range from any type of atomic objects shared by the processes (including consensus objects), to any class of non-atomic objects like failure detectors (including perfect ones), and broadcast primitives (including totally ordered one). The servi

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

The Dolev-Reischuk bound says that any deterministic Byzantine consensus protocol has (at least) quadratic communication complexity in the worst case. While it has been shown that the bound is tight in synchronous environments, it is still unknown whether ...

Decentralized machine learning over peer-to-peer networks is very appealing for it enables to learn personalized models without sharing users data, nor relying on any central server. Peers can improve upon their locally trained model across a network graph ...

We introduce a new synchronization problem in mobile ad-hoc systems: the Driving Philosophers. In this problem, an unbounded number of driving philosophers (processes) access a round-about (set of shared resources organized along a logical ring). The crux of the problem is to ensure, beside traditional mutual exclusion and starvation freedom at each particular resource, gridlock freedom (i.e., cyclic waiting chain amongst processes). The problem captures explicitly the very notion of process mobility and th

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

Providing type interoperability consists in ensuring that, even if written by different programmers, possibly in different languages and running on different platforms, types that are supposed to represent the same software module are indeed treated as one single type. This form of interoperability is crucial in modern distributed programming. We present a pragmatic approach to deal with type interoperability in a distributed system. Our approach is based on a specific serialization mechanism and a set of t

The Transactional Memory (TM) paradigm promises to greatly simplify the development of concurrent applications. This led, over the years, to the creation of a plethora of TM implementations delivering wide ranges of performance across workloads. Yet, no un ...

It is known that the agreement property of the Byzantine consensus problem among n processes can be violated in a non-synchronous system if the number of faulty processes exceeds t0 = ┌n/3┐ − 1 [10], [19]. In this paper, we investigate the accountable Byza ...

This paper presents x-ability (Exactly-once-ability): a correctness criteria for replicated services. X-ability provides the illusion that the actions executed by a replicated service are executed exactly-once, even if these actions have been actually executed several times and by various replicas. A client can treat a x-able replicated service as if it was not replicated, even if this service executes actions that are non-deterministic and have side-effects on the environment, e.g., invoke other services.

Remote Direct Memory Access (RDMA) is becoming widely available in data centers. This technology allows a process to directly read and write the memory of a remote host, with a mechanism to control access permissions. In this paper, we study the fundamenta ...

The upsurge in the number of web users over the last two decades has resulted in a significant growth of online information. This information growth calls for recommenders that personalize the in- formation proposed to each individual user. Nevertheless, p ...

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

We prove that transactions cannot be fast in an asynchronous fault-tolerant system. Our result holds in any system where we require transactions to ensure monotonic writes, or any stronger consistency model, such as, causal consistency. Thus, our result un ...

Rachid Guerraoui

Chattez avec Graph Search

On Obstruction-Free Transactions

A paradox of eventual linearizability in shared memory

Asynchronous Byzantine Machine Learning (the case of SGD)

Permissiveness in Transactional Memories

A General Characterization of Indulgence

Byzantine Machine Learning: A Primer

On the Impossibility of Boosting Distributed Service Resilience

Collaborative Personalized Top-k Processing

Byzantine Consensus is Θ(n^2): The Dolev-Reischuk Bound is Tight even in Partial Synchrony!

Robust P2P Personalized Learning

The Driving Philosophers

Genuine atomic multicast in asynchronous distributed systems

Pragmatic Type Interoperability

ProteusTM: Abstraction Meets Performance in Transactional Memory

As easy as ABC: Optimal (A)ccountable (B)yzantine (C)onsensus is easy!

X-ability: A Theory of Replication

The Impact of RDMA on Agreement

D2P: Distance-Based Differential Privacy in Recommenders

The Complexity of Renaming

The Impossibility of Fast Transactions