Optimal tree structure with loyal users and batch updates
We study the probabilistic model in the key tree management problem. Users have different behaviors. Normal users have probability p to issue join/leave request while the loyal users have probability zero. Given the numbers of such users, our objective is to construct a key tree with minimum expected updating cost. We observe that a single LUN (Loyal User Node) is enough to represent all loyal users. When 1-pa parts per thousand currency sign0.57 we prove that the optimal tree that minimizes the cost is a star. When 1-p > 0.57, we try to bound the size of the subtree rooted at every non-root node. Based on the size bound, we construct the optimal tree using dynamic programming algorithm in O(na <...K+K (4)) time where K=min {4(log (1-p)(-1))(-1),n} and n is the number of normal users.
optimality key trees probability updating cost group keys