Peter Robinson

Xianbin Zhu

Proceedings of the 15th Innovations in Theoretical Computer Science Conference, 2024

The Message Complexity of Distributed Graph Optimization.

[BibT_eX]

[DOI]

Proceedings of the 15th Innovations in Theoretical Computer Science Conference, 2024

2023

Leader Election in Well-Connected Graphs.

[BibT_eX]

[DOI]

Algorithmica, April, 2023

Distributed Sketching Lower Bounds for k-Edge Connected Spanning Subgraphs, BFS Trees, and LCL Problems.

[BibT_eX]

[DOI]

Proceedings of the 37th International Symposium on Distributed Computing, 2023

Brief Announcement: What Can We Compute in a Single Round of the Congested Clique?

[BibT_eX]

[DOI]

Proceedings of the 2023 ACM Symposium on Principles of Distributed Computing, 2023

Improved Tradeoffs for Leader Election.

[BibT_eX]

[DOI]

Proceedings of the 2023 ACM Symposium on Principles of Distributed Computing, 2023

Tight Bounds on the Message Complexity of Distributed Tree Verification.

[BibT_eX]

[DOI]

Shay Kutten

Ming Ming Tan

Proceedings of the 27th International Conference on Principles of Distributed Systems, 2023

2022

Latency, capacity, and distributed minimum spanning trees.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2022

What Can We Compute in a Single Round of the Congested Clique?

[BibT_eX]

[DOI]

CoRR, 2022

Awake-Efficient Distributed Algorithms for Maximal Independent Set.

[BibT_eX]

[DOI]

Khalid Hourani

Proceedings of the 42nd IEEE International Conference on Distributed Computing Systems, 2022

Byzantine-Resilient Counting in Networks.

[BibT_eX]

[DOI]

Proceedings of the 42nd IEEE International Conference on Distributed Computing Systems, 2022

2021

On the Distributed Complexity of Large-Scale Graph Computations.

[BibT_eX]

[DOI]

ACM Trans. Parallel Comput., 2021

Robust Lower Bounds for Graph Problems in the Blackboard Model of Communication.

[BibT_eX]

[DOI]

Christian Konrad

Viktor Zamaraev

CoRR, 2021

Being Fast Means Being Chatty: The Local Information Cost of Graph Spanners.

[BibT_eX]

[DOI]

Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, 2021

Can We Break Symmetry with o(m) Communication?

[BibT_eX]

[DOI]

Proceedings of the PODC '21: ACM Symposium on Principles of Distributed Computing, 2021

2020

A Time- and Message-Optimal Distributed Algorithm for Minimum Spanning Trees.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2020

The complexity of leader election in diameter-two networks.

[BibT_eX]

[DOI]

Distributed Comput., 2020

DConstructor: Efficient and Robust Network Construction with Polylogarithmic Overhead.

[BibT_eX]

[DOI]

Proceedings of the PODC '20: ACM Symposium on Principles of Distributed Computing, 2020

Latency, Capacity, and Distributed Minimum Spanning Tree†.

[BibT_eX]

[DOI]

Proceedings of the 40th IEEE International Conference on Distributed Computing Systems, 2020

2019

Slow Links, Fast Links, and the Cost of Gossip.

[BibT_eX]

[DOI]

IEEE Trans. Parallel Distributed Syst., 2019

Latency, Capacity, and Distributed MST.

[BibT_eX]

[DOI]

CoRR, 2019

The Complexity of Symmetry Breaking in Massive Graphs.

[BibT_eX]

[DOI]

Proceedings of the 33rd International Symposium on Distributed Computing, 2019

Network Size Estimation in Small-World Networks Under Byzantine Faults.

[BibT_eX]

[DOI]

Proceedings of the 2019 IEEE International Parallel and Distributed Processing Symposium, 2019

On the hardness of the strongly dependent decision problem.

[BibT_eX]

[DOI]

Proceedings of the 20th International Conference on Distributed Computing and Networking, 2019

2018

Fast Distributed Algorithms for Connectivity and MST in Large Graphs.

[BibT_eX]

[DOI]

ACM Trans. Parallel Comput., 2018

Special Issue of ICDCN 2016 (Distributed Computing Track).

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2018

Gracefully degrading consensus and k-set agreement in directed dynamic networks.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2018

The Distributed Minimum Spanning Tree Problem.

[BibT_eX]

[DOI]

Bull. EATCS, 2018

Breaking the Ω̃(√n) Barrier: Fast Consensus under a Late Adversary.

[BibT_eX]

[DOI]

Christian Scheideler

Alexander Setzer

CoRR, 2018

Fault-Tolerant Consensus with an Abstract MAC Layer.

[BibT_eX]

[DOI]

Calvin Newport

Proceedings of the 32nd International Symposium on Distributed Computing, 2018

Breaking the $ilde$Omega($sqrt{n})$ Barrier: Fast Consensus under a Late Adversary.

[BibT_eX]

[DOI]

Christian Scheideler

Alexander Setzer

Proceedings of the 30th on Symposium on Parallelism in Algorithms and Architectures, 2018

Session details: Session 1D: Graph Algorithms.

[BibT_eX]

[DOI]

Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing, 2018

The Complexity of Leader Election: A Chasm at Diameter Two.

[BibT_eX]

[DOI]

Proceedings of the 19th International Conference on Distributed Computing and Networking, 2018

2017

Symmetry Breaking in the Congest Model: Time- and Message-Efficient Algorithms for Ruling Sets.

[BibT_eX]

[DOI]

Proceedings of the 31st International Symposium on Distributed Computing, 2017

Brief Announcement: Symmetry Breaking in the CONGEST Model: Time- and Message-Efficient Algorithms for Ruling Sets.

[BibT_eX]

[DOI]

Proceedings of the ACM Symposium on Principles of Distributed Computing, 2017

Brief Announcement: Gossiping with Latencies.

[BibT_eX]

[DOI]

Proceedings of the ACM Symposium on Principles of Distributed Computing, 2017

2016

Distributed Algorithmic Foundations of Dynamic Networks.

[BibT_eX]

[DOI]

John Augustine

SIGACT News, 2016

Efficient computation of sparse structures.

[BibT_eX]

[DOI]

Random Struct. Algorithms, 2016

DEX: self-healing expanders.

[BibT_eX]

[DOI]

Amitabh Trehan

Distributed Comput., 2016

Tight Bounds for Distributed Graph Computations.

[BibT_eX]

[DOI]

CoRR, 2016

Gossiping with Latencies.

[BibT_eX]

[DOI]

CoRR, 2016

2015

Sublinear bounds for randomized leader election.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2015

Distributed agreement in dynamic peer-to-peer networks.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2015

On the Complexity of Universal Leader Election.

[BibT_eX]

[DOI]

J. ACM, 2015

Almost Optimal Distributed Algorithms for Large-Scale Graph Problems.

[BibT_eX]

[DOI]

CoRR, 2015

Fast Byzantine Leader Election in Dynamic Networks.

[BibT_eX]

[DOI]

John Augustine

Proceedings of the Distributed Computing - 29th International Symposium, 2015

Distributed Computation of Large-scale Graph Problems.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 2015

Gracefully Degrading Consensus and k-Set Agreement in Directed Dynamic Networks.

[BibT_eX]

[DOI]

Proceedings of the Networked Systems - Third International Conference, 2015

Enabling Robust and Efficient Distributed Computation in Dynamic Peer-to-Peer Networks.

[BibT_eX]

[DOI]

Proceedings of the IEEE 56th Annual Symposium on Foundations of Computer Science, 2015

2014

The Generalized Loneliness Detector and Weak System Models for k-Set Agreement.

[BibT_eX]

[DOI]

IEEE Trans. Parallel Distributed Syst., 2014

Distributed Symmetry Breaking in Hypergraphs.

[BibT_eX]

[DOI]

Proceedings of the Distributed Computing - 28th International Symposium, 2014

Brief announcement: gracefully degrading consensus and k-set agreement under dynamic link failures.

[BibT_eX]

[DOI]

Proceedings of the ACM Symposium on Principles of Distributed Computing, 2014

2013

The Distributed Complexity of Large-scale Graph Processing.

[BibT_eX]

[DOI]

CoRR, 2013

Robust Leader Election in a Fast-Changing World.

[BibT_eX]

[DOI]

Proceedings of the Proceedings Ninth International Workshop on Foundations of Mobile Computing, 2013

Storage and search in dynamic peer-to-peer networks.

[BibT_eX]

[DOI]

Proceedings of the 25th ACM Symposium on Parallelism in Algorithms and Architectures, 2013

Fast byzantine agreement in dynamic networks.

[BibT_eX]

[DOI]

John Augustine

Proceedings of the ACM Symposium on Principles of Distributed Computing, 2013

Efficient Computation of Balanced Structures.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages, and Programming - 40th International Colloquium, 2013

2012

Self-healing Deterministic Expanders

[BibT_eX]

[DOI]

Amitabh Trehan

CoRR, 2012

Towards robust and efficient computation in dynamic peer-to-peer networks.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, 2012

Agreement in Directed Dynamic Networks.

[BibT_eX]

[DOI]

Proceedings of the Structural Information and Communication Complexity, 2012

2011

The Asynchronous Bounded-Cycle model.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2011

Easy impossibility proofs for k-set agreement in message passing systems.

[BibT_eX]

[DOI]

Proceedings of the 30th Annual ACM Symposium on Principles of Distributed Computing, 2011

Solving k-Set Agreement with Stable Skeleton Graphs.

[BibT_eX]

[DOI]

Proceedings of the 25th IEEE International Symposium on Parallel and Distributed Processing, 2011

Optimal regional consecutive leader election in mobile ad-hoc networks.

[BibT_eX]

[DOI]

Hyun Chul Chung

Jennifer L. Welch

Proceedings of the FOMC'11, 2011

2010

Regional consecutive leader election in mobile ad-hoc networks.

[BibT_eX]

[DOI]

Hyun Chul Chung

Jennifer L. Welch

Proceedings of the DIALM-POMC Joint Workshop on Foundations of Mobile Computing, 2010

Brief Announcement: Regional Consecutive Leader Election in Mobile Ad-Hoc Networks.

[BibT_eX]

[DOI]

Hyun Chul Chung

Jennifer L. Welch

Proceedings of the Algorithms for Sensor Systems, 2010

2009

Brief Announcement: Weak Synchrony Models and Failure Detectors for Message Passing (k-)Set Agreement.

[BibT_eX]

[DOI]

Proceedings of the Distributed Computing, 23rd International Symposium, 2009

Weak Synchrony Models and Failure Detectors for Message Passing (k-)Set Agreement.

[BibT_eX]

[DOI]