Back to search

University of British Columbia

Distributed skip list in fine-grain message passing interface : implementation and analysis of a dictionary data structure that supports range queries

Abstract

dc:description

With scalability in mind, we have implemented a pure message-passing distributed data structure ideal for range queries. The structure is a distributed skip list that takes full advantage of Fine-Grain MPI to execute on a variety of scales ranging from a single multicore to multiple machines across clusters. The skip list data structure provides parallel implementation of range queries. Our implementation architecture is based on several services layered on top of each other that simplifies the effort required in building distributed code. Unlike concurrent data structures the distributed skip list operations are deterministic and atomic. The layered service architecture of our implementation exposes several control parameters that make it easy to distribute load, have operation flow control, vary granularity at different layers and tune performance to the underlying machine and network. Range-queries are implemented in a way that parallelizes the operation and takes advantage of the recursive properties of the skip list structure. We investigate a shortcut mechanism that alleviates the bottleneck at the head and introduces semantic trade offs between performance and consistency. We report on the performance of the skip list on a medium size cluster of two hundred cores with twenty thousand processes.

Degree

thesis:*
Name thesis:degree_name
Master of Science - MSc
Level thesis:degree_level
master's
Discipline thesis:degree_discipline
Computer Science
Grantor dc:publisher
University of British Columbia
Year dc:date
2014

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Alam, Sarwar

Rights

dc:rights
Statement dc:rights
  • Attribution-NonCommercial-NoDerivs 2.5 Canada
Language dc:language
eng

Identifiers

dc:identifier.*
Handle dc:identifier
http://hdl.handle.net/2429/46286

Chain of custody

source
Harvested from
University of British Columbia
Base URL
circle.library.ubc.ca/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Alam, Sarwar. Distributed skip list in fine-grain message passing interface : implementation and analysis of a dictionary data structure that supports range queries. master's thesis, University of British Columbia, 2014. http://hdl.handle.net/2429/46286