论文部分内容阅读
本文研究了分布式随机Ｏｂｌｉｖｉｏｕｓ路由算法中随机性与时间代价的关系．证明了：对于ｎ个结点，最大结点度为ｄ的图Ｇ及其上的任意一个分布式随机路由算法，若该算法以概率Ｑ（＜在Ｔ步内完成，则它至少需使用个随机位．从而证明了Ｖａｌｉａｎｔ二阶段路由算法所使用的随机位数目是近似最优的．结合本文及文献［１０］中的结果，还反映了分布式算法与集中式算法之间的深刻区别．