We consider consensus protocols in the model that is most commonly considered for use in state machine replication, as initiated by Dwork-Lynch-Stockmeyer, then by Castro-Liskov in 1999 with "PBFT." Such protocols guarantee, assuming n players out of ...

We give a randomness-efficient Massively Parallel Computation (MPC) algorithm for deciding whether an undirected graph is connected. For Connectivity on n-vertex, m-edge graphs whose components have diameter at most D = 2o(log n/ log log n), our ...

We consider networks of small, autonomous devices that communicate with each other wirelessly. Minimizing energy usage is an important consideration in designing algorithms for such networks, as battery life is a crucial and limited resource. Working in ...

This paper investigates on the message complexity of the two fundamental problems, namely, leader election and agreement in the crash-fault synchronous and fully-connected distributed network. We present randomized algorithms for both the problems and ...

It is well known that Byzantine fault tolerant (BFT) consensus cannot be solved in the classic asynchronous message passing model when one-third or more of the processes may be faulty. Since many modern applications require higher fault tolerance, this ...

Approximate agreement is a weaker version of consensus where two or more processes must agree on a real number within a distance ε of each other. Many variants of this task have been considered in the literature: continuous or discrete ones; multi-...

This brief announcement presents an algorithm for (1+ε) approximate single-source shortest paths for directed graphs with non-negative real edge weights in the CONGEST model that runs in Õ ((n^1/2 +D+n^2/5+o(1) D^2/5 )log W / ε^2) rounds, where W is the ...

Linearizability is the de facto consistency condition for concurrent objects, widely used in theory and practice. Loosely speaking, linearizability classifies concurrent executions as correct if operations on shared objects appear to take effect ...

The recent commercial release of persistent main memory by Intel has sparked intense interest in recoverable concurrent objects. Specifying and implementing such objects is technically challenging on current generation hardware precisely because the top ...

The popularity of permissioned blockchain systems demands BFT SMR protocols that are efficient under good network conditions (synchrony) and robust under bad network conditions (asynchrony). The state-of-the-art partially synchronous BFT SMR protocols ...

Over the years, population protocols with the goal of reaching consensus have been studied in great depth. However, many systems in the real-world do not result in all agents eventually reaching consensus, but rather in the opposite: they converge to a ...

The standard single-writer snapshot type allows processes to obtain a consistent snapshot of an array of n memory locations, each of which can be updated by one of n processes. In almost all algorithms, a \Scan operation returns a linearizable snapshot ...

We present a tight RMR complexity lower bound for the recoverable mutual exclusion (RME) problem, defined by Golab and Ramaraju [9]. In particular, we show that any n-process RME algorithm using only atomic read, write, fetch-and-store, fetch-and-...

We present a deterministic O(log log log n)-round low-space Massively Parallel Computation (MPC) algorithm for the classical problem of (Δ+1)-coloring on n-vertex graphs. In this model, every machine has sublinear local space of size n^φ for any ...

Studying distributed computing through the lens of algebraic topology has been the source of many significant breakthroughs during the last two decades, especially in the design of lower bounds or impossibility results for deterministic algorithms. In a ...

We prove that any n-node graph G with diameter D admits shortcuts with congestion O(δ D log n) and dilation O(δ D), where δ is the maximum edge-density of any minor of G. Our proof is simple and constructive with a tildeΘ (δ D)-round1 distributed ...

Consider any locally checkable labeling problem Π in rooted regular trees: there is a finite set of labels Σ, and for each label χ x Σ we specify what are permitted label combinations of the children for an internal node of label x (the leaf nodes are ...

Network decomposition is a central concept in the study of distributed graph algorithms. We present the first polylogarithmic-round deterministic distributed algorithm with small messages that constructs a strong-diameter network decomposition with ...

We show how to construct an overlay network of constant degree and diameter O(log n) in time O(log n) starting from an arbitrary weakly connected graph. We assume a synchronous communication network in which nodes can send messages to nodes they know ...

The Local Computation Algorithm (LCA) model is a popular model in the field of sublinear-time algorithms that measures the complexity of an algorithm by the number of probes the algorithm makes in the neighborhood of one node to determine that node's ...