George Giakkoupis

Volker Turau

Inf. Process. Lett., 2025

2024

Naively Sorting Evolving Data is Optimal and Robust.

[BibT_eX]

[DOI]

Marcos Kiwi

Dimitrios Los

CoRR, 2024

Self-Stabilizing MIS Computation in the Beeping Model.

[BibT_eX]

[DOI]

Volker Turau

Proceedings of the 38th International Symposium on Distributed Computing, 2024

Brief Announcement: Self-Stabilizing MIS Computation in the Beeping Model.

[BibT_eX]

[DOI]

Volker Turau

Proceedings of the 43rd ACM Symposium on Principles of Distributed Computing, 2024

Faster Randomized Repeated Choice and DCAS.

[BibT_eX]

[DOI]

Dante Bencivenga

Proceedings of the 43rd ACM Symposium on Principles of Distributed Computing, 2024

2023

Distributed Self-Stabilizing MIS with Few States and Weak Communication.

[BibT_eX]

[DOI]

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

Word-Size RMR Tradeoffs for Recoverable Mutual Exclusion.

[BibT_eX]

[DOI]

David Yu Cheng Chan

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

2022

Expanders via local edge flips in quasilinear time.

[BibT_eX]

[DOI]

Proceedings of the STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20, 2022

2021

Efficient randomized DCAS.

[BibT_eX]

[DOI]

Mehrdad Jafari Giv

Proceedings of the STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021

Self-Stabilizing Clock Synchronization with 1-bit Messages.

[BibT_eX]

[DOI]

Paul Bastide

Hayk Saribekyan

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

Search via Parallel Lévy Walks on Z2.

[BibT_eX]

[DOI]

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

Cluster-and-Conquer: When Randomness Meets Graph Locality.

[BibT_eX]

[DOI]

Proceedings of the 37th IEEE International Conference on Data Engineering, 2021

2020

On the Search Efficiency of Parallel Lévy Walks on Z2.

[BibT_eX]

[DOI]

CoRR, 2020

Spread of Information and Diseases via Random Walks in Sparse Graphs.

[BibT_eX]

[DOI]

Hayk Saribekyan

Thomas Sauerwald

Proceedings of the 34th International Symposium on Distributed Computing, 2020

Optimal time and space leader election in population protocols.

[BibT_eX]

[DOI]

Peter Kling

Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, 2020

Brief Announcement: Optimal Time and Space Leader Election in Population Protocols.

[BibT_eX]

[DOI]

Peter Kling

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

2019

Efficient randomized test-and-set implementations.

[BibT_eX]

[DOI]

Distributed Comput., 2019

How to Spread a Rumor: Call Your Neighbors or Take a Walk?

[BibT_eX]

[DOI]

Frederik Mallmann-Trenn

Hayk Saribekyan

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

2018

Rumor Spreading and Conductance.

[BibT_eX]

[DOI]

J. ACM, 2018

An Improved Bound for Random Binary Search Trees with Concurrent Insertions.

[BibT_eX]

[DOI]

Proceedings of the 35th Symposium on Theoretical Aspects of Computer Science, 2018

Tight Bounds for Coalescing-Branching Random Walks on Regular Graphs.

[BibT_eX]

[DOI]

Peter Kling

Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

2017

Tight Bounds on Vertex Connectivity Under Sampling.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2017

Randomized Abortable Mutual Exclusion with Constant Amortized RMR Complexity on the CC Model.

[BibT_eX]

[DOI]

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

2016

Deterministic and Fast Randomized Test-and-Set in Optimal Space.

[BibT_eX]

[DOI]

CoRR, 2016

Amplifiers and Suppressors of Selection for the Moran Process on Undirected Graphs.

[BibT_eX]

[DOI]

CoRR, 2016

How Asynchrony Affects Rumor Spreading Time.

[BibT_eX]

[DOI]

Yasamin Nazari

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

Lightweight Privacy-Preserving Averaging for the Internet of Things.

[BibT_eX]

[DOI]

Proceedings of the 3rd Workshop on Middleware for Context-Aware Applications in the IoT, 2016

Bounds on the Voter Model in Dynamic Networks.

[BibT_eX]

[DOI]

Anne-Marie Kermarrec

Frederik Mallmann-Trenn

Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming, 2016

Efficient Plurality Consensus, Or: the Benefits of Cleaning up from Time to Time.

[BibT_eX]

[DOI]

Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming, 2016

2015

Privacy-Conscious Information Diffusion in Social Networks.

[BibT_eX]

[DOI]

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

Test-and-Set in Optimal Space.

[BibT_eX]

[DOI]

Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, 2015

Tight Bounds on Vertex Connectivity Under Vertex Sampling.

[BibT_eX]

[DOI]

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

2014

Greedy routing in small-world networks with power-law degrees.

[BibT_eX]

[DOI]

Distributed Comput., 2014

Tight Bounds for Rumor Spreading with Vertex Expansion.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014

Randomized Rumor Spreading in Dynamic Graphs.

[BibT_eX]

[DOI]

Thomas Sauerwald

Alexandre Stauffer

Proceedings of the Automata, Languages, and Programming - 41st International Colloquium, 2014

Randomized Mutual Exclusion with Constant Amortized RMR Complexity on the DSM.

[BibT_eX]

[DOI]

Proceedings of the 55th IEEE Annual Symposium on Foundations of Computer Science, 2014

2013

Gossip Protocols for Renaming and Sorting.

[BibT_eX]

[DOI]

Anne-Marie Kermarrec

Proceedings of the Distributed Computing - 27th International Symposium, 2013

An O(sqrt n) Space Bound for Obstruction-Free Leader Election.

[BibT_eX]

[DOI]

Proceedings of the Distributed Computing - 27th International Symposium, 2013

Randomized loose renaming in O(log log n) time.

[BibT_eX]

[DOI]

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

2012

A tight RMR lower bound for randomized mutual exclusion.

[BibT_eX]

[DOI]

Proceedings of the 44th Symposium on Theory of Computing Conference, 2012

Low Randomness Rumor Spreading via Hashing.

[BibT_eX]

[DOI]

Proceedings of the 29th International Symposium on Theoretical Aspects of Computer Science, 2012

Rumor spreading and vertex expansion.

[BibT_eX]

[DOI]

Thomas Sauerwald

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

Brief announcement: a tight RMR lower bound for randomized mutual exclusion.

[BibT_eX]

[DOI]

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

On the time and space complexity of randomized test-and-set.

[BibT_eX]

[DOI]

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

2011

Optimal path search in small worlds: dimension matters.

[BibT_eX]

[DOI]

Nicolas Schabanel

Proceedings of the 43rd ACM Symposium on Theory of Computing, 2011

Tight bounds for rumor spreading in graphs of a given conductance.

[BibT_eX]

[DOI]

Proceedings of the 28th International Symposium on Theoretical Aspects of Computer Science, 2011

On the Randomness Requirements of Rumor Spreading.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, 2011

2010

On the searchability of small-world networks with arbitrary underlying structure.

[BibT_eX]

[DOI]

Proceedings of the 42nd ACM Symposium on Theory of Computing, 2010

On the bit communication complexity of randomized rumor spreading.

[BibT_eX]

[DOI]

Proceedings of the SPAA 2010: Proceedings of the 22nd Annual ACM Symposium on Parallelism in Algorithms and Architectures, 2010

2009

On Load Balancing and Routing in Peer-to-peer Systems.

[BibT_eX]

[DOI]

PhD thesis, 2009

The effect of power-law degrees on the navigability of small worlds: [extended abstract].

[BibT_eX]

[DOI]

Proceedings of the 28th Annual ACM Symposium on Principles of Distributed Computing, 2009

2007

On the complexity of greedy routing in ring-based peer-to-peer networks.

[BibT_eX]

[DOI]

Vassos Hadzilacos

Proceedings of the Twenty-Sixth Annual ACM Symposium on Principles of Distributed Computing, 2007

2005

A scheme for load balancing in heterogenous distributed hash tables.

[BibT_eX]

[DOI]