Journal article icon

Journal article

Lock-free concurrent binomial heaps

Abstract:

We present a linearizable, lock-free concurrent binomial heap. In our experience, a binomial heap is considerably more complex than previously considered concurrent datatypes. The implementation presents a number of challenges. We need to deal with interference when a thread is traversing the heap, searching for the smallest key: our solution is to detect such interference, and restart the traversal. We must avoid interference between updating operations: we add labels to nodes to prevent int...

Expand abstract
Publication status:
Published
Peer review status:
Peer reviewed

Actions


Access Document


Files:
  • (Accepted manuscript, pdf, 440.0KB)
Publisher copy:
10.1016/j.jlamp.2018.08.001

Authors


More by this author
Institution:
University of Oxford
Division:
MPLS
Department:
Computer Science
Oxford college:
St Catherine's College
Role:
Author
Publisher:
Elsevier
Journal:
Journal of Logical and Algebraic Methods in Programming More from this journal
Volume:
101
Pages:
44-87
Publication date:
2018-08-24
Acceptance date:
2018-08-10
DOI:
ISSN:
2352-2208
Keywords:
Pubs id:
pubs:911512
UUID:
uuid:f7833406-bc72-4b20-90fc-e0f2e89fa0a4
Local pid:
pubs:911512
Source identifiers:
911512
Deposit date:
2018-08-31

Terms of use


Views and Downloads






If you are the owner of this record, you can report an update to it here: Report update to this record

TO TOP