Faith Ellen Fich, Panagiota Fatourou, Eric Ruppert, Franck van Breugel
This paper describes the first complete implementation of a non-blocking binary search tree in an asynchronous shared-memory system using single-word compare-and-swap operations. The implementation is linearizable and tolerates any number of crash ...
Johannes Schneider, Roger Wattenhofer
We introduce Multi-Trials, a new technique for symmetry breaking for distributed algorithms and apply it to various problems in general graphs. For instance, we present three randomized algorithms for distributed (vertex or edge) coloring improving ...
We describe an algorithm for Byzantine agreement that is scalable in the sense that each processor sends only Õ(√n) bits, where n is the total number of processors. Our algorithm succeeds with high probability against an adaptive adversary, which ...
Atish Das Sarma, Danupon Nanongkai, Gopal Pandurangan, Prasad Tetali
We focus on the problem of performing random walks efficiently in a distributed network. Given bandwidth constraints, the goal is to minimize the number of rounds required to obtain a random walk sample. We first present a fast sublinear time ...
Jurek Czyzowicz, Adrian Kosowski, Andrzej Pelc
Two identical (anonymous) mobile agents start from arbitrary nodes in an a priori unknown graph and move synchronously from node to node with the goal of meeting. This rendezvous problem has been thoroughly studied, both for anonymous and for labeled ...
Leonid Barenboim, Michael Elkin
Consider an n-vertex graph G = (V,E) of maximum degree Δ, and suppose that each vertex v ∈ V hosts a processor. The processors are allowed to communicate only with their neighbors in G. The communication is synchronous, i.e., it proceeds in ...
Dmitri Perelman, Rui Fan, Idit Keidar
An effective way to reduce the number of aborts in software transactional memory (STM) is to keep multiple versions of transactional objects. In this paper, we study inherent properties of STMs that use multiple versions to guarantee successful ...
Yongmin Tan, Xiaohui Gu, Haixun Wang
Large-scale hosting infrastructures require automatic system anomaly management to achieve continuous system operation. In this paper, we present a novel adaptive runtime anomaly prediction system, called ALERT, to achieve robust hosting ...
An edge dominating set for a graph G is a set D of edges such that each edge of G is in D or adjacent to at least one edge in D. This work studies deterministic distributed approximation algorithms for finding minimum-size edge dominating sets. The ...
Fabian Kuhn, Nancy A. Lynch, Calvin C. Newport, Rotem Oshman, Andréa W. Richa
Practitioners agree that unreliable links, which sometimes deliver messages and sometime do not, are an important characteristic of wireless networks. In contrast, most theoretical models of radio networks fix a static set of links and assume that ...