Revisionist Simulations: A New Approach to Proving Space Lower Bounds

Faith Ellen, Rati Gelashvili, Leqi Zhu

Determining the space complexity of $x$-obstruction-free $k$-set agreement for $x\le k$ is an open problem. In $x$-obstruction-free protocols, processes are required to return in…