An evaluation of dynamic labeling schemes for tree networks

TY - GEN

T1 - An evaluation of dynamic labeling schemes for tree networks

AU - Rotbart, Noy Galil

AU - Vaz Salles, Marcos António

AU - Zotos, Iasonas

N1 - Conference code: 13

PY - 2014

Y1 - 2014

N2 - We present an implementation and evaluation based on simulation of dynamic labeling schemes for tree networks. Two algorithms are studied: a general scheme that converts static labeling schemes to dynamic, and a specialized dynamic distance labeling scheme. Our study shows that theoretical bounds only partially portray the performance of such dynamic labeling schemes in practice. First, we observe order-of-magnitude differences between the gains in label size when compared to the number of messages passed. Second, we demonstrate a significant bottleneck in the tree network, suggesting that the current practice of counting total messages passed in the whole network is insufficient to properly characterize performance of these distributed algorithms. Finally, our experiments provide intuition on the worst case scenarios for the stated algorithms, in particular path tree networks and fully dynamic schemes permitting both node additions and deletions.

AB - We present an implementation and evaluation based on simulation of dynamic labeling schemes for tree networks. Two algorithms are studied: a general scheme that converts static labeling schemes to dynamic, and a specialized dynamic distance labeling scheme. Our study shows that theoretical bounds only partially portray the performance of such dynamic labeling schemes in practice. First, we observe order-of-magnitude differences between the gains in label size when compared to the number of messages passed. Second, we demonstrate a significant bottleneck in the tree network, suggesting that the current practice of counting total messages passed in the whole network is insufficient to properly characterize performance of these distributed algorithms. Finally, our experiments provide intuition on the worst case scenarios for the stated algorithms, in particular path tree networks and fully dynamic schemes permitting both node additions and deletions.

U2 - 10.1007/978-3-319-07959-2_17

DO - 10.1007/978-3-319-07959-2_17

M3 - Article in proceedings

SN - 978-3-319-07958-5

T3 - Lecture notes in computer science

SP - 199

EP - 210

BT - Experimental Algorithms

A2 - Gudmundsson, Joachim

A2 - Katajainen, Jyrki

PB - Springer

T2 - 13th International Symposium on Experimental Algorithms

Y2 - 29 June 2014 through 1 July 2014

ER -