uu.seUppsala University Publications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
A Skiplist-based Concurrent Priority Queue with Minimal Memory Contention
Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
2013 (English)In: OPODIS 2013: 17th International Conference On Principles Of DIstributed Systems / [ed] Roberto Baldoni, Nicolas Nisse, Maarten van Steen, Berlin: Springer Berlin/Heidelberg, 2013, 206-220 p.Conference paper, Published paper (Refereed)
Abstract [en]

Priority queues are fundamental to many multiprocessor  applications. Several priority queue algorithms based on skiplists  have been proposed, as skiplists allow concurrent accesses to  different parts of the data structure in a simple way. However, for  priority queues on multiprocessors, an inherent bottleneck is the  operation that deletes the minimal element. We present a  linearizable, lock-free, concurrent priority queue algorithm, based  on skiplists, which minimizes the contention for shared memory that  is caused by the DeleteMin operation. The main idea is to  minimize the number of global updates to shared memory that are  performed in one DeleteMin. In comparison with other  skiplist-based priority queue algorithms, our algorithm achieves a  30 - 80% improvement.

Place, publisher, year, edition, pages
Berlin: Springer Berlin/Heidelberg, 2013. 206-220 p.
Series
Lecture Notes in Computer Science, ISSN 0302-9743 ; 8304
Keyword [en]
Concurrent Data Structures, Priority Queue, Lock-free, Non- blocking, Skiplist
National Category
Computer Systems
Research subject
Computer Science
Identifiers
URN: urn:nbn:se:uu:diva-213426DOI: 10.1007/978-3-319-03850-6_15OAI: oai:DiVA.org:uu-213426DiVA: diva2:682052
Conference
OPODIS 2013: 17th International Conference On Principles Of DIstributed Systems, Nice, France,December 16-18th, 2013
Projects
CoDeR-MPUPMARC
Available from: 2013-12-21 Created: 2013-12-21 Last updated: 2014-02-06

Open Access in DiVA

No full text

Other links

Publisher's full texthttp://link.springer.com/chapter/10.1007/978-3-319-03850-6_15

Authority records BETA

Lindén, JonatanJonsson, Bengt

Search in DiVA

By author/editor
Lindén, JonatanJonsson, Bengt
By organisation
Computer Systems
Computer Systems

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 521 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf