Constructing Distributed Doubly Linked Lists without Distributed Locking
Kota Abe, Mikio Yoshida: Constructing Distributed Doubly Linked Lists without Distributed Locking, In Proceeding of the IEEE International Conference on Peer-to-Peer Computing 2015 (P2P 2015) (Sep. 2015).
Abstract
A distributed doubly linked list (or bidirectional ring) is a fundamental distributed data structure commonly used in structured peer-to-peer networks. This paper presents DDLL, a novel decentralized algorithm for constructing distributed doubly linked lists. In the absence of failure, DDLL maintains consistency with regard to lookups of nodes, even while multiple nodes are simultaneously being inserted or deleted. Unlike existing algorithms, DDLL adopts a novel strategy based on conflict detection and sequence numbers. A formal description and correctness proofs are given. Simulation results show that DDLL outperforms conventional algorithms in terms of both time and number of messages.
Paper
- Accepted version:
- Published version is available on IEEE Xplore
Presentation
Photo
