currently the only way to remove and to repair a skip graph is to build a new skip graph with surviving nodes. Random failure Skip graphs are highly resistant to random failures. By maintaining information on the state of neighbors and using redundant links to avoid failed neighbors, normal operations can continue even with a large number of node failures. While the number of failed nodes is less than the skip graph can continue to function normally. Simulations performed by James Aspnes show that a skip graph with 131072 nodes was able tolerate up to 60% of its nodes failing before surviving nodes were isolated. While other distributed data structures may be able to achieve higher levels of resiliency they tend to be much more complex. Adversarial failure Adversarial failure is difficult to simulate in a large network as it becomes difficult to find worst case failure patterns. Theoretical analysis shows that the resilience depends based on the vertex expansion ratio of the graph, defined as follows. For a set of nodes A in the graph G, the expansion factor is the number of nodes not in A but adjacent to a node in A divided by the number of nodes in A. If skip graphs have a sufficiently large expansion ratio of then at most nodes may be separated, even if up to f failures are specifically targeted. References Graph data structures