Publication

A paradox of eventual linearizability in shared memory

Related publications (32)

Graph Chatbot

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

Laws of Order: Expensive Synchronization in Concurrent Algorithms Cannot be Eliminated

Rachid Guerraoui, Hagit Albo Attiya

Building correct and efﬁcient concurrent algorithms is known to be a difﬁcult problem of fundamental importance. To achieve ef- ﬁciency, designers try to remove unnecessary and costly synchro- nization. However, not only is this manual trial-and-error proc ...

2011

Laws of order

Rachid Guerraoui, Hagit Albo Attiya

Building correct and efficient concurrent algorithms is known to be a difficult problem of fundamental importance. To achieve efficiency, designers try to remove unnecessary and costly synchronization. However, not only is this manual trial-and-error proce ...

2011

Transactions in the Jungle

Rachid Guerraoui, Michal Kapalka, Vasu Singh

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

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, Michal Kapalka, Vasu Singh

Transactional memory (TM) has shown potential to simplify the task of writing concurrent programs. However, the semantics of interactions between transactions managed by a TM and non-transactional operations, while widely studied, lacks a clear formal spec ...

2009

Anonymous and Fault-Tolerant Shared-Memory Computing

Rachid Guerraoui, Eric Ruppert

The vast majority of papers on distributed computing assume that processes are assigned unique identifiers before computation begins. But is this assumption necessary? What if processes do not have unique identifiers or do not wish to divulge them for re ...

2007

Anonymous and fault-tolerant shared-memory computing

Rachid Guerraoui, Eric Ruppert

Springer, Springer-Verlag2007

Temporal Streaming of Shared Memory

Anastasia Ailamaki, Babak Falsafi

Coherent read misses in shared-memory multiprocessors account for a substantial fraction of execution time in many important scientific and commercial workloads. We propose Temporal Streaming, to eliminate coherent read misses by streaming data to a proces ...

2005

Store-Ordered Streaming of Shared Memory

Anastasia Ailamaki, Babak Falsafi

Coherence misses in shared-memory multiprocessors account for a substantial fraction of execution time in many important scientific and commercial workloads. Memory streaming provides a promising solution to the coherence miss bottleneck because it improve ...

2005

Contention elimination by replication of sequential sections in distributed shared memory programs

Willy Zwaenepoel

In shared memory programs contention often occurs at the transition between a sequential and a parallel section of the code. As all threads start executing the parallel section, they often access data just modified by the thread that executed the sequentia ...

2001