Choose a key at random, with probability proportional to its weight. Think about what happens if you pick an edge whose endpoints have already been contracted. Suppose we instead use some other constant value for p . Discuss the relation between the choice of p and the performance of the skip list in practice. The Aethernet corporation has developed an exciting new protocol to let a collection of m machines communicate on a shared wire.
Time is divided into fixed slots.
In a slot, any machine that wants to send information to another can broadcast it onto the wire. If more than one broadcast is attempted, none are successful. However, in each time slot, the set of machines might be different. For a competitive advantage, Aethernet believes they can cut costs by using fewer random bits to make broadcast decisions. And assume again that n is known.