ABSTRACT
This chapter presents different types of distributed data structures. It describes distributed architecture and the difficulties of implementation in that environment and discusses distributed hashing, lists, trees, and skiplists. A Distributed Data Structure (DDS) is a self-managing storage layer developed to run on a collection of workstations inter connected by an underlying network. A DDS automates replication, partitions data, and distributes data over servers that ensure high availability and automatic recovery. A distributed hash table is a class of a decentralized distributed system that provides a lookup service similar to a hash table: pairs are stored in a distributed hash table, and any participating node can efficiently retrieve the value associated with a given key. Rotations in a distributed environment are performed via message exchanges between servers. The search operation is identical to the search in a skiplist with only minor adaptations to run in a distributed system.
