We study the dispersion problem for k mobile agents on an n-node anonymous, memory-less graph with maximum degree Δ. Agents must autonomously relocate so that no two agents occupy the same node. While an optimal O(k)-time, O(log(k + Δ))-memory algorithm is known under synchronous settings, the best known asynchronous algorithm requires O(k log min {k, Δ}) time due to the difficulty of distinguishing unvisited nodes from nodes temporarily vacated by agents. We close this gap by presenting the first fully asynchronous algorithm achieving asymptotically optimal O(k) time and O(log(k + Δ)) memory. Our main technical contribution is the Port-1 Tree (P1Tree), a novel structural property of a port-labeled graph. By forcing the DFS traversal to prioritize edges locally labeled with port 1, P1Tree allows agents to verify the status of neighboring nodes in O(1) asynchronous epochs without relying on timing assumptions or oscillations used in synchronous settings. We show that this approach yields optimal bounds for both rooted and general initial configurations.

The distributed Data Retrieval (DR) model consists of k peers connected by a complete peer-to-peer communication network, and a trusted external data source that stores an array X of n bits (n ≫ k). Up to β k of the peers might fail in any execution (for β ∈ [0, 1)). Peers can obtain the information either by inexpensive messages passed among themselves or through expensive queries to the source array X. In the DR model, we focus on designing protocols that minimize the number of queries performed by any nonfaulty peer (a measure referred to as the query complexity) while maximizing the resiliency parameter β. The Download problem requires each nonfaulty peer to correctly learn the entire array X. Earlier work on this problem focused on synchronous communication networks and established several deterministic and randomized upper and lower bounds. Our work is the first to extend the study of distributed data retrieval to asynchronous communication networks. We address the Download problem under both the Byzantine and crash failure models. We present query-optimal deterministic solutions in an asynchronous model that can tolerate any fixed fraction β < 1 of crash faults. In the Byzantine failure model, it is known that deterministic protocols incur a query complexity of Ω(n) per peer, even under synchrony. We extend this lower bound to randomized protocols in the asynchronous model for β ≥ 1/2, and further show that for β < 1/2, a randomized protocol exists with near-optimal query complexity.

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 of data can be learned by a peer either through a direct (costly) query of the source or through other peers that have already learned it; the goal is to design a collaborative protocol that reduces the maximum number of bits queried by any one peer ("query complexity"). We achieve optimal query complexity in a synchronous fully connected network with resilience to any constant fraction β < 1 of Byzantine peers, under varying assumptions regarding time and message size.

The dispersion problem has received much attention recently in the distributed computing literature. In this problem, k ≤ n agents placed initially arbitrarily on the nodes of an n-node, m-edge anonymous graph of maximum degree Δ have to reposition autonomously to reach a configuration in which each agent is on a distinct node of the graph. Dispersion is interesting as well as important due to its connections to many fundamental coordination problems by mobile agents on graphs, such as exploration, scattering, load balancing, relocation of self-driven electric cars (robots) to recharge stations (nodes), etc. The objective has been to provide a solution that optimizes simultaneously time and memory complexities. There exist graphs for which the lower bound on time complexity is Ω(k). Memory complexity is Ω(log k) per agent independent of graph topology. The state-of-the-art algorithms have (i) time complexity O(k log2 k) and memory complexity O(log(k + Δ)) under the synchronous setting [DISC'24] and (ii) time complexity O(min{m, kΔ}) and memory complexity O(log(k + Δ)) under the asynchronous setting [OPODIS'21]. In this paper, we improve substantially on this state-of-the-art. Under the synchronous setting as in [DISC'24], we present the first optimal O(k) time algorithm keeping memory complexity O(log(k + Δ)). Under the asynchronous setting as in [OPODIS'21], we present the first algorithm with time complexity O(k log k) keeping memory complexity O(log(k + Δ)), which is time-optimal within an O(log k) factor despite asynchrony. Both the results were obtained through novel techniques to quickly find empty nodes to settle agents, which may be of independent interest.

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 of data can be learned by a peer either through a direct and costly query of the source or through other peers that have already learned it; the goal is to design a collaborative protocol that reduces the query complexity defined as the maximum number of bits queried by any honest peer. We begin with a randomized protocol for the Download problem that achieves optimal query complexity, up to a logarithmic factor. For a stronger "dynamic" adversary that can change the set of Byzantine peers from one round to the next, we achieve optimality (within log factors) for both query complexity (in expectation) and time complexity, but with larger messages. In broadcast communication, where all peers (including Byzantine peers) are required to send the same message to all peers, we achieve (up to log factors) an optimal trade-off between query complexity, time complexity, and message size with the dynamic adversary. All of our protocols can tolerate any constant fraction β < 1 of Byzantine peers.

The distributed Data Retrieval (DR) model consists of k peers connected by a complete peer-to-peer communication network, and a trusted external data source that stores an array X of n bits (n ≫ k). Up to β k of the peers might fail in any execution (for β ∈ [0, 1)). Peers can obtain the information either by inexpensive messages passed among themselves or through expensive queries to the source array X. In the DR model, we focus on designing protocols that minimize the number of queries performed by any nonfaulty peer (a measure referred to as query complexity) while maximizing the resilience parameter β. The Download problem requires each nonfaulty peer to correctly learn the entire array X. Earlier work on this problem focused on synchronous communication networks and established several deterministic and randomized upper and lower bounds. Our work is the first to extend the study of distributed data retrieval to asynchronous communication networks. We address the Download problem under both the Byzantine and crash failure models. We present query-optimal deterministic solutions in an asynchronous model that can tolerate any fixed fraction β < 1 of crash faults. In the Byzantine failure model, it is known that deterministic protocols incur a query complexity of Ω(n) per peer, even under synchrony. We extend this lower bound to randomized protocols in the asynchronous model for β ≥ 1/2, and further show that for β < 1/2, a randomized protocol exists with near-optimal query complexity. To the best of our knowledge, this is the first work to address the Download problem in asynchronous communication networks.

We study the dispersion problem in anonymous port-labeled graphs: k ≤ n mobile agents, each with a unique ID and initially located arbitrarily on the nodes of an n-node graph with maximum degree Δ, must autonomously relocate so that no node hosts more than one agent. Dispersion serves as a fundamental task in the distributed computing of mobile agents, and its complexity stems from key challenges in local coordination under anonymity and limited memory. The goal is to minimize both the time to achieve dispersion and the memory required per agent. It is known that any algorithm requires Ω(k) time in the worst case, and Ω(log k) bits of memory per agent. A recent result [Kshemkalyani et al., 2025] gives an optimal O(k)-time algorithm in the synchronous setting and an O(k log k)-time algorithm in the asynchronous setting, both using O(log(k+Δ)) bits. We close the complexity gap in the asynchronous setting by presenting the first dispersion algorithm that runs in optimal O(k) time using O(log(k+Δ)) bits of memory per agent. Our solution relies on a novel technique for constructing a port-one tree in anonymous graphs, which may be of independent interest.

This article investigates the message complexity of two fundamental problems, leader election and agreement in the crash-fault synchronous and fully-connected distributed network. We present randomized (Monte Carlo) algorithms for both the problems and also show non-trivial lower bounds on the message complexity. Our algorithms achieve sublinear message complexity in the so-called implicit version of the two problems when tolerating more than a constant fraction of the faulty nodes. In comparison to the state-of-art, our results improved and extended the works of [Gilbert-Kowalski, SODA’10] (which studied only the agreement problem) in several directions. Specifically, our algorithms tolerate any number of faulty nodes up to$(n -\operatorname{polylog}n)$. The message complexity (and also the time complexity) of our algorithms is optimal (up to a$\operatorname{polylog}n$factor). Further, our algorithm works in anonymous networks, where nodes do not know each other. To the best of our knowledge, these are the first sub-linear results for both the leader election and the agreement problem in the crash-fault distributed networks.

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 also develop non-trivial lower bounds on the message complexity. In the so-called implicit version of the two problems, our algorithms achieve sublinear message complexity while tolerating more than a constant fraction of faulty nodes. The algorithms work in anonymous networks, where nodes do not know each other. Specifically, our main results are: (1)A randomized leader election algorithm which elects a leader with high probability in a complete network with n nodes, in which at least ⌉ n⌈ nodes are non-faulty and the remaining can be faulty, where ≥ (log2 n)/n. The time complexity of the algorithm is O (log nα) rounds and message complexity is O((n0.5 log2.5 n)/2.5) with high probability (i.e., with probability ≥ 1-1/n). A non-trivial lower bound of Ω(n0.5 / α1.5) messages for any leader election algorithm that tolerates at most (1-α)-fraction faulty nodes and succeeds with high probability. (2)A randomized algorithm, tolerating at most ⌊(1-α)n⌋ faulty nodes, solves agreement in O (log n/α) rounds and with high probability uses only O((n0.5 log1.5n)/α1.5) messages. A matching lower bound (up to a polylog n factor) of Ω (n0.5 /α1.5) messages for any agreement algorithm that tolerates at most (1-α)-fraction faulty nodes and succeeds with high probability. A full version of the paper is available at [17].