随机Oblivious路由算法中随机性与时间代价的研究

• 作 者: 张立 戴一奇 等
• 机 构: 清华大学计算机科学与技术系
• 出 处: 计算机学报
• 发表日期: 1996年5期
• 关键词: 路由算法 随机性 时间代价 互连网络 Oblivious routing algorithm randomness-time tradeoff interc
• 基金项目: 清华大学自然科学基金

本文研究了分布式随机Oblivious路由算法中随机性与时间代价的关系。证明了：对于n个结点，最大结点度为d的图G及其上的任意一个分布式随机路由算法，若该算法以概率Q(1/2<Q<1)在T步（logdn≤T≤√n/4ed）内完成，则它至少需使用n/2log√n/dT+√nlogQ/4dT-2n个随机位。从而证明了Valiant二阶段路由算法的使用的随机位数目是近似最优的。结合本文及文献[10]中的结果，还反映了分布式算法与集中式算法之间的深刻区别。