Résumé | We study 3 objects in shared-memory model: conflict detector, adopt-commit and value splitter. We design for each of these objects an implementation that is wait-free, anonymous, input-oblivious and only uses two register primitive operations: read and write. Each of these implementations requires $O(sqrt(n))$ atomic registers where $n$ is the number of processes. We conclude, by establishing a lower bound for each of these implementations matching the upper bounds derived from the proposed implementations.
Joint work with Claire Capdevielle and Alessia Milani |