Abstract

A tree algorithm is a procedure that divides (splits) recursively into subsets an initial set of n items until each of the subsets obtained has a cardinality strictly less than some fixed number D. These algorithms have a wide range of applications: access protocols in communication networks, divide and conquer algorithms for data structures, leader election in distributed systems, ... The asymptotic behavior of additive cost functions associated to these algorithms is presented. When the successive splittings are assumed to be independent then, via an appropriate probabilistic representation of the quantities of interest, the asymptotic behavior of these algorithms can be obtained quite easily without resorting to complex analysis techniques as it is usually the case in this domain. When the successive splittings are not anymore independent but only stationary (dynamical source), it is shown the entropy function of the dynamical system determines the asymptotical behavior of the cost function. The key ingredient of all these results is a generalized renewal theorem.

Joint work with Mohamed

WEDNESDAY, April 26, 2006
Time: 4:30 P.M.
Location: WeH 7500