Abstract
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 ?log_2 n? 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 paper, 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 ?log_2 n? 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. Furthermore, 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. Finally, we remark that our algorithms also produce asymptotically optimal schedules for general degree-d DAGs when d is a constant, while the problem becomes NP-hard even when the out-degree of each node in the DAG is limited to 6.