William K. Moses
YOU?
Author Swipe
View article: Brief Announcement: Broadcast via Mobile Agents in a Dynamic Network: Interplay of Graph Properties & Agents
Brief Announcement: Broadcast via Mobile Agents in a Dynamic Network: Interplay of Graph Properties & Agents Open
In this paper, we revisit the problem of Broadcast, introduced by Das, Giachoudis, Luccio, and Markou [OPODIS, 2020], where k+1 agents are initially placed on an n node dynamic graph, where 1 agent has a message that must be broadcast to t…
View article: Dispersion, Capacitated Nodes, and the Power of a Trusted Shepherd
Dispersion, Capacitated Nodes, and the Power of a Trusted Shepherd Open
In this paper, we look at and expand the problems of dispersion and Byzantine dispersion of mobile robots on a graph, introduced by Augustine and Moses Jr. [ICDCN 2018] and by Molla, Mondal, and Moses Jr. [ALGOSENSORS 2020], respectively, …
View article: Towards Communication-Efficient Peer-To-Peer Networks
Towards Communication-Efficient Peer-To-Peer Networks Open
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 pro…
View article: Awake Complexity of Distributed Minimum Spanning Tree
Awake Complexity of Distributed Minimum Spanning Tree Open
The \emph{awake complexity} of a distributed algorithm measures the number of rounds in which a node is awake. When a node is not awake, it is {\em sleeping} and does not do any computation or communication and spends very little resources…
View article: Exploiting Automorphisms of Temporal Graphs for Fast Exploration and Rendezvous
Exploiting Automorphisms of Temporal Graphs for Fast Exploration and Rendezvous Open
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…
View article: Time- and Communication-Efficient Overlay Network Construction via Gossip
Time- and Communication-Efficient Overlay Network Construction via Gossip Open
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 kn…
View article: Dispersion, Capacitated Nodes, and the Power of a Trusted Shepherd
Dispersion, Capacitated Nodes, and the Power of a Trusted Shepherd Open
In this paper, we look at and expand the problems of dispersion and Byzantine dispersion of mobile robots on a graph, introduced by Augustine and Moses~Jr.~[ICDCN~2018] and by Molla, Mondal, and Moses~Jr.~[ALGOSENSORS~2020], respectively, …
View article: Efficient live exploration of a dynamic ring with mobile robots
Efficient live exploration of a dynamic ring with mobile robots Open
The graph exploration problem requires a group of mobile robots, initially placed arbitrarily on the nodes of a graph, to work collaboratively to explore the graph such that each node is eventually visited by at least one robot. One import…
View article: Distributed MIS in O(log log n) Awake Complexity
Distributed MIS in O(log log n) Awake Complexity Open
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 complexit…
View article: Fast Deterministic Gathering with Detection on Arbitrary Graphs: The Power of Many Robots
Fast Deterministic Gathering with Detection on Arbitrary Graphs: The Power of Many Robots Open
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…
View article: Fast Deterministic Gathering with Detection on Arbitrary Graphs: The Power of Many Robots
Fast Deterministic Gathering with Detection on Arbitrary Graphs: The Power of Many Robots Open
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…
View article: Balanced Allocation: Patience Is Not a Virtue
Balanced Allocation: Patience Is Not a Virtue Open
Load balancing is a well-studied problem, with balls-in-bins being the primary framework. The greedy algorithm of Azar et al. [SIAM J. Comput., 29 (1999), pp. 180–200] places each ball by probing random bins and placing the ball in the lea…
View article: An Almost Singularly Optimal Asynchronous Distributed MST Algorithm
An Almost Singularly Optimal Asynchronous Distributed MST Algorithm Open
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 distribut…
View article: Brief Announcement: Distributed MST Computation in the Sleeping Model: Awake-Optimal Algorithms and Lower Bounds
Brief Announcement: Distributed MST Computation in the Sleeping Model: Awake-Optimal Algorithms and Lower Bounds Open
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 …
View article: Distributed MIS in $O(\log\log{n} )$ Awake Complexity
Distributed MIS in $O(\log\log{n} )$ Awake Complexity Open
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 compl…
View article: Awake Complexity of Distributed Minimum Spanning Tree
Awake Complexity of Distributed Minimum Spanning Tree Open
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 $\tilde{O}(D+\sqrt{n})$ rounds in the standard CONGEST model (where $n$ is…
View article: Distributed Algorithms for Connectivity and MST in Large Graphs with Efficient Local Computation
Distributed Algorithms for Connectivity and MST in Large Graphs with Efficient Local Computation Open
We study distributed algorithms for large-scale graphs, focusing on the fundamental problems of connectivity and minimum spanning tree (MST). We consider the k-machine model, a well-studied model for distributed computing for large-scale g…
View article: Dispersion of Mobile Robots
Dispersion of Mobile Robots Open
In this tutorial, we provide an extensive survey of the work on dispersion of mobile robots, introduced by Augustine and Moses Jr. [ICDCN 2018]. The problem of dispersion of k robots, initially arbitrarily placed on the nodes of an n node …
View article: Singularly Near Optimal Leader Election in Asynchronous Networks
Singularly Near Optimal Leader Election in Asynchronous Networks Open
This paper concerns designing distributed algorithms that are {\em singularly optimal}, i.e., algorithms that are {\em simultaneously} time and message {\em optimal}, for the fundamental leader election problem in {\em asynchronous} networ…
View article: Efficient Deterministic Leader Election for Programmable Matter
Efficient Deterministic Leader Election for Programmable Matter Open
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…
View article: Optimal dispersion on an anonymous ring in the presence of weak Byzantine robots
Optimal dispersion on an anonymous ring in the presence of weak Byzantine robots Open
The problem of dispersion of mobile robots on a graph asks that n robots initially placed arbitrarily on the nodes of an n-node anonymous graph, autonomously move to reach a final configuration where each node has at most one robot on it. …
View article: Byzantine Dispersion on Graphs
Byzantine Dispersion on Graphs Open
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 to $f$ of which are Byzantine, initially placed arbitrarily on an $…
View article: Singularly Optimal Randomized Leader Election
Singularly Optimal Randomized Leader Election Open
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 networks. Our main result is a randomized d…
View article: Deterministic Leader Election in Programmable Matter
Deterministic Leader Election in Programmable Matter Open
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 eith…
View article: Dispersion of Mobile Robots
Dispersion of Mobile Robots Open
We introduce a new problem in the domain of mobile robots, which we term dispersion. In this problem, n robots are placed in an n node graph arbitrarily and must coordinate with each other to reach a final configuration such that exactly o…