3
$\begingroup$

In the context of multi-processor/multi-threaded systems, there are plenty of well-studied concurrent data structures, including stacks, queues, linked lists, etc. Here is an excellent survey on concurrent data structures by Mark Moir and Nir Shavit.

Even though they use a "shared memory" model similar to the one used by concurrent data structures, I can only find information on a few distributed data structures: those data structures designed specifically for distributed systems. Such data structures are typically characterized by replication and certain consistency models. The examples I have found include

My questions are

  1. What are the big challenges of designing distributed data structures (even harder than those of concurrent data structures)?
  2. Did I miss other distributed data structures in the literature?
$\endgroup$
3
$\begingroup$

What are the big challenges of designing distributed data structures (even harder than those of concurrent data structures)?

Some important challenges that practically all distributed data structures face, are handling dynamic changes, implementing a scalable design, and being fault-tolerant.

This includes finding answers to questions such as:

  • How can we maintain/repair the properties of the data structure in the presence of churn? That is, new nodes join and old nodes leave the network over time.
  • Can we design the data structure such that it is robust against faults?
  • How can we deal with the congestion on the communication links caused by many parallel requests?
  • Do the connections required per node and the necessary length of messages scale (at most) logarithmically with the system size?
  • Is it possible to design a system that is "spam resistant" in the sense that it can withstand attacks by adversarial nodes?

There are also locality issues since, in a distributed system, each node runs its own instance of a distributed algorithm and has only a local view of the network due to being directly connected to only a small number of other nodes. (Typically you would want a node degree of $O(\log n)$ to make the system scalable.) These issues come into play when maintaining global state such as counting the number of data items, finding the maximum, etc.

Did I miss other distributed data structures in the literature?

DHTs: To give you some pointers, you might want to look at distributed hash tables (DHT) such as Chord, CAN, Tapestry, and Pastry.

Skip Graphs: Since you mentioned skip lists, you might be interested in skip graphs, which is a data structure providing range-queries and $O(\log n)$-time operations for lookups, inserts, etc. The advantage of a skip graph (vs a skip list) is that a skip graph contains an expander as a subgraph with high probability. This implies that routing can be done efficiently (i.e. link congestion is low) and that the skip graph remains connected even if a lot of nodes fail.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.