whether to promote only the even ones or only the odd ones. Instead of coin flips, there would only be of them. Unfortunately, this gives the adversarial user a 50/50 chance of being correct upon guessing that all of the even numbered nodes (among the ones at level 1 or higher) are higher than level one. This is despite the property that there is a very low probability of guessing that a particular node is at level N for some integer N. A skip list does not provide the same absolute worst-case performance guarantees as more traditional balanced tree data structures, because it is always possible (though with very low probability) that the coin-flips used to build the skip list will produce a badly balanced structure. However, they work well in practice, and the randomized balancing scheme has been argued to be easier to implement than the deterministic balancing schemes used in balanced binary search trees. Skip lists are also useful in parallel computing, where insertions can be done in different parts of the skip list in parallel without any global rebalancing of the data structure. Such parallelism can be especially advantageous for resource discovery in an ad-hoc wireless network because a randomized skip list can be made robust to the loss of any single node. Indexable skiplist As described above, a skip list is capable of fast insertion and removal of values from a sorted sequence, but it has only slow lookups of values at a given position in the sequence (i.e. return the 500th value); however, with a minor modification the speed of random access indexed lookups can be improved to . For every link, also store the width of the link. The width is defined as the number of bottom layer links being traversed by each of the higher layer "express lane" links. For example, here are the widths of the links in the example at the top of the page: 1 10 o---> o---------------------------------------------------------> o Top level 1 3 2 5 o---> o---------------> o---------> o---------------------------> o Level 3 1 2 1 2 3 2 o---> o---------> o---> o---------> o---------------> o---------> o Level 2 1 1 1 1 1 1 1 1 1 1 1 o---> o---> o---> o---> o---> o---> o---> o---> o---> o---> o---> o Bottom level Head 1st 2nd 3rd 4th 5th 6th 7th 8th 9th 10th NIL Node Node Node Node Node Node