Protocol: Fix and test the specification of search for skip lists

The skip list specification was broken for the [Nearest] case. We fix the specification and gives a test which explains why it was broken.