Distributed Computing
Publisher: Springer Nature · ISSN 0178-2770,1432-0452 · 25 articles
-
Distributed download from an external data source in Byzantine majority settings
We consider the Download problem in the Data Retrieval Model, introduced in DISC’24, where a distributed set of peers, some of which may be Byzantine, seek to learn n bits of data stored at a trustworthy external data source. Each bit...
-
Scalable distributed agreement from LWE: Byzantine agreement, broadcast, and leader election
Distributed agreement is a general name for the task of ensuring consensus among non-faulty nodes in the presence of faulty or malicious behavior. Well-known instances of agreement tasks are Byzantine Agreement, Broadcast, and Committee...
-
Approach of agents with restricted fuel tanks
Two mobile agents, modeled as points in the plane moving at speed 1, have to get at a distance at most 1 from each other. This task is known as approach or rendezvous in the plane. An adversary initially places both agents at distinct...
-
Non-uniform content-oblivious leader election in 2-edge-connected networks
Censor-Hillel, Cohen, Gelles, and Sela (PODC 2022 & Distributed Computing 2023) studied fully-defective asynchronous networks, where communication channels may suffer an extreme form of alteration errors, rendering messages completely...
-
On the notions of bounded bypass, and how to make any deadlock-free MUTEX protocol satisfy one of them
In the literature on mutual exclusion, bounded bypass has been used for a long time as a strengthening of starvation-freedom, but, to the best of our knowledge, it still lacks a satisfying definition as a liveness property on its own....
-
Exploration on highly dynamic graphs
We study the exploration problem by mobile agents in two prominent models of dynamic graphs: 1-Interval Connectivity and T -Connectivity Time. The 1-Interval Connectivity model was introduced by Kuhn et al. [STOC 2010], and the T...
-
Demand-aware plane Spanners of Bounded Degree
Plane spanners of bounded degree are efficient communication backbones for networks. As the performance requirements of applications are becoming increasingly stringent, it is crucial to design networks in a way that data transmissions...
-
Optimal simultaneous Byzantine Agreement, common knowledge and limited information exchange
In order to develop solutions that perform actions as early as possible, analysis of distributed algorithms using epistemic logic has generally concentrated on “full-information protocols”, which may be inefficient with respect to space...
-
Time-optimal self-stabilizing leader election in population protocols
We consider the standard population protocol model, where ( a priori ) indistinguishable and anonymous agents interact in pairs according to uniformly random scheduling. The self-stabilizing leader election problem requires the protocol...
-
Team formation and applications
A novel long-lived distributed problem, called Team Formation (TF) , is introduced together with a message- and time-efficient randomized algorithm. The problem is defined over the asynchronous model with a complete communication graph,...
-
Memory lower bounds and impossibility results for anonymous dynamic broadcast
Broadcast is a ubiquitous distributed computing problem that underpins many other system tasks. In static, connected networks, it was recently shown that broadcast is solvable without any node memory and only constant-size messages in...
-
A topological characterization of stabilizing consensus
We provide a complete characterization of the solvability/impossibility of deterministic stabilizing consensus in virtually any computing model with benign process and communication faults using point-set topology. Relying on the...
-
Satrapy: From abstract to practical consensus for heterogeneous quorum systems
The traditional Byzantine quorum-system model assumes a pre-existing, global agreement on the set of quorums (typically defined as the sets consisting of more than two-thirds of the participants). This assumption is problematic in...
-
Polylogarithmic time algorithms for shortest path forests in programmable matter
In this paper, we study the computation of shortest paths within the geometric amoebot model , a commonly used model for programmable matter. Shortest paths are essential for various tasks and therefore have been heavily investigated in...
-
Connectivity Labeling in Faulty Colored Graphs
Fault-tolerant connectivity labelings are schemes that, given an n -vertex graph $$G=(V,E)$$ G = ( V , E ) and a parameter f , produce succinct yet informative labels for the elements of the graph. Given only the labels of two vertices...
-
Improved all-pairs approximate shortest paths in congested clique
In this paper, we present a new randomized O (1)-approximation algorithm for the All-Pairs Shortest Paths (APSP) problem in weighted undirected graphs that runs in just $$O(\log \log \log n)$$ rounds in the Congested-Clique model....
-
Content-oblivious leader election on rings
In content-oblivious computation , n nodes wish to compute a given task over an asynchronous network that suffers from an extremely harsh type of noise, which corrupts the content of all messages across all channels. In a recent work,...
-
Universal pattern formation by oblivious robots under sequential schedulers
We study the computational power that oblivious robots operating in the plane have under sequential schedulers. We show that this power is much stronger than the obvious capacity these schedulers offer of breaking symmetry, and thus to...
-
Gathering teams of bounded memory agents on a line
Several mobile agents, modelled as deterministic automata, navigate in an infinite line in synchronous rounds. All agents start in the same round. In each round, an agent can move to one of the two neighboring nodes, or stay idle....
-
Distributed MIS in O(log log n) Awake Complexity
Maximal Independent Set (MIS) is one of the fundamental and most well-studied problems in distributed graph algorithms. Even after four decades of intensive research, the best known (randomized) MIS algorithms have $$O(\log {n})$$ round...
-
Constant-round spanners and shortest paths in congested clique and MPC
In this work we present the first constant-round algorithms for computing spanners and approximate All-Pairs Shortest Paths (APSP) in the distributed Congested Clique model. Specifically, we show the following results for undirected n...
-
Byzantine-tolerant distributed grow-only sets: specification and applications
In order to formalize Distributed Ledger Technologies and their interconnections, recent research has introduced the concept of a Distributed Ledger Object (denoted $$\mathcal {O}^L$$ ), a concurrent abstraction that maintains a totally...
-
Narrowing the LOCAL–CONGEST gaps in sparse networks via expander decompositions
Many combinatorial optimization problems, including maximum weighted matching and maximum independent set, can be approximated within $$(1 \pm \epsilon )$$ factors in $$\operatorname {poly}(\log n, 1/\epsilon )$$ rounds in the...
-
Near-linear time dispersion of mobile agents
Consider that there are $$k\le n$$ agents in a simple, connected, and undirected graph $$G=(V,E)$$ with n nodes and $$m$$ edges. The goal of the dispersion problem is to move these $$k$$ agents to mutually distinct nodes. Agents can...
-
The computational power of distributed shared-memory models with bounded-size registers
The celebrated Asynchronous Computability Theorem of Herlihy and Shavit (JACM 1999) provided a topological characterization of the tasks that are wait-free solvable by processes communicating through writing and reading shared...