Brief Announcement: Highly Dynamic and Fully Distributed Data Structures

We adopt the dynamic network with churn (DNC) model [4, 3]: a synchronous message-passing network of fixed size $n$, controlled by an oblivious adversary that may replace up to $𝒪(n/\log n)$ nodes per round after an initial $B=\beta \log n$-round bootstrap phase with no churn. Each node has a unique ID in $[0,poly(n)]$, stores one item, and can send/receive at most $\text{polylog}(n)$-bit messages over at most $\text{polylog}(n)$ links per round. New nodes are connected to distinct existing nodes to avoid congestion. The adversary specifies a sequence ${(V_t)}_{t\ge 0}$ with $|V_t|=n$ for all $t$; joins and leaves are arbitrary subject to the churn bound. Nodes may create/delete edges; a bidirectional link $(u,v)$ exists if both endpoints exchange invitation/acceptance messages, and is removed when either endpoint leaves or sends a delete message. For clarity, we focus here on the fixed-$n$, single-item case; in the full version, we generalize our algorithms to handle multiple items per node and a network size that may vary over time [2].

We aim to maintain an approximate distributed data structure storing all items in the network, resilient to high adversarial churn. Insertions and deletions complete in $O(\log n)$ rounds, and membership queries $q(x,r,s)$ (initiated at source $s$ in round $r$) must be answered within $Q=𝒪(\log n)$ rounds. A query returns “Yes” if $x$ is present for the entire interval $[r,r+Q]$, “No” if absent for the entire interval, and may return either answer otherwise. This relaxed consistency, or eventual correctness, allows scalability and liveness under churn.

We require a dynamic formulation of resource-competitiveness [6]: the total work (number of messages and edge addition/deletions) over any interval is within a $\text{polylog}(n)$ factor of the churn in that interval (allowing an $𝒪(\log n)$ lookback to capture delayed effects).

We fist show how to maintain an approximate distributed skip list, and then we extend our techniques to skip graphs and, in the full version, to general pointer-based distributed data structures.

Our dynamic distributed skip list data structure is architected using multiple “virtual networks” (see Figure 1). Each peer node can participate in more than one network and in some cases more than one location within the same network. We use the following network structures.

The Spartan Network $𝒮$

is a wrapped butterfly network that contains all the current nodes. This network can handle heavy churn of up to $𝒪(n/\log n)$ nodes joining and leaving in every round [5]. However, this network is not capable of handling search queries.

Live Network $ℒ$

is the skip list network on which all queries are executed. Some of the nodes in this network may have left. We require such nodes to be temporarily represented by their replacement nodes (from their respective neighbors in $𝒮$).

Buffer Network $ℬ$

is a skip list network on which we maintain all new nodes that joined recently.

Clean Network $𝒞$

is a skip list network that seeks to maintain an updated version of the data structure that includes the nodes in the system.

Moreover, in all skip lists, when a node exits the system, it is operated by a selected group of nodes. In the course of our algorithm description, if a node $u$ is required to perform some operation, but is no longer in the system, then its replacement node(s) will perform that operation on its behalf. Note further that some of the replacement nodes themselves may need to be replaced. Such replacement nodes will continue to represent $u$. The protocol assumes a short ($\mathrm{\Theta }(\log n)$ round) initial “bootstrap” phase, where there is no churn¹¹1Without a bootstrap phase, it is easy to show that the adversary can partition the network into large pieces, with no chance of forming even a connected graph. and it initializes the underlying network. More precisely, the bootstrap is divided in two sub-phases in which we (i) build the underlying churn resilient network in $𝒪(\log n)$ rounds and, (ii) we build the skip lists data structures $ℒ$ and $𝒞$ (initially $ℒ=𝒞$) in $𝒪(\log n)$ rounds; after this, the adversary is free to exercise its power to add or delete nodes up to the churn limit and the network will undergo a continuous maintenance process. The overall maintenance of the dynamic distributed data structure goes through cycles. Each cycle $c\ge 1$ in Algorithm 1 consists of four sequential phases. Without loss of generality, assume that initially $ℒ$ and $𝒞$ are the same. We use the notation ${ℒ}^{(c)}$ (resp. ${𝒮}^{(c)},{𝒞}^{(c)},{ℬ}^{(c)}$) to indicate the network $ℒ$ (resp. $𝒮,𝒞,ℬ$) during the cycle $c\in \mathbb{N}$, when it is clear from the context we omit the superscript to maintain a cleaner exposition.

Each phase of Algorithm 1 requires $𝒪(\log n)$ rounds w.h.p. In particular, the deletion and merge phases implement two novel parallel and fully distributed protocols to delete a batch of $\mathrm{\Theta }(n)$ and merge two skip lists of $\mathrm{\Theta }(n)$ elements in $𝒪(\log n)$ rounds w.h.p, respectively. This improves over prior $𝒪(k\log n)$-round bounds to perform these operation on a batch of $k$ elements in skip-lists. We believe that some ideas from our results could be used in the centralized batch parallel setting to quickly insert batches of new elements in skip lists-like data structures (see e.g.,[17]) and in the fully dynamic graph algorithms settings (see for example the survey [13]) to perform fast updates of fully dynamic data structures. Indeed, in principle (provided the right amount of parallelism), our deletion and merge algorithms could be implemented in a parallel (centralized) setting and used to speed-up all kinds of computations involving these specific data structures. Our major contribution can be summarized in the following theorem.

The above architecture and results extend to skip graphs and, to settings with multiple items per node and variable network size.

On a broader picture, the above results can be unified under a single general framework for maintaining pointer-based data structures under adversarial churn. Given a data structure $𝒟$, we can “abstract away” the ideas in Algorithm 1 and obtain the following abstract maintenance cycle for a generic data structure $𝒟$:

1. 1.

   Delete Phase: Identify and remove corrupted, outdated, or disconnected regions of $𝒟$. Deletion ensures that inconsistencies caused by churn do not propagate through the structure.

2. 2.

   Creation Phase: Organize the set of newly arrived nodes into a provisional structure $ℬ$ (the buffer data structure). The goal is to prepare these nodes for integration, typically by arranging them into a sorted or partially structured form.

3. 3.

   Merge Phase: Integrate the buffer network $ℬ$ into the main structure $𝒟$ using a distributed merge protocol. This phase reconstructs the structure while respecting existing invariants.

4. 4.

   Update Phase: Perform any necessary local corrections, including pointer rebalancing, level adjustments, or redundancy restoration, to finalize the integration.

Provided that we have $𝒪(T)$-round distributed algorithms for each phase of the above abstract maintenance cycle, we can maintain $𝒟$ against an adversarial churn rate of $𝒪(n/T)$ per round.

Our abstract maintenance cycle allows to define classes of churn-resilient data structures in the DNC model, where each class is characterized by the churn rate per round (thus the maintenance cycle runtime) that the data structure can tolerate while still supporting efficient update and query operations. Formally, let $t$ be the maintenance cycle run time function. We say that a distributed data structure $𝒟$ is $t$-maintainable if it can be successfully maintained by a $t$-round maintenance cycle.

In this brief announcment, we showed that Skip-Lists and Skip-Graphs are both $𝒪(\log n)$-maintainable and that are robust against and oblivious adversarial churn rate of $𝒪(n/\log n)$ per round. We conjecture that our bounds are tight, in the sense that $\log n$ is also a lower bound for the maintenance cycles for these data structures. That is because, in order to beat the $\mathrm{\Omega }(\log n)$ barrier we would need to solve distributed sorting faster than in $\log n$ rounds while maintaining dynamic resource competitiveness.

This classification also raises a number of intriguing open problems. For example, it remains unclear whether there exist distributed data structures in the DNC model that are $\log \log n$-maintainable, and more generally, how to characterize the precise boundaries between maintainability classes. A key challenge is to establish lower bounds on the maintenance cycle time for fundamental distributed data structures. Do entirely new data structures need to be designed to exploit faster maintenance cycles? We believe that our formulation of maintainability classes in the DNC model opens up a rich landscape for further exploration.