Revisionist Simulations
Faith Ellen, Rati Gelashvili, Leqi Zhu · 2018
Determining the number of registers required for solving x-obstruction-free (or randomized wait-free) k-set agreement for x ≤ k is an open problem that highlights important gaps in our understanding of the space complexity of synchronization. In x-obstruction-free protocols, processes are required to return in executions where at most x processes take steps. The best known upper bound on the number of registers needed to solve this problem among n>k processes is n-k+x registers. No general lower bound better than 2 was known.