vector is defined as an infinite random word over a fixed alphabet, each list in the skip graph is identified by a finite word w from the same alphabet, if that word is a prefix of then node x is a member of the list. Operations Skip graphs support the basic operations of search, insert and delete. Skip graphs will also support the more complex range search operation. Search The search algorithm for skip graphs is almost identical to the search algorithm for skip lists but it is modified to run in a distributed system. Searches start at the top level and traverse through the structure. At each level, the search traverses the list until the next node contains a greater key. When a greater key is found, the search drops to the next level, continuing until the key is found or it is determined that the key is not contained in the set of nodes. If the key is not contained in the set of nodes the largest value less than the search key is returned. Each node in a list has the following fields: The node's value. An array containing pointers to the right and left neighbor in the node's doubly linked at level i. search(searchOp, startNode, searchKey, level) if (v.key = searchKey) then send(foundOp, v) to startNode if (v.key < searchKey) then while level ≥ 0 if (v.neighbor[R][level].key ≤ searchKey) then send(searchOp, startNode, searchKey, level) to v.neighbor[R][level] break else level = level - 1 else while level ≥ 0 if ((v.neighbor[L][level]).key ≥ searchKey) then send(searchOp, startNode, searchKey, level) to v.neighbor[L][level] break else level = level - 1 if (level < 0) then send(notFoundOp, v) to startNode Analysis performed by William Pugh shows that on average, a skip list and by extension a skip graph contains levels for a fixed value of . Given that at most nodes are searched on average per level, the total expected number of messages sent is and the expected time for the search is . Therefore, for a fixed value of , the search operation is expected to take time using messages. Insert Insertion is done in two phases and requires that a new node knows some introducing node ; the introducing node may be any other node currently in the skip graph. In the first phase the new node uses the introducing node to search for its own key; this search