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

【Abstract】 This paper studies the randomness-time tradeoff for distributed random ized oblivious routing (DROR).The main result is: For any graph G with n ver tices,maximum degree d and for any DROR algorithm A on G,if A terminates in T steps with probability Q(logd nT, QM 1 ), A must use at least log random bits. Then, Valiant’s two-phase routing algorithm is nearly optimal. Combined with previous results, the main theorem also reflects the essential difference between distributed and centralized algorithms.更多还原