Abstract
Peer-to-Peer (P2P) technology has emerged as a solution of the file dissemination to lessen server load and reduce average download time. Many efficient and secure solutions were proposed. Yet, in a peer-to-peer network,it is generally assumed that every node can send and receive files to and from any other node, while in practice, files can only be transmitted according to certain trust relationship among participating peers. Ku~et~al.~(GLOBECOM 2012) first studied the file dissemination problem under hierarchical trust relationship. They showed that when the trust relationship is defined as a rooted full binary tree, then there exists an optimal schedule for file dissemination taking $\lceil \log_2 n \rceil$ rounds, where $n$ is the total number of nodes including the source and destinations of broadcasting. Furthermore, they devised a linear-time algorithm to compute such a schedule. In this thesis, we extend the file dissemination problem with the trust relationship in the form of general binary tree, i.e., each internal node is not restricted to have exactly two children. We show that an optimal schedule for file dissemination remains $\lceil \log_2 n \rceil$ rounds, irrespective of the tree topology, and such a schedule can be computed in linear time. While we are extending Ku~et~al.'s results, our algorithm is based on a completely different approach. We have also considered the case of finding such an optimal schedule in the parallel setting, and propose an algorithm with parallel time complexity $O(h \log^{2} n)$, where $h$ denotes height of the tree. Finally, we show that the sequential algorithm and the parallel algorithm work for the case when the trust relationship is a rooted DAG such that the out-degree of each node is bounded by two.