Reliable broadcasting and secure distributing in channel networks

Let T-1, ..., T-n be n spanning trees rooted at node r of graph G. If for any node v of G, among the n paths from r to v, each path in each spanning tree of T-1, ..., T-n, there are k (k less than or equal to n) internally disjoint paths, then T-1, ..., T-n are said to be (k, n)-independent spanning trees rooted at r. A graph G is called an (k, n)-channel graph if G has (k, n)-independent spanning trees rooted at each node of G. We study two fault-tolerant communication tasks in (k, n)-channel graphs. The first task is reliable broadcasting. We analyze the relation between the reliability and the efficiency of broadcasting. The second task is secure message distributing. It is required that each message should be received by its destination node and that we should keep the message secret from the nodes called adversaries. We give two message distribution schemes. The first scheme uses secret sharing, and it can tolerate t + k - n listening adversaries for any t < n if G is an (k, n)-channel graph. The second one uses unverifiable secret sharing, and it can tolerate t + k - n disrupting adversaries for any t < n/3 if G is an (k, n)-channel graph.