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-p≤0.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(n·K+K ⁴) time where K=min∈{4(log∈(1-p) ^-1) ^-1,n} and n is the number of normal users. © 2010 Springer Science+Business Media, LLC.