A STEADY-STATE ANALYSIS OF DIFFRACTING TREES

Diffracting trees are an effective and highly scalable distributed-par allel technique for shared counting and load balancing. This paper pre sents the first steady-state combinatorial model and analysis for diff racting trees, and uses it to answer several critical algorithmic desi gn questions. Our model is simple and sufficiently high level to overc ome many implementation-specific details, and yet as we show it is ric h enough to predict empirically observed behaviors accurately. As a re sult of our analysis we were able to identify starvation problems in t he original diffracting tree algorithm and modify it to a create a mor e stable version. We were also able to identify the range in which the diffracting tree performs most efficiently, and the ranges in which i ts performance degrades. We believe our model and modeling approach op en the way to steady-state analysis of other distributed-parallel stru ctures such as counting networks and elimination trees.