2026-07-25T06:17:48Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:14818 2024-03-06T10:54:55Z ddc:004 open_access

Fully Read/Write Fence-Free Work-Stealing with Multiplicity Castañeda, Armando Piña, Miguel Correctness condition Linearizability Nonblocking Relaxed data type Set-linearizability Wait-freedom Work-stealing It is known that any algorithm for work-stealing in the standard asynchronous shared memory model must use expensive Read-After-Write synchronization patterns or atomic Read-Modify-Write instructions. There have been proposed algorithms for relaxations in the standard model and algorithms in restricted models that avoid the impossibility result, but only in some operations. This paper considers work-stealing with multiplicity, a relaxation in which every task is taken by at least one operation, with the requirement that any process can extract a task at most once. Two versions of the relaxation are considered and two fully Read/Write algorithms are presented in the standard asynchronous shared memory model, both devoid of Read-After-Write synchronization patterns in all its operations, the second algorithm additionally being fully fence-free, namely, no specific ordering among the algorithm’s instructions is required, beyond what is implied by data dependence. To our knowledge, these are the first algorithms for work-stealing possessing all these properties. Our algorithms are also wait-free solutions of relaxed versions of single-enqueue multi-dequeuer queues. The algorithms are obtained by reducing work-stealing with multiplicity and weak multiplicity to MaxRegister and RangeMaxRegister, a relaxation of MaxRegister which might be of independent interest. An experimental evaluation shows that our fully fence-free algorithm exhibits better performance than Cilk THE, Chase-Lev and Idempotent Work-Stealing algorithms. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Armando Castañeda and Miguel Piña 2021 Is Part Of LIPIcs, Volume 209, 35th International Symposium on Distributed Computing (DISC 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.DISC.2021.16 urn:nbn:de:0030-drops-148181 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2021.16 eng https://creativecommons.org/licenses/by/4.0/legalcode