is expected to fail and return the node with the largest key smaller than . In the second phase inserts itself in each level until it is the only element in a list at the top level. Insertion at each level is performed using standard doubly linked list operations; the left neighbor's next pointer is changed to point to the new node and the right neighbor's previous pointer is changed to point to the node. insert() search for = 0 while true insert into level L from Scan through level to find such which has membership vector matching membership vector of for first +1 characters if no exists exit else = = + 1 Similar to the search, the insert operation takes expected O(log n) messages and O(log n) time. With a fixed value of p; the search operation in phase 1 is expected to take O(log n) time and messages. In phase 2 at each level L ≥ 0, communicates with an average 1/p other nodes to locate ', this will require O(1/p) time and messages leading to O(1) time and messages for each step in phase 2. Delete Nodes may be deleted in parallel at each level in O(1) time and O(log n) messages. When a node wishes to leave the graph it must send messages to its immediate neighbors to rearrange their next and previous pointers. delete() for L = 1 to max level, in parallel delete u from each level. delete u from level 0 The skip graph contains an average of O(log n) levels; at each level u must send 2 messages to complete a delete operation on a doubly linked list. As operations on each level may be done in parallel the delete operation may be finished using O(1) time and expected O(log n) messages. Fault tolerance In skip graphs, fault tolerance describes the number of nodes which can be disconnected from the skip graph by failures of other nodes. Two failure models have been examined; random failures and adversarial failures. In the random failure model any node may fail independently from any other node with some probability. The adversarial model assumes node failures are planned such that the worst possible failure is achieved at each step, the entire skip graph structure is known and failures are chosen to maximize node disconnection. A drawback of skip graphs is that there is no repair mechanism;