Publications related to Synchronizing without Locks is Inherently Expensive

Introducing Speculation in Self-Stabilization: An Application to Mutual Exclusion

Self-stabilization ensures that, after any transient fault, the system recovers in a finite time and eventually exhibits correct behavior. Speculation consists in guaranteeing that the system satisfies its requirements for any execution but exhibits signif ...

2013

Randomized versus Deterministic Implementations of Concurrent Data Structures

Dan Alistarh

One of the key trends in computing over the past two decades has been increased distribution, both at the processor level, where multi-core architectures are now the norm, and at the system level, where many key services are currently distributed overmulti ...

EPFL2012

How to Allocate Tasks Asynchronously

Rachid Guerraoui, Seth Gilbert, Dan Alistarh

Asynchronous task allocation is a fundamental problem in distributed computing, in which p asyn- chronous 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 bui ...

2012

Neutralité et engagement. Les relations entre le Comité international de la Croix-Rouge et le gouvernement suisse pendant la Seconde Guerre mondiale

Isabelle Barbara Marie-Hélène Cardia

Since its creation in 1863, the ICRC has maintained a special relationship with Switzerland and its government, based on the pursuit of neutrality and on the perception of a common destiny. Such a perception and the adherence to shared political values wer ...

Société d'histoire de la Suisse romande2012

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

Optimal-Time Adaptive Strong Renaming, with Applications to Counting

Seth Gilbert, Dan Alistarh, Morteza Zadimoghaddam

We give two new randomized algorithms for tight renaming, both of which work against an adaptive adversary. The first uses repeated sampling over a sequence of arrays of decreasing size to assign unique names to each of

n

processes with step complexity $ ...

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

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

Repeater Insertion Techniques for 3D Interconnects

Giovanni De Micheli, Vasileios Pavlidis

A new approach for inserting repeaters in 3-D interconnects is proposed. The allocation of repeaters along an interplane interconnect is iteratively determined. The proposed approach is compared with two other techniques based on conventional methods used ...

2010

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

The Semantics of Progress in Lock-Based Transactional Memory

Rachid Guerraoui, Michal Kapalka

Transactional memory (TM) is a promising paradigm for concurrent programming. Whereas the number of TM implementations is growing, however, little research has been conducted to precisely define TM semantics, especially their progress guarantees. This pape ...

ACM2009

Synchronizing without Locks is Inherently Expensive

Graph Chatbot

Chat with Graph Search

Introducing Speculation in Self-Stabilization: An Application to Mutual Exclusion

Randomized versus Deterministic Implementations of Concurrent Data Structures

How to Allocate Tasks Asynchronously

Neutralité et engagement. Les relations entre le Comité international de la Croix-Rouge et le gouvernement suisse pendant la Seconde Guerre mondiale

The complexity of robust atomic storage

Optimal-Time Adaptive Strong Renaming, with Applications to Counting

Cache-Aware Lock-Free Concurrent Hash Tries

Repeater Insertion Techniques for 3D Interconnects

Tight Failure Detection Bounds on Atomic Object Implementations

The Semantics of Progress in Lock-Based Transactional Memory

How to Allocate Tasks Asynchronously

Randomized versus Deterministic Implementations of Concurrent Data Structures

Neutralité et engagement. Les relations entre le Comité international de la Croix-Rouge et le gouvernement suisse pendant la Seconde Guerre mondiale

Optimal-Time Adaptive Strong Renaming, with Applications to Counting

Tight Failure Detection Bounds on Atomic Object Implementations

Repeater Insertion Techniques for 3D Interconnects

Cache-Aware Lock-Free Concurrent Hash Tries

The Semantics of Progress in Lock-Based Transactional Memory

The complexity of robust atomic storage

Introducing Speculation in Self-Stabilization: An Application to Mutual Exclusion