Skip to main content

Research Repository

Advanced Search

Outputs (28)

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.

An Almost Singularly Optimal Asynchronous Distributed MST Algorithm (2022)
Presentation / Conference Contribution
Dufoulon, F., Kutten, S., Moses Jr., W. K., Pandurangan, G., & Peleg, D. (2022, December). An Almost Singularly Optimal Asynchronous Distributed MST Algorithm. Presented at 36th International Symposium on Distributed Computing (DISC 2022)

Byzantine Dispersion on Graphs (2021)
Presentation / Conference Contribution
Molla, A. R., Mondal, K., & Moses Jr., W. K. (2021, December). Byzantine Dispersion on Graphs. Presented at 2021 IEEE International Parallel and Distributed Processing Symposium (IPDPS)

Efficient Deterministic Leader Election for Programmable Matter (2021)
Presentation / Conference Contribution
Dufoulon, F., Kutten, S., & Moses Jr., W. K. (2021, December). Efficient Deterministic Leader Election for Programmable Matter. Presented at Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing

Singularly Near Optimal Leader Election in Asynchronous Networks (2021)
Presentation / Conference Contribution
Kutten, S., Moses Jr., W. K., Pandurangan, G., & Peleg, D. (2021, December). Singularly Near Optimal Leader Election in Asynchronous Networks. Presented at 35th International Symposium on Distributed Computing (DISC 2021)

Singularly Optimal Randomized Leader Election (2020)
Presentation / Conference Contribution
Kutten, S., Moses Jr., W. K., Pandurangan, G., & Peleg, D. (2020, December). Singularly Optimal Randomized Leader Election. Presented at 34th International Symposium on Distributed Computing (DISC 2020)