6 Consider the following process for matching n jobs to n processors. In each step, every...

Transcribed Image Text:

6 Consider the following process for matching n jobs to n processors. In each step, every job picks a processor at random. The jobs that have no contention on the processors they picked get executed, and all the other jobs back off and then try again. Jobs only take one round of time to execute, so in every round all the processors are available. Show that all the jobs finish executing w.h.p. after O(log log n) steps. Hint: Try to argue that if there are currently en unmatched jobs, then in the next round roughly en jobs remain unmatched. 6 Consider the following process for matching n jobs to n processors. In each step, every job picks a processor at random. The jobs that have no contention on the processors they picked get executed, and all the other jobs back off and then try again. Jobs only take one round of time to execute, so in every round all the processors are available. Show that all the jobs finish executing w.h.p. after O(log log n) steps. Hint: Try to argue that if there are currently en unmatched jobs, then in the next round roughly en jobs remain unmatched.