Publication

Universally Scalable Concurrent Data Structures

Graph Chatbot

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.

Connectez-vous pour utiliser Chat avec Graph Search

Obstruction degree: measuring concurrency in shared memory systems

Rachid Guerraoui, Mihai Letia

This paper presents the notion of obstruction degree, a new metric for reasoning about the scalability of concurrent algorithms. Essentially, this simple metric gives an indication as to which of two concurrent algorithms is expected to scale better, as we ...

2012

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

Concurrent Tries with Efficient Non-Blocking Snapshots

Martin Odersky, Aleksandar Prokopec

We describe a non-blocking concurrent hash trie based on shared-memory single-word compare-and-swap instructions. The hash trie supports standard mutable lock-free operations such as insertion, removal, lookup and their conditional variants. To ensure spac ...

Assoc Computing Machinery2012

On the cost of composing shared-memory algorithms

Rachid Guerraoui, Dan Alistarh, Giuliano Losa

Decades of research in distributed computing have led to a variety of perspectives on what it means for a concurrent algorithm to be efficient, depending on model assumptions, progress guarantees, and complexity metrics. It is therefore natural to ask whet ...

ACM Press2012

Transaction Polymorphism

Rachid Guerraoui, Vincent Gramoli

Concurrent implementations of abstract types usually rely on lock-free primitives or locks and are highly tuned to support a finite set of efficient operations. However, it is very hard to extend such types for specific needs by adding new operations. The ...

2011

Speculative Linearizability

Rachid Guerraoui, Viktor Kuncak, Giuliano Losa

2011

Cache-Aware Lock-Free Concurrent Hash Tries

Martin Odersky, Aleksandar Prokopec

This report describes an implementation of a non-blocking concurrent shared-memory hash trie based on single-word compare-and-swap instructions. Insert, lookup and remove operations modifying different parts of the hash trie can be run independent of each ...

2011

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

Deadlock Immunity

Horatiu Jula

Deadlock immunity is a property by which programs, once afflicted by a deadlock, develop resistance against future occurrences of that deadlock. We enable real applications to automatically achieve immunity against deadlock bugs involving mutex locks, sema ...

EPFL2011

A Data-oriented Transaction Execution Engine and Supporting Tools

Anastasia Ailamaki, Miguel Sérgio De Oliveira Branco, Frederick Ryan Johnson, Pinar Tözün, Ippokratis Pandis, Danica Porobic, Dimitrios Karampinas

Conventional OLTP systems assign each transaction to a worker thread and that thread accesses data, depending on what the transaction dictates. This thread-to-transaction work assignment policy leads to unpredictable accesses. The unpredictability forces e ...

2011