2026-07-20T14:47:53Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8020 2024-03-06T10:41:44Z ddc:004 open_access

Brief Announcement: Towards Reduced Instruction Sets for Synchronization Gelashvili, Rati Keidar, Idit Spiegelman, Alexander Wattenhofer, Roger Consensus hierarchy universal construction synchronization instruction. Contrary to common belief, a recent work by Ellen, Gelashvili, Shavit, and Zhu has shown that computability does not require multicore architectures to support "strong" synchronization instructions like compare-and-swap, as opposed to combinations of "weaker" instructions like decrement and multiply. However, this is the status quo, and in turn, most efficient concurrent data-structures heavily rely on compare-and-swap (e.g. for swinging pointers). We show that this need not be the case, by designing and implementing a concurrent linearizable Log data-structure (also known as a History object), supporting two operations: append(item), which appends the item to the log, and get-log(), which returns the appended items so far, in order. Readers are wait-free and writers are lock-free, hence this data-structure can be used in a lock-free universal construction to implement any concurrent object with a given sequential specification. Our implementation uses atomic read, xor, decrement, and fetch-and-increment instructions supported on X86 architectures, and provides similar performance to a compare-and-swap-based solution on today's hardware. This raises a fundamental question about minimal set of synchronization instructions that the architectures have to support. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Rati Gelashvili and Idit Keidar and Alexander Spiegelman and Roger Wattenhofer 2017 Is Part Of LIPIcs, Volume 91, 31st International Symposium on Distributed Computing (DISC 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.DISC.2017.53 urn:nbn:de:0030-drops-80201 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2017.53 eng https://creativecommons.org/licenses/by/3.0/legalcode