Computing in fault tolerance broadcast networks
Computing in fault tolerance broadcast networks
复制标题
容错广播网络中的计算
DOI：
10.1109/ccc.2004.1313813
复制
发表时间：
2004
期刊：
影响因子：
--
通讯作者：
I. Newman
中科院分区：
文献类型：
--
作者：
I. Newman
我们考虑一个容错广播网络的n个处理器，每个持有一个比特的信息。目标是在n位上计算给定的布尔函数。在每个步骤中，处理器可以广播一位信息。每个监听处理器接收以固定常数/spl epsi/为界的错误概率广播的比特。不同步骤中的误差以及同一步骤中不同接收处理器的误差是相互独立的。在这个模型中考虑的协议是不经意的协议：在每一步，广播的处理器是预先固定的，并且独立于前一步的输入和结果。该模型中的原始复杂性度量是协议执行的广播总数。我们在这里提出了几类布尔函数的第一个线性复杂度协议，包括OR函数，具有O（1）-minterm（maxterm）大小的函数，具有线性大小的函数AC/sub 0/公式和一些其他函数。考虑到El-Gamal（1984）和Gallager（1988）的容错模型，这回答了Yao（1997）的一个开放性问题。
We consider a fault tolerance broadcast network of n processors each holding one bit of information. The goal is to compute a given Boolean function on the n bits. In each step, a processor may broadcast one bit of information. Each listening processor receives the bit that was broadcasted with error probability bounded by a fixed constant /spl epsi/. The errors in different steps, as well as for different receiving processors in the same step, are mutually independent. The protocols that are considered in this model are oblivious protocols: At each step, the processors that broadcast are fixed in advanced and independent of the input and the outcome of previous steps. The primal complexity measure in this model is the total number of broadcasts that is performed by the protocol. We present here the first linear complexity protocols for several classes of Boolean functions, including the OR function, functions that have O(l)-minterm (maxterm) size, functions that have linear size AC/sub 0/ formulae and some other functions. This answer an open question of Yao (1997), considering this fault tolerance model of El-Gamal (1984) and Gallager (1988).