Skip to main content

Research Repository

Advanced Search

Outputs (29)

Brief Announcement: Broadcast via Mobile Agents in a Dynamic Network: Interplay of Graph Properties & Agents (2025)
Presentation / Conference Contribution
Moses, W. K., Redlich, A., & Stock, F. (2025, June). Brief Announcement: Broadcast via Mobile Agents in a Dynamic Network: Interplay of Graph Properties & Agents. Presented at Leibniz International Proceedings in Informatics Lipics, Liverpool, UK

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 the remaini... Read More about Brief Announcement: Broadcast via Mobile Agents in a Dynamic Network: Interplay of Graph Properties & Agents.

Towards Communication-Efficient Peer-to-Peer Networks (2024)
Presentation / Conference Contribution
Hourani, K., Moses Jr., W. K., & Pandurangan, G. (2024, September). Towards Communication-Efficient Peer-to-Peer Networks. Presented at 32nd Annual European Symposium on Algorithms (ESA 2024), Egham, United Kingdom

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 suc... Read More about Towards Communication-Efficient Peer-to-Peer Networks.

Exploiting Automorphisms of Temporal Graphs for Fast Exploration and Rendezvous (2024)
Presentation / Conference Contribution
Dogeas, K., Erlebach, T., Kammer, F., Meintrup, J., & Moses Jr, W. K. (2024, July). Exploiting Automorphisms of Temporal Graphs for Fast Exploration and Rendezvous. Presented at 51st EATCS International Colloquium on Automata, Languages and Programming, Tallinn, Estonia

Awake Complexity of Distributed Minimum Spanning Tree (2024)
Presentation / Conference Contribution
Augustine, J., Moses Jr, W. K., & Pandurangan, G. (2024, May). Awake Complexity of Distributed Minimum Spanning Tree. Presented at SIROCCO 2024: 31st International Colloquium On Structural Information and Communication Complexity, Vietri sul Mare, Salerno, Italy

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.
Reduci... Read More about Awake Complexity of Distributed Minimum Spanning Tree.

Time- and Communication-Efficient Overlay Network Construction via Gossip (2024)
Presentation / Conference Contribution
Dufoulon, F., Moorman, M., Moses Jr., W. K., & Pandurangan, G. (2024, January). Time- and Communication-Efficient Overlay Network Construction via Gossip. Presented at ITCS 2024: Innovations in Theoretical Computer Science (ITCS), Berkeley, California

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 ne... Read More about Time- and Communication-Efficient Overlay Network Construction via Gossip.

Dispersion, Capacitated Nodes, and the Power of a Trusted Shepherd (2024)
Presentation / Conference Contribution
Moses Jr., W. K., & Redlich, A. (2024, January). Dispersion, Capacitated Nodes, and the Power of a Trusted Shepherd. Presented at 25th International Conference on Distributed Computing and Networking, Chennai, India

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, to graphs w... Read More about Dispersion, Capacitated Nodes, and the Power of a Trusted Shepherd.

Efficient live exploration of a dynamic ring with mobile robots (2023)
Journal Article
Mandal, S., Molla, A. R., & Moses Jr., W. K. (2023). Efficient live exploration of a dynamic ring with mobile robots. Theoretical Computer Science, 980, Article 114201. https://doi.org/10.1016/j.tcs.2023.114201

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 important require... Read More about Efficient live exploration of a dynamic ring with mobile robots.

Fast Deterministic Gathering with Detection on Arbitrary Graphs: The Power of Many Robots (2023)
Presentation / Conference Contribution
Molla, A. R., Mondal, K., & Moses Jr., W. K. (2023, May). Fast Deterministic Gathering with Detection on Arbitrary Graphs: The Power of Many Robots. Presented at 37th IEEE International Parallel & Distributed Processing Symposium, St. Petersburg, Florida, USA

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. G... Read More about Fast Deterministic Gathering with Detection on Arbitrary Graphs: The Power of Many Robots.

Distributed MIS in O(log log n) Awake Complexity (2023)
Presentation / Conference Contribution
Dufoulon, F., Moses Jr., W. K., & Pandurangan, G. (2023, June). Distributed MIS in O(log log n) Awake Complexity. Presented at PODC '23: 2023 ACM Symposium on Principles of Distributed Computing, Orlando, Florida

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 genera... Read More about Distributed MIS in O(log log n) Awake Complexity.