Show simple item record

dc.contributor.author
Gelashvili, Rati
dc.contributor.author
Keidar, Idit
dc.contributor.author
Spiegelman, Alexander
dc.contributor.author
Wattenhofer, Roger
dc.contributor.editor
Richa, Andrea
dc.date.accessioned
2017-12-07T17:08:03Z
dc.date.available
2017-11-08T04:34:58Z
dc.date.available
2017-12-07T17:08:03Z
dc.date.issued
2017
dc.identifier.isbn
978-3-95977-053-8
en_US
dc.identifier.issn
1868-8969
dc.identifier.other
10.4230/LIPIcs.DISC.2017.53
en_US
dc.identifier.uri
http://hdl.handle.net/20.500.11850/205788
dc.identifier.doi
10.3929/ethz-b-000205788
dc.description.abstract
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.
en_US
dc.format
application/pdf
dc.language.iso
en
en_US
dc.publisher
Schloss Dagstuhl, Leibniz-Zentrum für Informatik
en_US
dc.rights.uri
http://creativecommons.org/licenses/by/3.0/
dc.subject
Consensus hierarchy
en_US
dc.subject
universal construction
en_US
dc.subject
synchronization instruction
en_US
dc.title
Brief Announcement: Towards Reduced Instruction Sets for Synchronization
en_US
dc.type
Conference Paper
dc.rights.license
Creative Commons Attribution 3.0 Unported
ethz.book.title
31st International Symposium on Distributed Computing (DISC 2017)
en_US
ethz.journal.title
Leibniz International Proceedings in Informatics
ethz.journal.volume
91
en_US
ethz.journal.abbreviated
Leibniz int. proc. inform.
ethz.pages.start
53
en_US
ethz.size
4 p.
en_US
ethz.version.deposit
publishedVersion
en_US
ethz.event
31st International Symposium on Distributed Computing (DISC 2017)
en_US
ethz.event.location
Vienna, Austria
en_US
ethz.event.date
October 16-20, 2017
en_US
ethz.identifier.scopus
ethz.publication.place
Dagstuhl
en_US
ethz.publication.status
published
en_US
ethz.date.deposited
2017-11-08T04:35:02Z
ethz.source
SCOPUS
ethz.eth
yes
en_US
ethz.availability
Open access
en_US
ethz.rosetta.installDate
2017-12-07T17:08:08Z
ethz.rosetta.lastUpdated
2020-02-15T10:18:41Z
ethz.rosetta.exportRequired
true
ethz.rosetta.versionExported
true
ethz.COinS
ctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.atitle=Brief%20Announcement:%20Towards%20Reduced%20Instruction%20Sets%20for%20Synchronization&rft.jtitle=Leibniz%20International%20Proceedings%20in%20Informatics&rft.date=2017&rft.volume=91&rft.spage=53&rft.issn=1868-8969&rft.au=Gelashvili,%20Rati&Keidar,%20Idit&Spiegelman,%20Alexander&Wattenhofer,%20Roger&rft.isbn=978-3-95977-053-8&rft.genre=proceeding&rft_id=info:doi/978-3-95977-053-8&rft.btitle=31st%20International%20Symposium%20on%20Distributed%20Computing%20(DISC%202017)
 Search via SFX

Files in this item

Thumbnail

Publication type

Show simple item record