The Complexity of Asynchronous Algorithms with Bounded-Size Objects

Par

Sean Ovens

Université de Waterloo

Mercredi 12 mars 2025, 10:30-11:30 EST, Salle 6214

Pavillon André-Aisenstadt, Université de Montréal, 2920 Chemin de la Tour

Abstract: In a shared memory system, a set of processes communicate by applying operations to a set of shared objects. When designing shared memory algorithms, it is often convenient to assume that the shared objects are infinitely large. However, this is not a practical assumption, as real systems are constrained to use shared objects with constant domain sizes. My work studies the capabilities and limitations of shared memory systems with bounded-size objects. Specifically, I seek to prove new complexity lower bounds in such systems.

In this talk, I will introduce a general technique for obtaining space complexity lower bounds in systems with bounded-size objects. In particular, I will apply this technique to the well-studied consensus problem. To solve consensus, processes begin with private input values and must agree on a common output value, which is equal to one of the inputs. It was previously known that solving obstruction-free consensus using swap objects among n processes requires at least Ω(√n) objects. My work was the first in nearly thirty years to improve upon this lower bound, showing that Ω(n/b) swap objects with domain size b are needed. I will conclude my talk by highlighting a few longstanding open questions about the complexity of shared memory algorithms that could be easier to approach in a system with bounded-size shared objects.

Bio: Sean Ovens is a postdoctoral researcher at the University of Waterloo working with Trevor Brown. He earned his PhD in Summer 2023 from the University of Toronto, where he was supervised by Faith Ellen. His research interests include impossibility results and complexity lower bounds for distributed algorithms, concurrent data structures, and performance profilers and visualizations for multithreaded applications. Sean's work has been published in the Journal of the ACM, DISC, and PODC, where he received best paper awards in both 2022 and 2024.