Comment by mritun

Non-determinism doesn’t mean chaos.

Record the seed for all RNGs used (if you’re using more than one for your SkipList implementation) and then your Skip lists are no more harder to debug than a linked-list.