Atish Das Sarma, Danupon Nanongkai, Gopal Pandurangan
Performing random walks in networks is a fundamental primitive that has found applications in many areas of computer science, including distributed computing. In this paper, we focus on the problem of performing random walks efficiently in a ...
Avinash Lakshman, Prashant Malik
Cassandra is a distributed storage system for managing structured data that is designed to scale to a very large size across many commodity servers, with no single point of failure. Reliability at massive scale is a very big challenge. Outages in the ...
Riko Jacob, Andréa W. Richa, Christian Scheideler, Stefan Schmid, Hanjo Täubig
Peer-to-peer systems rely on scalable overlay networks that enable efficient routing between its members. Hypercubic topologies facilitate such operations while each node only needs to connect to a small number of other nodes. In contrast to static ...
Alexander Fanghänel, Thomas Kesselheim, Harald Räcke, Berthold Vöcking
In the interference scheduling problem, one is given a set of n communication requests described by pairs of points from a metric space. The points correspond to devices in a wireless network. In the directed version of the problem, each pair of ...
Hervé Baumann, Pierluigi Crescenzi, Pierre Fraigniaud
An edge-Markovian process with birth-rate p and death-rate q generates sequences of graphs (G0,G1,G2,…) with the same node set [n] such that Gt is obtained from Gt−1 as follows: if e ∉ E(Gt−1) then e ∈ E(Gt) with probability p, and if e ∈ ...
Christoph Lenzen, Thomas Locher, Roger Wattenhofer
We present a novel clock synchronization algorithm and prove tight upper and lower bounds on the worst-case clock skew that may occur between any two participants in any given distributed system. More importantly, the worst-case clock skew between ...
Marcos Kawazoe Aguilera, Idit Keidar, Dahlia Malkhi, Alexander Shraer
This paper deals with the emulation of atomic read/write (R/W) storage in dynamic asynchronous message passing systems. In static settings, it is well known that atomic R/W storage can be implemented in a fault-tolerant manner even if the system is ...
A failure detector is a distributed oracle that provides processes in a distributed system with hints about failures. The notion of a weakest failure detector captures the exact amount of synchrony needed for solving a given distributed computing ...