×

A concurrent implementation of skip graphs. (English) Zbl 1268.05208

Liebling, Thomas M. (ed.) et al., LAGOS’09 – V Latin-American algorithms, graphs, and optimization symposium. Papers from the symposium, Gramado, Brazil, November 3–7, 2009. Amsterdam: Elsevier. Electronic Notes in Discrete Mathematics 35, 263-268 (2009).
Summary: In this extended abstract, we outline a concurrent implementation of a data structure called skip graphs. This data structure, proposed by Aspnes and Shah, has similar functionality to binary search trees, and has also special features that make it suitable for P2P distributed environments. In our implementation, we used non-blockirig locking primitives to synchronize the operations whenever necessary. The resulting implementation performed well in practice, according to our experiments.
For the entire collection see [Zbl 1239.05007].

MSC:

05C85 Graph algorithms (graph-theoretic aspects)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Aspnes, J.; Shah, G., Skip graphs, ACM Trans. on Algorithms, 3, 4, 37 (2007) · Zbl 1445.68061
[2] S. Heller, M. Herlihy, V. Luchangco. M. Moir, W. Scherer, and N. Shavit. A lazy concurrent list-based set algorithm. In Proc. of the. 9th Intl. Conf. On Princ. Of Distributed Systems; S. Heller, M. Herlihy, V. Luchangco. M. Moir, W. Scherer, and N. Shavit. A lazy concurrent list-based set algorithm. In Proc. of the. 9th Intl. Conf. On Princ. Of Distributed Systems
[3] Lamport, L., The mutual exclusion problem: Part I - the theory of interprocess communication, Journal of the ACM, 33, 2, 313-326 (1986) · Zbl 0627.68017
[4] Y. Lev, M. Herlihy, V. Luchangco, and N. Shavit. A provably correct scalable skiplist, In Proc. of the 10th Intl. Conf. On Princ. Of Distributed Systems; Y. Lev, M. Herlihy, V. Luchangco, and N. Shavit. A provably correct scalable skiplist, In Proc. of the 10th Intl. Conf. On Princ. Of Distributed Systems · Zbl 1201.68043
[5] H. Mendes. Estruturas de dados concorrentes: um estudo de caso em skip graphs. Master’s thesis, Universidade de São Paulo - USP, 2008. In Portuguese. Implementation at http://www.ime.usp.br/hmendes/skipgraphs.html; H. Mendes. Estruturas de dados concorrentes: um estudo de caso em skip graphs. Master’s thesis, Universidade de São Paulo - USP, 2008. In Portuguese. Implementation at http://www.ime.usp.br/hmendes/skipgraphs.html
[6] W. Pugh. Skip lists: A probabilistic alternative to balanced trees. In Workshop on Algorithms and Data Structures; W. Pugh. Skip lists: A probabilistic alternative to balanced trees. In Workshop on Algorithms and Data Structures · Zbl 0767.68023
[7] J. Valois. Lock-free linked lists using compare-and-swap. In Proc. of the 14th annual ACM Symp. on Princ. of Distributed Computing; J. Valois. Lock-free linked lists using compare-and-swap. In Proc. of the 14th annual ACM Symp. on Princ. of Distributed Computing · Zbl 1373.68200
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.