Contention resolution. Given n processes P1,...,Pn, each competing for access to a shared database. If two or more processes access the database simultaneously, all processes are locked out. Devise protocol to ensure all processes get through on a regular basis.
有一个变量，
S（i,t) 表示i这个进程在t访问了这个资源。
Pr[S(i, t)] = $p(1-p)^{n-1}$
求导
$$ \text { Setting } p=1 / n \text {, we have } \operatorname{Pr}[S(i, t)]=1 / n(1-1 / n)^{n-1} \text {. } $$
随机算法一般跑很多遍
说明一个进程跑了很多次后它成功的概率就非常高了。
所有的进程都成功是独立的？？？？？
随机算法本质：多跑几遍，概率下降
坍缩的过程中最小割的值不变？？？？？
缩nlogn次， 最后取最小的。
算法本质：随机的遍历
优化算法： 因为越到后面越有可能收缩小最小割，所以每次只收缩到n/√2
分治算法（可能考！）