CPL - Chalmers Publication Library
| Utbildning | Forskning | Styrkeområden | Om Chalmers | In English In English Ej inloggad.

Self-tuning Reactive Distributed Trees for Counting and Balancing

Phuong Ha (Institutionen för datavetenskap, Datakommunikation och Distribuerade System) ; Marina Papatriantafilou (Institutionen för datavetenskap, Datakommunikation och Distribuerade System) ; Philippas Tsigas (Institutionen för datavetenskap, Datakommunikation och Distribuerade System)
Lecture Notes in Computer Science (0302-9743). Vol. 3544 (2004), p. 140-157.
[Artikel, refereegranskad vetenskaplig]

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.

Proceedings paper in: 8th International Conference on Principles of Distributed Systems (OPODIS 2004), Grenoble, FRANCE.DEC 15-17, 2004

Denna post skapades 2006-08-25. Senast ändrad 2013-06-19.
CPL Pubid: 2866


Läs direkt!

Länk till annan sajt (kan kräva inloggning)

Institutioner (Chalmers)

Institutionen för datavetenskap, Datakommunikation och Distribuerade System (2002-2004)


Information Technology

Chalmers infrastruktur

Relaterade publikationer

Denna publikation ingår i:

Reactive Concurrent Data Structures and Algorithms for Synchronization