Self-tuning Reactive Distributed Trees for Counting and Balancing

The main contribution of this paper is that it shows that it is possible to have reactive distributed trees for counting and balancing with no need for the user to fix manually any parameters. We present a data structure that in an on-line manner balances the trade-off between the tree traversal latency and the latency due to contention at the tree nodes. Moreover, the fact that our method can expand or shrink a subtree several levels in any adjustment step, has a positive effect in the efficiency: this feature helps the self-tuning reactive tree minimize the adjustment time, which affects not only the execution time of the process adjusting the size of the tree but also the latency of all other processes traversing the tree at the same time with no extra memory requirements. Our experimental study compared the new trees with the reactive diffracting ones on the SGI Origin2000, a well-known commercial ccNUMA multiprocessor. This study showed that the self-tuning reactive trees i) select the same tree depth as the reactive diffracting trees do; ii) perform better and iii) react faster.

Authors and Affiliations

1. Department of Comp. Science, Chalmers University of Technology, SE-412 96, Göteborg, Sweden

   Phuong Hoai Ha, Marina Papatriantafilou & Philippas Tsigas

Editors and Affiliations

1. Japan Science Technology and Agency, CREST, Japan

   Teruo Higashino

Reprints and permissions

© 2005 Springer-Verlag Berlin Heidelberg

Policies and ethics