<blockquote>
  <p>What are the big challenges of designing distributed data structures (even harder than those of concurrent data structures)?</p>
</blockquote>

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

<p>This includes finding answers to questions such as:</p>

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

<p>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.</p>

<blockquote>
  <p>Did I miss other distributed data structures in the literature?</p>
</blockquote>

<p><strong>DHTs</strong>: To give you some pointers, you might want to look at <a href="http://en.wikipedia.org/wiki/Distributed_hash_table" rel="nofollow">distributed hash tables</a> (DHT) such as <a href="http://en.wikipedia.org/wiki/Chord_%28peer-to-peer%29" rel="nofollow">Chord</a>, <a href="http://en.wikipedia.org/wiki/Content_addressable_network" rel="nofollow">CAN</a>, <a href="http://en.wikipedia.org/wiki/Tapestry_%28DHT%29" rel="nofollow">Tapestry</a>, and <a href="http://en.wikipedia.org/wiki/Pastry_%28DHT%29" rel="nofollow">Pastry</a>. </p>

<p><strong>Skip Graphs</strong>: Since you mentioned skip lists, you might be interested in <a href="http://en.wikipedia.org/wiki/Skip_graph" rel="nofollow">skip graphs</a>, 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.</p>

CC BY-SA 3.0
2014-07-09T14:09:04.670Z
2014-07-09T14:09:04.670Z
Peter
<p>In the context of multi-processor/multi-threaded systems, there are plenty of well-studied <em>concurrent data structures</em>, including stacks, queues, linked lists, etc. <a href="http://www.cs.tau.ac.il/~shanir/concurrent-data-structures.pdf" rel="nofollow">Here</a> is an excellent survey on concurrent data structures by Mark Moir and Nir Shavit. </p>

<p>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 <em>distributed data structures</em>: those data structures designed specifically for distributed systems. Such data structures are typically characterized by replication and certain <a href="https://en.wikipedia.org/wiki/Consistency_model" rel="nofollow">consistency models</a>. The examples I <em>have</em> found include</p>

<ul>
<li><a href="http://arxiv.org/pdf/1210.3368.pdf" rel="nofollow">An Optimized Conflict-free Replicated Set</a> (arXiv, 2012)</li>
<li><a href="http://dl.acm.org/citation.cfm?id=384050" rel="nofollow">Randomized Shared Queues</a> (PODC, 2001)</li>
</ul>

<p>My questions are</p>

<ol>
<li>What are the big challenges of designing distributed data structures (even harder than those of concurrent data structures)?</li>
<li>Did I miss other distributed data structures in the literature?</li>
</ol>

<ds.data-structures><dc.distributed-comp><concurrency>
Concurrent data structures vs. Distributed data structures
hengxin
# Concurrent data structures vs. Distributed data structures

(Asked by: username_0 on 2014-07-09)

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](http://www.cs.tau.ac.il/~shanir/concurrent-data-structures.pdf) 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](https://en.wikipedia.org/wiki/Consistency_model). The examples I *have* found include

* [An Optimized Conflict-free Replicated Set](http://arxiv.org/pdf/1210.3368.pdf) (arXiv, 2012)
* [Randomized Shared Queues](http://dl.acm.org/citation.cfm?id=384050) (PODC, 2001)

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?

**Tags:** ds.data-structures, dc.distributed-comp, concurrency

---

## 1 answers

### Answer by username_1 on 2014-07-09. Score: 3 | Accepted answer

> 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](http://en.wikipedia.org/wiki/Distributed_hash_table) (DHT) such as [Chord](http://en.wikipedia.org/wiki/Chord_%28peer-to-peer%29), [CAN](http://en.wikipedia.org/wiki/Content_addressable_network), [Tapestry](http://en.wikipedia.org/wiki/Tapestry_%28DHT%29), and [Pastry](http://en.wikipedia.org/wiki/Pastry_%28DHT%29).

**Skip Graphs**: Since you mentioned skip lists, you might be interested in [skip graphs](http://en.wikipedia.org/wiki/Skip_graph), 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.


---

