Reliable Broadcasting in Logarithmic Time with Byzantine Link Failures |
| |
Authors: | Piotr Berman Krzysztof Diks Andrzej Pelc |
| |
Institution: | aComputer Science Department, The Pennsylvania State University, University Park, Pennsylvania, 16802;bInstytut Informatyki, Universytet Warszawski, Banacha 2, 02-097, Warsaw, Poland;cDépartement d'Informatique, Université du Québec à Hull, C.P. 1250, Succursale B, Hull, Quebec, J8X 3X7, Canada |
| |
Abstract: | Broadcasting is a process of transmitting a message held in one node of a communication network to all other nodes. Links of the network are subject to randomly and independently distributed faults with probability; faults are permanent and Byzantine, while all nodes are fault-free. In a unit of time, each node can communicate with at most one other node. We present a broadcasting algorithm which works fornnodes in timeO(log n) with probability of correctness exceeding 1 − 1/n, for sufficiently largen. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|