Constructing distributed doubly linked lists without distributed locking

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.