Résumé | We study on uncontended complexity of anonymous algorithms, counting the number of distinct memory accesses in operations that encounter no contention. We assume that contention-free operations on a concurrent object perform “fast” reads and writes, and resort to more expensive synchronization primitives, such as CAS, only when contention is detected. We call such concurrent implementations interval-solo-fast and derive tight lower bounds on time and space complexity of anonymous interval-solo-fast consensus. |