We study gossip algorithms for the fundamental rumor spreading problem, where the goal is to disseminate a rumor from a given source node to all nodes in an arbitrary (and unknown) graph. Gossip algorithms allow each node to call only one neighbor per round and are therefore highly message-efficient, with low per-node communication overhead per round. The state of the art works present fast gossip algorithms, however they typically leverage large-sized messages. This undermines the lightweight communication advantage of gossip, since even though only one neighbor is contacted per round, the message size can be linear in í µí±, the network size. Hence, a fundamental question is whether one can perform fast gossip using small messages. The main contribution of this paper is to answer the above question in the affirmative and present two gossip algorithms that achieve fast rumor spreading using messages of polylog 𝑛 size. Specifically , we show the following results: (1) We present a gossip algorithm for rumor spreading that runs in 𝑂(𝑐 log𝑛/Φ𝑐 ) rounds for every 𝑐 ⩾ 1, and Φ𝑐 is the weak conductance. Our algorithm's run time not only improves over the Censor-Hillel-Shachnai bound [SODA 2011; SICOMP 2012], but more significantly, it uses messages of small (polylog 𝑛) size, unlike the prior work that used messages of large (at least linear in 𝑛) size. Our bound in terms of weak conductance is essentially optimal. (2) We also present a gossip algorithm for rumor spreading that depends on the network diameter (and is independent of the graph's conductance), which runs in \tilde{𝑂}(𝐷 +√𝑛) rounds with high probability and uses small (polylog 𝑛 size) messages. Our bound is a significant improvement over the gossip algorithm of \tilde{𝑂}(√𝑛𝐷) due to Ghaffari and Kuhn [DISC 2018], which also uses small-sized messages. We note that our algorithm (unlike that of Ghaffari and Kuhn) is optimal for when 𝐷 = Ω(√𝑛). Furthermore, our gossip algorithm can be modified to output a minimum spanning tree (MST) in the same number of rounds, which is essentially round-optimal (even for non-gossip algorithms). Our gossip algorithms use graph sketches [Ahn, Guha, McGregor, SODA 2012] in a novel way to overcome communication bottlenecks and achieve small communication overhead with small message sizes.

Abstract 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 complexity on general graphs [Luby, STOC 1986] (where n is the number of nodes), while the best known lower bound is $$\Omega (\sqrt{\log {n}/\log \log {n}})$$ [Kuhn, Moscibroda, Wattenhofer, JACM 2016]. Breaking past the $$O(\log {n})$$ round complexity upper bound or showing stronger lower bounds have been longstanding open problems. Energy is a premium resource in various settings such as battery-powered wireless networks and sensor networks. The bulk of the energy is used by nodes when they are awake , i.e., when they are sending, receiving, and even just listening for messages. On the other hand, when a node is sleeping , it does not perform any communication and thus spends very little energy. Several recent works have addressed the problem of designing energy-efficient distributed algorithms for various fundamental problems. These algorithms operate by minimizing the number of rounds in which any node is awake , also called the (worst-case) awake complexity . An intriguing open question is whether one can design a distributed MIS algorithm that has significantly smaller awake complexity compared to existing algorithms. In particular, the question of obtaining a distributed MIS algorithm with $$o(\log n)$$ awake complexity was left open in [Chatterjee, Gmyr, Pandurangan, PODC 2020]. Our main contribution is to show that MIS can be computed in awake complexity that is exponentially better compared to the best known round complexity of $$O(\log n)$$ and also bypassing its fundamental $$\Omega (\sqrt{\log {n}/\log \log {n}})$$ round complexity lower bound exponentially. Specifically, we show that MIS can be computed by a randomized distributed (Monte Carlo) algorithm in $$O(\log \log {n} )$$ awake complexity with high probability (i.e., with probability at least $$1 - n^{-1}$$ ). This algorithm has a round complexity of $$O((\log ^7 n) \log \log n)$$ . We also show that we can improve the round complexity at the cost of a slight increase in awake complexity, by presenting a randomized distributed (Monte Carlo) algorithm for MIS that, with high probability, computes an MIS in $$O((\log \log {n})\log ^*n)$$ awake complexity and $$O((\log ^3 n) (\log \log n) \log ^*n)$$ round complexity. Our algorithms work in the $$\mathcal{CONGEST}$$ model where messages of size $$O(\log n)$$ bits can be sent per edge per round.

We focus on designing Peer-to-Peer (P2P) networks that enable efficient communication. Over the last two decades, there has been substantial algorithmic research on distributed protocols for building P2P networks with various desirable properties such as high expansion, low diameter, and robustness to a large number of deletions. A key underlying theme in all of these works is to distributively build a random graph topology that guarantees the above properties. Moreover, the random connectivity topology is widely deployed in many P2P systems today, including those that implement blockchains and cryptocurrencies. However, a major drawback of using a random graph topology for a P2P network is that the random topology does not respect the underlying (Internet) communication topology. This creates a large propagation delay, which is a major communication bottleneck in modern P2P networks. In this paper, we work towards designing P2P networks that are communication-efficient (having small propagation delay) with provable guarantees. Our main contribution is an efficient, decentralized protocol, Close-Weaver, that transforms a random graph topology embedded in an underlying Euclidean space into a topology that also respects the underlying metric. We then present efficient point-to-point routing and broadcast protocols that achieve essentially optimal performance with respect to the underlying space.

Temporal graphs are graphs where the edge set can change in each time step, and the vertex set stays the same. Exploration of temporal graphs whose snapshot in each time step is a connected graph, called connected temporal graphs, has been widely studied. We extend the concept of graph automorphisms from static graphs to temporal graphs and show that symmetries enable faster exploration: We prove that a connected temporal graph with $n$ vertices and orbit number $r$ (i.e., $r$ is the number of automorphism orbits) can be explored in $O(r n^{1+ε})$ time steps, for any fixed $ε>0$. For $r=O(n^c)$ for constant $c<1$, this is a significant improvement over the known tight worst-case bound of $Θ(n^2)$ time steps for arbitrary connected temporal graphs. We also give two lower bounds for exploration, showing that $Ω(n \log n)$ time steps are required for some inputs with $r=O(1)$ and that $Ω(rn)$ time steps are required for some inputs for any $r$ with $1\le r\le n$. The techniques we develop for fast exploration are used to derive the following result for rendezvous in connected temporal graphs: Two agents are placed by an adversary at arbitrary vertices and given full information about the temporal graph, except that they do not have consistent vertex labels. The agents can meet at a common vertex after $O(n^{1+ε})$ time steps, for any $ε>0$. For some connected temporal graphs with constant orbit number we present a complementary lower bound of $Ω(n\log n)$ time steps. Finally, we give a randomized algorithm to construct a temporal walk $W$ that visits all vertices of a given orbit with probability at least $1-ε$ for any $0<ε<1$ such that $W$ spans $O((n^{5/3}+rn)\log n)$ time steps. The runtime of this algorithm consists of $O(n^{1/3} \log (n/ε))$ linear-time scans of the snapshots that exist in this time span.

We focus on the well-studied problem of distributed overlay network construction. We consider a synchronous gossip-based communication model where in each round a node can send a message of small size to another node whose identifier it knows. The network is assumed to be reconfigurable, i.e., a node can add new connections (edges) to other nodes whose identifier it knows or drop existing connections. Each node initially has only knowledge of its own identifier and the identifiers of its neighbors. The overlay construction problem is, given an arbitrary (connected) graph, to reconfigure it to obtain a bounded-degree expander graph as efficiently as possible. The overlay construction problem is relevant to building real-world peer-to-peer network topologies that have desirable properties such as low diameter, high conductance, robustness to adversarial deletions, etc. Our main result is that we show that starting from any arbitrary (connected) graph G on n nodes and m edges, we can construct an overlay network that is a constant-degree expander in polylog rounds using only Õ(n) messages. Our time and message bounds are both essentially optimal (up to polylogarithmic factors). Our distributed overlay construction protocol is very lightweight as it uses gossip (each node communicates with only one neighbor in each round) and also scalable as it uses only Õ(n) messages, which is sublinear in m (even when m is moderately dense). To the best of our knowledge, this is the first result that achieves overlay network construction in polylog rounds and o(m) messages. Our protocol uses graph sketches in a novel way to construct an expander overlay that is both time and communication efficient. A consequence of our overlay construction protocol is that distributed computation can be performed very efficiently in this model. In particular, a wide range of fundamental tasks such as broadcast, leader election, and minimum spanning tree (MST) construction can be accomplished in polylog rounds and Õ(n) message complexity in any graph.

Over the years, much research involving mobile computational entities has been performed. From modeling actual microscopic (and smaller) robots, to modeling software processes on a network, many important problems have been studied in this context. Gathering is one such fundamental problem in this area. The problem of gathering k robots, initially arbitrarily placed on the nodes of an n-node graph, asks that these robots coordinate and communicate in a local manner, as opposed to global, to move around the graph, find each other, and settle down on a single node as fast as possible. A more difficult problem to solve is gathering with detection, where once the robots gather, they must subsequently realize that gathering has occurred and then terminate.In this paper, we propose a deterministic approach to solve gathering with detection for any arbitrary connected graph that is faster than existing deterministic solutions for even just gathering (without the requirement of detection) for arbitrary graphs. In contrast to earlier work on gathering, it leverages the fact that there are more robots present in the system to achieve gathering with detection faster than those previous papers that focused on just gathering. The state of the art solution for deterministic gathering [Ta-Shma and Zwick, TALG, 2014] takes $\tilde O\left({{n^5}\log \ell }\right)$ rounds, where is the smallest label among robots and $\tilde O$ hides a polylog factor. We design a deterministic algorithm for gathering with detection with the following trade-offs depending on how many robots are present: (i) when k ≥ ⌊n/2⌋ + 1, the algorithm takes O(n3) rounds, (ii) when k ≥ ⌊n/3⌋ + 1, the algorithm takes O(n4log n) rounds, and (iii) otherwise, the algorithm takes $\tilde O\left({{n^5}}\right)$ rounds. The algorithm is not required to know k, but only n.

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 complexity on general graphs [Luby, STOC 1986] (where n is the number of nodes), while the best known lower bound is [EQUATION] [Kuhn, Moscibroda, Wattenhofer, JACM 2016]. Breaking past the O(log n) round complexity upper bound or showing stronger lower bounds have been longstanding open problems.

We study the distributed minimum spanning tree (MST) problem, a fundamental problem in distributed computing. It is well-known that distributed MST can be solved in Õ(D+√n) rounds in the standard CONGEST model (where n is the network size and D is the network diameter) and this is essentially the best possible round complexity (up to logarithmic factors). However, in resource-constrained networks such as wireless ad hoc and sensor networks, nodes spending so much time can lead to significant spending of resources such as energy.

A singularly (near) optimal distributed algorithm is one that is (near) optimal in \emph{two} criteria, namely, its time and message complexities. For \emph{synchronous} CONGEST networks, such algorithms are known for fundamental distributed computing problems such as leader election [Kutten et al., JACM 2015] and Minimum Spanning Tree (MST) construction [Pandurangan et al., STOC 2017, Elkin, PODC 2017]. However, it is open whether a singularly (near) optimal bound can be obtained for the MST construction problem in general \emph{asynchronous} CONGEST networks. We present a randomized distributed MST algorithm that, with high probability, computes an MST in \emph{asynchronous} CONGEST networks and takes $\tilde{O}(D^{1+ε} + \sqrt{n})$ time and $\tilde{O}(m)$ messages, where $n$ is the number of nodes, $m$ the number of edges, $D$ is the diameter of the network, and $ε>0$ is an arbitrarily small constant (both time and message bounds hold with high probability). Our algorithm is message optimal (up to a polylog$(n)$ factor) and almost time optimal (except for a $D^ε$ factor). Our result answers an open question raised in Mashregi and King [DISC 2019] by giving the first known asynchronous MST algorithm that has sublinear time (for all $D = O(n^{1-ε})$) and uses $\tilde{O}(m)$ messages. Using a result of Mashregi and King [DISC 2019], this also yields the first asynchronous MST algorithm that is sublinear in both time and messages in the $KT_1$ CONGEST model. A key tool in our algorithm is the construction of a low diameter rooted spanning tree in asynchronous CONGEST that has depth $\tilde{O}(D^{1+ε})$ (for an arbitrarily small constant $ε> 0$) in $\tilde{O}(D^{1+ε})$ time and $\tilde{O}(m)$ messages. To the best of our knowledge, this is the first such construction that is almost singularly optimal in the asynchronous setting.

Abstract. Load balancing is a well-studied problem, with balls-in-bins being the primary framework. The greedy algorithm [Formula: see text] of Azar et al. [ SIAM J. Comput., 29 (1999), pp. 180–200] places each ball by probing [Formula: see text] random bins and placing the ball in the least loaded of them. With high probability, the maximum load under [Formula: see text] is exponentially lower than the result when balls are placed uniformly randomly. Vöcking [ J. ACM, 50 (2003), pp. 568–589] showed that a slightly asymmetric variant, [Formula: see text], provides a further significant improvement. However, this improvement comes at the additional computational cost of imposing structure on the bins. Here, we present a fully decentralized and easy-to-implement algorithm called [Formula: see text] that combines the simplicity of [Formula: see text] and the improved balance of [Formula: see text]. The key idea in [Formula: see text] is to probe until a different bin size from the first observation is located and then place the ball. Although the number of probes could be quite large for some of the balls, we show that [Formula: see text] requires only at most [Formula: see text] probes on average per ball (in both the standard and the heavily loaded settings). Thus the number of probes is no greater than that of either [Formula: see text] or [Formula: see text]. More importantly, we show that [Formula: see text] closely matches the improved maximum load ensured by [Formula: see text] in both the standard and heavily loaded settings. We further provide a tight lower bound on the maximum load up to [Formula: see text] terms. We additionally give experimental data that [Formula: see text] is indeed as good as [Formula: see text], if not better, in practice.

This paper considers the problem of Byzantine dispersion and extends previous work along several parameters. The problem of Byzantine dispersion asks: given n robots, up tofof which are Byzantine, initially placed arbitrarily on annnode anonymous graph, design a terminating algorithm to be run by the robots such that they eventually reach a configuration where each node has at most one non-Byzantine robot on it. Previous work solved this problem for rings and tolerated up ton- 1 Byzantine robots. In this paper, we investigate the problem on more general graphs. We first develop an algorithm that tolerates up ton- 1 Byzantine robots and works for a more general class of graphs. We then develop an algorithm that works for any graph but tolerates a lesser number of Byzantine robots. We subsequently turn our focus to the strength of the Byzantine robots. Previous work considers only “weak” Byzantine robots that cannot fake their IDs. We develop an algorithm that solves the problem when Byzantine robots are not weak and can fake IDs. Finally, we study the situation where the number of the robots is not n but somek. We show that in such a scenario, the number of Byzantine robots that can be tolerated is severely restricted. Specifically, we show that it is impossible to deterministically solve Byzantine dispersion when ⌈k/n⌉ > ⌈(k-f)/n⌉.

It was suggested that a programmable matter system (composed of multiple computationally weak mobile particles) should remain connected at all times since otherwise, reconnection is difficult and may be impossible. At the same time, it was not clear that allowing the system to disconnect carried a significant advantage in terms of time complexity. We demonstrate for a fundamental task, that of leader election, an algorithm where the system disconnects and then reconnects automatically in a non-trivial way (particles can move far away from their former neighbors and later reconnect to others). Moreover, the runtime of the temporarily disconnecting deterministic leader election algorithm is linear in the diameter. Hence, the disconnecting -- reconnecting algorithm is as fast as previous randomized algorithms. When comparing to previous deterministic algorithms, we note that some of the previous work assumed weaker schedulers. Still, the runtime of all the previous deterministic algorithms that did not assume special shapes of the particle system (shapes with no holes) was at least quadratic in n, where n is the number of particles in the system. (Moreover, the new algorithm is even faster in some parameters than the deterministic algorithms that did assume special initial shapes.)

This paper concerns designing distributed algorithms that are singularly optimal, i.e., algorithms that are simultaneously time and message optimal, for the fundamental leader election problem in asynchronous networks. Kutten et al. (JACM 2015) presented a singularly near optimal randomized leader election algorithm for general synchronous networks that ran in O(D) time and used O(m log n) messages (where D, m, and n are the network’s diameter, number of edges and number of nodes, respectively) with high probability. Both bounds are near optimal (up to a logarithmic factor), since Ω(D) and Ω(m) are the respective lower bounds for time and messages for leader election even for synchronous networks and even for (Monte-Carlo) randomized algorithms. On the other hand, for general asynchronous networks, leader election algorithms are only known that are either time or message optimal, but not both. Kutten et al. (DISC 2020) presented a randomized asynchronous leader election algorithm that is singularly near optimal for complete networks, but left open the problem for general networks. This paper shows that singularly near optimal (up to polylogarithmic factors) bounds can be achieved for general asynchronous networks. We present a randomized singularly near optimal leader election algorithm that runs in O(D + log² n) time and O(m log² n) messages with high probability. Our result is the first known distributed leader election algorithm for asynchronous networks that is near optimal with respect to both time and message complexity and improves over a long line of results including the classical results of Gallager et al. (ACM TOPLAS, 1983), Peleg (JPDC, 1989), and Awerbuch (STOC, 89).

Addressing a fundamental problem in programmable matter, we present the first deterministic algorithm to elect a unique leader in a system of connected amoebots assuming only that amoebots are initially contracted. Previous algorithms either used randomization, made various assumptions (shapes with no holes, or known shared chirality), or elected several co-leaders in some cases. Some of the building blocks we introduce in constructing the algorithm are of interest by themselves, especially the procedure we present for reaching common chirality among the amoebots. Given the leader election and the chirality agreement building block, it is known that various tasks in programmable matter can be performed or improved. The main idea of the new algorithm is the usage of the ability of the amoebots to move, which previous leader election algorithms have not used.

Load balancing is a well-studied problem, with balls-inbins being the primary framework. The greedy algorithm Greedy[d] of Azar et al. places each ball by probing d > 1 random bins and placing the ball in the least loaded of them. It ensures a maximum load that is exponentially better than the strategy of placing each ball uniformly at random. Vöcking showed that a slightly asymmetric variant, Left[d], provides a further significant improvement. However, this improvement comes at an additional computational cost of imposing structure on the bins. Here, we present a fully decentralized and easy-to-implement algorithm called FirstDiff[d] that combines the simplicity of Greedy[d] and the improved balance of Left[d]. The key idea in FirstDiff[d] is to probe until a different bin size from the first observation is located, then place the ball. Although the number of probes could be quite large for some of the balls, we show that FirstDiff[d] requires only d probes on average per ball (in both the standard and the heavily-loaded settings). Thus the number of probes is no greater than either that of Greedy[d] or Left[d]. More importantly, we show that FirstDiff[d] closely matches the improved maximum load ensured by Left[d] in both the standard and heavily-loaded settings. We additionally give experimental data that FirstDiff[d] is indeed as good as Left[d], if not better, in practice.