Unconditionally reliable message transmission in directed hypergraphs

We study the problem of unconditionally reliable message transmission (URMT), where a sender S and a receiver R are part of a synchronous network modeled as a directed hypergraph, a part of which may be under the influence of an adversary having unbounded computing power. S intends to transmit a message m to R, such that R should correctly obtain S's message with probability at least (1∈-∈δ) for arbitrarily small δ>∈0. However, unlike most of the literature on this problem, we assume the adversary modeling the faults is threshold mixed, and can corrupt different set of nodes in Byzantine, passive and fail-stop fashion simultaneously. The main contribution of this work is the complete characterization of URMT in directed hypergraph tolerating such an adversary, which is done for the first time in the literature. © 2008 Springer Berlin Heidelberg.