Reliable broadcasting and secure distributing in channel networks
Feng Bao, Yutaka Funyu, Yukihiro Hamada, Yoshihide Igarashi · 2002
Let T/sub 1/, /spl middot//spl middot//spl middot/, T/sub n/ be n spanning trees rooted at node r of graph G. If for any node /spl nu/ of G, among the n paths from r to /spl nu/, each path in each spanning tree of T/sub 1/, /spl middot//spl middot//spl middot/, T/sub n/, there are k (k/spl les/n) internally disjoint paths, then T/sub 1/, /spl middot//spl middot//spl middot/, T/sub n/, are said to be (k, n)-independent spanning trees rooted at r. A graph 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