Probabilistic reliability and privacy of communication using multicast in general neighbor networks (Q2425532)

This paper studies the possibility of reliable and secure communication in general communication networks. The authors characterize this possibility in general neighbor graphs. In the model considered by them communication is multicast, i.e. if a player casts a message it is received by all its neighbours. Furthermore, communication takes place in rounds and is synchronous. The adversary is byzantine: given a number of players \(t\), the adversary takes control of a coalition of \(t\) nodes and chooses their messages at will. In this model, the authors prove that reliable and secure information transmission is possible if and only if the number of paths from the sender to the receiver exceeds the number of faulty players. This paper extends an earlier result by \textit{M. Franklin} and \textit{R. N. Wright} [J. Cryptology 13, No. 1, 9--30 (2000; Zbl 0957.68042)] where it was proved for particular neighbor graphs with neighbor-disjoint paths.