Self-Adjusting Trees
Phuong Hoai Ha, Marina Papatriantafilou, Philippas Tsigas · 2003
The reactive diffracting trees are known efficient distributed data structures for supporting synchronization. They not only distribute a set of processes to smaller groups accessing different parts of the memory in a global coordinated manner, but also adjust their size in order to attain efficient performance across different levels of contention. However, the existing reactive adjustment policy of these trees is sensitive to parameters that have to be manually set in an optimal way and be determined after experimentation. Because these parameters depend on the application as well as on the system configuration, determining their optimal values is hard in practice. Moreover, because the reactive diffracting trees expand or shrink one level at a time, the cost of a multi-adjustment phase on a reactive tree can become high. We argue that these two problems are not fundamental, and that it is possible to construct reactive trees that: (i) are selfadjustable with no need of fixing manually any parameter, and (ii) have the ability to expand or shrink many levels at one time. In this paper...