Every node of a network has a value which should be made known to all the other nodes. Some arbitrarily placed nodes and links may be faulty, however for each pair of fault-free nodes the number of fault-free paths of length 2 that connect them is linear in the size of the network. Faults are of crash type: faulty links do not transmit and faulty nodes neither send nor receive messages. In a unit of time a node can send or receive at most one packet containing the values of at most b nodes. For every 1 <= b <= n we present an asymptotically time-optimal randomized agorithm to exchange values between all the fault-free nodes with the probability exceeding 1 - ~- epsilon , where n is the number of nodes and epsilon > 0 is an arbitrary constant.
展开▼
机译：网络的每个节点都有一个值，所有其他节点都应知道该值。一些任意放置的节点和链接可能有故障，但是对于每对无故障节点，连接它们的长度为2的无故障路径的数目在网络规模上是线性的。故障属于崩溃类型：故障链路不传输，故障节点既不发送也不接收消息。在一个时间单位内，一个节点最多可以发送或接收一个包含最多b个节点的值的数据包。对于每1 <= b <= n，我们提出一个渐近时间最优的随机算法，以在所有无故障节点之间交换值，概率超过1-〜-epsilon，其中n是节点数，epsilon> 0为一个任意常数。
展开▼
