Exploiting Automorphisms of Temporal Graphs for Fast Exploration and Rendezvous
(2024)
Conference Proceeding
Dogeas, K., Erlebach, T., Kammer, F., Meintrup, J., & Moses Jr, W. K. (in press). Exploiting Automorphisms of Temporal Graphs for Fast Exploration and Rendezvous. In Proceedings of the 51st EATCS International Colloquium on Automata, Languages and Programming (62:1-62:19). https://doi.org/10.4230/LIPIcs.ICALP.2024.62
Outputs (27)
Awake Complexity of Distributed Minimum Spanning Tree (2024)
Conference Proceeding
Augustine, J., Moses Jr, W. K., & Pandurangan, G. (in press). Awake Complexity of Distributed Minimum Spanning Tree.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.
Dispersion, Capacitated Nodes, and the Power of a Trusted Shepherd (2024)
Conference Proceeding
Moses Jr., W. K., & Redlich, A. (2024). Dispersion, Capacitated Nodes, and the Power of a Trusted Shepherd. In ICDCN '24: Proceedings of the 25th International Conference on Distributed Computing and Networking (400-405). https://doi.org/10.1145/3631461.3632310In 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.
Time- and Communication-Efficient Overlay Network Construction via Gossip (2023)
Conference Proceeding
Dufoulon, F., Moorman, M., Moses Jr., W. K., & Pandurangan, G. (in press). Time- and Communication-Efficient Overlay Network Construction via Gossip. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024) (42:1-42:23). https://doi.org/10.4230/LIPIcs.ITCS.2024.42
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.114201The 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)
Conference Proceeding
Molla, A. R., Mondal, K., & Moses Jr., W. K. (2023). Fast Deterministic Gathering with Detection on Arbitrary Graphs: The Power of Many Robots. In 2023 IEEE International Parallel and Distributed Processing Symposium (IPDPS) (47-57). https://doi.org/10.1109/IPDPS54959.2023.00015Over 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)
Conference Proceeding
Dufoulon, F., Moses Jr., W. K., & Pandurangan, G. (2023). Distributed MIS in O(log log n) Awake Complexity. In A. Nolin (Ed.), . https://doi.org/10.1145/3583668.3594574Maximal 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.
Dispersion of Mobile Robots (2022)
Other
Molla, A. R., & Moses Jr., W. K. (2022). Dispersion of Mobile Robots
An Almost Singularly Optimal Asynchronous Distributed MST Algorithm (2022)
Conference Proceeding
Dufoulon, F., Kutten, S., Moses Jr., W. K., Pandurangan, G., & Peleg, D. (2022). An Almost Singularly Optimal Asynchronous Distributed MST Algorithm. In S. Scheideler (Ed.), . https://doi.org/10.4230/lipics.disc.2022.19
Brief Announcement: Distributed MST Computation in the Sleeping Model: Awake-Optimal Algorithms and Lower Bounds (2022)
Conference Proceeding
Augustine, J., Moses Jr., W. K., & Pandurangan, G. (2022). Brief Announcement: Distributed MST Computation in the Sleeping Model: Awake-Optimal Algorithms and Lower Bounds. . https://doi.org/10.1145/3519270.3538459
Distributed Algorithms for Connectivity and MST in Large Graphs with Efficient Local Computation (2022)
Conference Proceeding
Ajieren, E., Hourani, K., Moses Jr., W. K., & Pandurangan, G. (2022). Distributed Algorithms for Connectivity and MST in Large Graphs with Efficient Local Computation. . https://doi.org/10.1145/3491003.3491011
Balanced Allocation: Patience Is Not a Virtue (2022)
Journal Article
Augustine, J., Moses Jr., W. K., Redlich, A., & Upfal, E. (2022). Balanced Allocation: Patience Is Not a Virtue. SIAM Journal on Computing, 51(6), https://doi.org/10.1137/17m1155375
Singularly Near Optimal Leader Election in Asynchronous Networks (2021)
Conference Proceeding
Kutten, S., Moses Jr., W. K., Pandurangan, G., & Peleg, D. (2021). Singularly Near Optimal Leader Election in Asynchronous Networks. In S. Gilbert (Ed.), . https://doi.org/10.4230/lipics.disc.2021.27
Deterministic protocols in the SINR model without knowledge of coordinates (2021)
Journal Article
Moses Jr., W. K., & Vaya, S. (2021). Deterministic protocols in the SINR model without knowledge of coordinates. Journal of Computer and System Sciences, 115, https://doi.org/10.1016/j.jcss.2020.06.002
Optimal dispersion on an anonymous ring in the presence of weak Byzantine robots (2021)
Journal Article
Molla, A. R., Mondal, K., & Moses Jr., W. K. (2021). Optimal dispersion on an anonymous ring in the presence of weak Byzantine robots. Theoretical Computer Science, 887, https://doi.org/10.1016/j.tcs.2021.07.008
Byzantine Dispersion on Graphs (2021)
Conference Proceeding
Molla, A. R., Mondal, K., & Moses Jr., W. K. (2021). Byzantine Dispersion on Graphs. . https://doi.org/10.1109/ipdps49936.2021.00103
Efficient Deterministic Leader Election for Programmable Matter (2021)
Conference Proceeding
Dufoulon, F., Kutten, S., & Moses Jr., W. K. (2021). Efficient Deterministic Leader Election for Programmable Matter. . https://doi.org/10.1145/3465084.3467900
Live Exploration with Mobile Robots in a Dynamic Ring, Revisited (2020)
Conference Proceeding
Mandal, S., Molla, A. R., & Moses Jr., W. K. (2020). Live Exploration with Mobile Robots in a Dynamic Ring, Revisited. In Algorithms for Sensor Systems (92-107). https://doi.org/10.1007/978-3-030-62401-9_7
Efficient Dispersion on an Anonymous Ring in the Presence of Weak Byzantine Robots (2020)
Conference Proceeding
Molla, A. R., Mondal, K., & Moses Jr., W. K. (2020). Efficient Dispersion on an Anonymous Ring in the Presence of Weak Byzantine Robots. In Algorithms for Sensor Systems (154-169). https://doi.org/10.1007/978-3-030-62401-9_11
Singularly Optimal Randomized Leader Election (2020)
Conference Proceeding
Kutten, S., Moses Jr., W. K., Pandurangan, G., & Peleg, D. (2020). Singularly Optimal Randomized Leader Election. In H. Attiya (Ed.), . https://doi.org/10.4230/lipics.disc.2020.22
Deterministic Leader Election in Programmable Matter (2019)
Conference Proceeding
Emek, Y., Kutten, S., Lavi, R., & Moses Jr., W. K. (2019). Deterministic Leader Election in Programmable Matter. In C. Baier, I. Chatzigiannakis, P. Flocchini, & S. Leonardi (Eds.), . https://doi.org/10.4230/lipics.icalp.2019.140
Dispersion of Mobile Robots: The Power of Randomness (2019)
Conference Proceeding
Molla, A. R., & Moses Jr., W. K. (2019). Dispersion of Mobile Robots: The Power of Randomness. In Theory and Applications of Models of Computation (481-500). https://doi.org/10.1007/978-3-030-14812-6_30
Deterministic Dispersion of Mobile Robots in Dynamic Rings (2018)
Conference Proceeding
Agarwalla, A., Augustine, J., Moses Jr., W. K., Sankar K., M., & Sridhar, A. K. (2018). Deterministic Dispersion of Mobile Robots in Dynamic Rings. . https://doi.org/10.1145/3154273.3154294
Dispersion of Mobile Robots (2018)
Conference Proceeding
Augustine, J., & Moses Jr., W. K. (2018). Dispersion of Mobile Robots. . https://doi.org/10.1145/3154273.3154293
Balanced Allocation: Patience is not a Virtue (2016)
Conference Proceeding
Augustine, J., Moses Jr., W. K., Redlich, A., & Upfal, E. (2016). Balanced Allocation: Patience is not a Virtue. . https://doi.org/10.1137/1.9781611974331.ch48
Rational Secret Sharing with Honest Players over an Asynchronous Channel (2011)
Conference Proceeding
Moses Jr., W. K., & Pandu Rangan, C. (2011). Rational Secret Sharing with Honest Players over an Asynchronous Channel. In Advances in Network Security and Applications. https://doi.org/10.1007/978-3-642-22540-6_40
Rational Secret Sharing Over an Asynchronous Broadcast Channel With Information Theoretic Security (2011)
Journal Article
Moses Jr., W. K., & Pandu Rangan, C. (2011). Rational Secret Sharing Over an Asynchronous Broadcast Channel With Information Theoretic Security. International journal of network security and its applications, 3(6), https://doi.org/10.5121/ijnsa.2011.3601