Andrzej Czygrinow, Michal Hanckowiak, Wojciech Wawrzyniak
We give deterministic distributed algorithms that given δ> 0 find in a planar graph G, (1±δ)-approximations of a maximum independent set, a maximum matching, and a minimum dominating set. The algorithms run in O(log*|G|) rounds. In addition, ...
Maurice Herlihy, Nir Shavit, Moran Tzafrir
We present a new class of resizable sequential and concurrent hash map algorithms directed at both uni-processor and multicore machines. The new hopscotch algorithms are based on a novel hopscotch multi-phased probing and displacement technique that ...
Rachid Guerraoui, Thomas A. Henzinger, Vasu Singh
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 ...
Iyad A. Kanj, Ljubomir Perkovic, Ge Xia
We consider the problem of computing bounded-degree lightweight plane spanners of unit disk graphs in the local distributed model of computation. We are motivated by the hypothesis that such subgraphs can provide the underlying network topology for ...
Carole Delporte-Gallet, Hugues Fauconnier, Rachid Guerraoui, Andreas Tielmann
In the set-agreement problem, n processes seek to agree on at most n − 1 different values. This paper determines the weakest failure detector to solve this problem in a message-passing system where processes may fail by crashing. This failure ...
Amitanand S. Aiyer, Lorenzo Alvisi, Rida A. Bazzi, Allen Clement
We present the first general implementation to provide the properties of digital signature using MACs in a system consisting of any number of untrusted clients and n servers, up to f of which are Byzantine. At the heart of the implementation is a ...
Robert Danek, Wojciech M. Golab
First-Come-First-Served (FCFS) mutual exclusion (ME) is the problem of ensuring that processes attempting to concurrently access a shared resource do so one by one, in a fair order. In this paper, we close the complexity gap between FCFS ME and ME in ...