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.
