Average and randomized complexity of distributed problems

作     者：AllenbergNavony, N Itai, A Moran, S 

作者机构：TECHNION ISRAEL INST TECHNOLDEPT COMP SCIIL-32000 HAIFAISRAEL 

出 版 物：《SIAM JOURNAL ON COMPUTING》 (工业与应用数学会计算杂志)

年 卷 期：1996年第25卷第6期

页      面：1254-1267页

核心收录：

学科分类：07[理学] 070104[理学-应用数学] 0701[理学-数学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主　　题：distributed computing randomized algorithms average complexity message complexity bit complexity lower bounds Yao's lemma 

摘      要：Yao proved that in the decision-tree model, the average complexity of the best deterministic algorithm is a lower bound on the complexity of randomized algorithms that solve the same problem. Here it is shown that a similar result does not always hold in the common model of distributed computation, the model in which all the processors run the same program (which may depend on the processors input). We therefore construct a new technique that together with Yao s method enables us to show that in many cases, a similar relationship does hold in the distributed model. This relationship enables us to carry over known lower bounds an the complexity of deterministic computations to the realm of randomized computations, thus obtaining new results. The new technique can also be used for obtaining results concerning algorithms with bounded error.