Published in: LIPIcs, Volume 302, 35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024)
Shuma Kumamoto, Shuji Kijima, and Tomoyuki Shirai. The Recurrence/Transience of Random Walks on a Bounded Grid in an Increasing Dimension. In 35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 302, pp. 22:1-22:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{kumamoto_et_al:LIPIcs.AofA.2024.22, author = {Kumamoto, Shuma and Kijima, Shuji and Shirai, Tomoyuki}, title = {{The Recurrence/Transience of Random Walks on a Bounded Grid in an Increasing Dimension}}, booktitle = {35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024)}, pages = {22:1--22:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-329-4}, ISSN = {1868-8969}, year = {2024}, volume = {302}, editor = {Mailler, C\'{e}cile and Wild, Sebastian}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2024.22}, URN = {urn:nbn:de:0030-drops-204577}, doi = {10.4230/LIPIcs.AofA.2024.22}, annote = {Keywords: Random walk, dynamic graph, recurrence, transience, coupling} }
Published in: LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024)
Fabien Dufoulon, Shreyas Pai, Gopal Pandurangan, Sriram V. Pemmaraju, and Peter Robinson. The Message Complexity of Distributed Graph Optimization. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 41:1-41:26, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{dufoulon_et_al:LIPIcs.ITCS.2024.41, author = {Dufoulon, Fabien and Pai, Shreyas and Pandurangan, Gopal and Pemmaraju, Sriram V. and Robinson, Peter}, title = {{The Message Complexity of Distributed Graph Optimization}}, booktitle = {15th Innovations in Theoretical Computer Science Conference (ITCS 2024)}, pages = {41:1--41:26}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-309-6}, ISSN = {1868-8969}, year = {2024}, volume = {287}, editor = {Guruswami, Venkatesan}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2024.41}, URN = {urn:nbn:de:0030-drops-195690}, doi = {10.4230/LIPIcs.ITCS.2024.41}, annote = {Keywords: Distributed graph algorithm, message complexity, distributed approximation} }
Published in: LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024)
Fabien Dufoulon, Michael Moorman, William K. Moses Jr., and Gopal Pandurangan. Time- and Communication-Efficient Overlay Network Construction via Gossip. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 42:1-42:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{dufoulon_et_al:LIPIcs.ITCS.2024.42, author = {Dufoulon, Fabien and Moorman, Michael and Moses Jr., William K. and Pandurangan, Gopal}, title = {{Time- and Communication-Efficient Overlay Network Construction via Gossip}}, booktitle = {15th Innovations in Theoretical Computer Science Conference (ITCS 2024)}, pages = {42:1--42:23}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-309-6}, ISSN = {1868-8969}, year = {2024}, volume = {287}, editor = {Guruswami, Venkatesan}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2024.42}, URN = {urn:nbn:de:0030-drops-195700}, doi = {10.4230/LIPIcs.ITCS.2024.42}, annote = {Keywords: Peer-to-Peer Networks, Overlay Construction Protocol, Gossip, Expanders, Sublinear Bounds} }
Published in: LIPIcs, Volume 246, 36th International Symposium on Distributed Computing (DISC 2022)
John Augustine, Anisur Rahaman Molla, Gopal Pandurangan, and Yadu Vasudev. Byzantine Connectivity Testing in the Congested Clique. In 36th International Symposium on Distributed Computing (DISC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 246, pp. 7:1-7:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{augustine_et_al:LIPIcs.DISC.2022.7, author = {Augustine, John and Molla, Anisur Rahaman and Pandurangan, Gopal and Vasudev, Yadu}, title = {{Byzantine Connectivity Testing in the Congested Clique}}, booktitle = {36th International Symposium on Distributed Computing (DISC 2022)}, pages = {7:1--7:21}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-255-6}, ISSN = {1868-8969}, year = {2022}, volume = {246}, editor = {Scheideler, Christian}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2022.7}, URN = {urn:nbn:de:0030-drops-171987}, doi = {10.4230/LIPIcs.DISC.2022.7}, annote = {Keywords: Byzantine protocols, distributed graph algorithms, congested clique, graph connectivity, fault-tolerant computation, randomized algorithms} }
Published in: LIPIcs, Volume 246, 36th International Symposium on Distributed Computing (DISC 2022)
Fabien Dufoulon, Shay Kutten, William K. Moses Jr., Gopal Pandurangan, and David Peleg. An Almost Singularly Optimal Asynchronous Distributed MST Algorithm. In 36th International Symposium on Distributed Computing (DISC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 246, pp. 19:1-19:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{dufoulon_et_al:LIPIcs.DISC.2022.19, author = {Dufoulon, Fabien and Kutten, Shay and Moses Jr., William K. and Pandurangan, Gopal and Peleg, David}, title = {{An Almost Singularly Optimal Asynchronous Distributed MST Algorithm}}, booktitle = {36th International Symposium on Distributed Computing (DISC 2022)}, pages = {19:1--19:24}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-255-6}, ISSN = {1868-8969}, year = {2022}, volume = {246}, editor = {Scheideler, Christian}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2022.19}, URN = {urn:nbn:de:0030-drops-172107}, doi = {10.4230/LIPIcs.DISC.2022.19}, annote = {Keywords: Asynchronous networks, Minimum Spanning Tree, Distributed Algorithm, Singularly Optimal} }
Published in: LIPIcs, Volume 209, 35th International Symposium on Distributed Computing (DISC 2021)
Shay Kutten, William K. Moses Jr., Gopal Pandurangan, and David Peleg. Singularly Near Optimal Leader Election in Asynchronous Networks. In 35th International Symposium on Distributed Computing (DISC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 209, pp. 27:1-27:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{kutten_et_al:LIPIcs.DISC.2021.27, author = {Kutten, Shay and Moses Jr., William K. and Pandurangan, Gopal and Peleg, David}, title = {{Singularly Near Optimal Leader Election in Asynchronous Networks}}, booktitle = {35th International Symposium on Distributed Computing (DISC 2021)}, pages = {27:1--27:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-210-5}, ISSN = {1868-8969}, year = {2021}, volume = {209}, editor = {Gilbert, Seth}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2021.27}, URN = {urn:nbn:de:0030-drops-148294}, doi = {10.4230/LIPIcs.DISC.2021.27}, annote = {Keywords: Leader election, Singular optimality, Randomized algorithms, Asynchronous networks, Arbitrary graphs} }
Published in: LIPIcs, Volume 179, 34th International Symposium on Distributed Computing (DISC 2020)
Shay Kutten, William K. Moses Jr., Gopal Pandurangan, and David Peleg. Singularly Optimal Randomized Leader Election. In 34th International Symposium on Distributed Computing (DISC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 179, pp. 22:1-22:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{kutten_et_al:LIPIcs.DISC.2020.22, author = {Kutten, Shay and Moses Jr., William K. and Pandurangan, Gopal and Peleg, David}, title = {{Singularly Optimal Randomized Leader Election}}, booktitle = {34th International Symposium on Distributed Computing (DISC 2020)}, pages = {22:1--22:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-168-9}, ISSN = {1868-8969}, year = {2020}, volume = {179}, editor = {Attiya, Hagit}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2020.22}, URN = {urn:nbn:de:0030-drops-131002}, doi = {10.4230/LIPIcs.DISC.2020.22}, annote = {Keywords: Leader election, Asynchronous systems, Randomized algorithms, Singularly optimal, Complete networks} }
Published in: LIPIcs, Volume 179, 34th International Symposium on Distributed Computing (DISC 2020)
John Augustine, Valerie King, Anisur Rahaman Molla, Gopal Pandurangan, and Jared Saia. Scalable and Secure Computation Among Strangers: Message-Competitive Byzantine Protocols. In 34th International Symposium on Distributed Computing (DISC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 179, pp. 31:1-31:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{augustine_et_al:LIPIcs.DISC.2020.31, author = {Augustine, John and King, Valerie and Molla, Anisur Rahaman and Pandurangan, Gopal and Saia, Jared}, title = {{Scalable and Secure Computation Among Strangers: Message-Competitive Byzantine Protocols}}, booktitle = {34th International Symposium on Distributed Computing (DISC 2020)}, pages = {31:1--31:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-168-9}, ISSN = {1868-8969}, year = {2020}, volume = {179}, editor = {Attiya, Hagit}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2020.31}, URN = {urn:nbn:de:0030-drops-131093}, doi = {10.4230/LIPIcs.DISC.2020.31}, annote = {Keywords: Byzantine protocols, Byzantine agreement, Leader election, Committee election, Message-competitive protocol, Randomized protocol} }
Published in: LIPIcs, Volume 121, 32nd International Symposium on Distributed Computing (DISC 2018)
Robert Gmyr and Gopal Pandurangan. Time-Message Trade-Offs in Distributed Algorithms. In 32nd International Symposium on Distributed Computing (DISC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 121, pp. 32:1-32:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{gmyr_et_al:LIPIcs.DISC.2018.32, author = {Gmyr, Robert and Pandurangan, Gopal}, title = {{Time-Message Trade-Offs in Distributed Algorithms}}, booktitle = {32nd International Symposium on Distributed Computing (DISC 2018)}, pages = {32:1--32:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-092-7}, ISSN = {1868-8969}, year = {2018}, volume = {121}, editor = {Schmid, Ulrich and Widder, Josef}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2018.32}, URN = {urn:nbn:de:0030-drops-98216}, doi = {10.4230/LIPIcs.DISC.2018.32}, annote = {Keywords: Randomized Algorithm, KT\underline1 Model, Sparsifier, MST, Singular Optimality} }
Published in: LIPIcs, Volume 91, 31st International Symposium on Distributed Computing (DISC 2017)
Shreyas Pai, Gopal Pandurangan, Sriram V. Pemmaraju, Talal Riaz, and Peter Robinson. Symmetry Breaking in the Congest Model: Time- and Message-Efficient Algorithms for Ruling Sets. In 31st International Symposium on Distributed Computing (DISC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 91, pp. 38:1-38:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{pai_et_al:LIPIcs.DISC.2017.38, author = {Pai, Shreyas and Pandurangan, Gopal and Pemmaraju, Sriram V. and Riaz, Talal and Robinson, Peter}, title = {{Symmetry Breaking in the Congest Model: Time- and Message-Efficient Algorithms for Ruling Sets}}, booktitle = {31st International Symposium on Distributed Computing (DISC 2017)}, pages = {38:1--38:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-053-8}, ISSN = {1868-8969}, year = {2017}, volume = {91}, editor = {Richa, Andr\'{e}a}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2017.38}, URN = {urn:nbn:de:0030-drops-80132}, doi = {10.4230/LIPIcs.DISC.2017.38}, annote = {Keywords: Congest model, Local model, Maximal independent set, Message complexity, Round complexity, Ruling sets, Symmetry breaking} }