
For FullText PDF, please login, if you are a member of IEICE,
or go to Pay Per View on menu list, if you are a nonmember of IEICE.

Reliable Broadcasting and Secure Distributing in Channel Networks
Feng BAO Yutaka FUNYU Yukihiro HAMADA Yoshihide IGARASHI
Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Vol.E81A
No.5
pp.796806 Publication Date: 1998/05/25 Online ISSN:
DOI: Print ISSN: 09168508 Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications) Category: Keyword: broadcasting, distributing, fault tolerance, independent spanning trees, networks, secret sharing,
Full Text: PDF>>
Summary:
Let T_{1}, , T_{n} be n spanning trees rooted at node r of graph G. If for any node v, n paths from r to v, each path in each spanning tree of T_{1}, , T_{n}, are internally disjoint, then T_{1}, , T_{n} are said to be independent spanning trees rooted at r. A graph G is called an nchannel graph if G has n independent spanning trees rooted at each node of G. We generalize the definition of nchannel graphs. 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 internally disjoint paths, then T_{1}, , T_{n} are said to be (k,n)independent spanning trees rooted at r of G. A graph G is called a (k,n)channel graph if G has (k,n)independent spanning trees rooted at each node of G. We study two faulttolerant 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 in (k,n)channel graphs. The second task is secure message distribution such that one node called the distributor attempts to send different messages safely to different nodes. We should keep each message secret from the nodes called adversaries. We give two message distribution schemes in (k,n)channel graphs. The first scheme uses secret sharing, and it can tolerate up to t+kn listening adversaries for any t < n if G is a (k,n)channel graph. The second scheme uses unverifiable secret sharing, and it can tolerate up to t+kn disrupting adversaries for any t < n/3 if G is a (k,n)channel graph.

