TY - GEN
T1 - An unstructured termination detection algorithm using gossip in cloud computing environments
AU - Lim, Jong Beom
AU - Chung, Kwang Sik
AU - Gil, Joon Min
AU - Suh, Tae Weon
AU - Yu, Heon Chang
PY - 2013
Y1 - 2013
N2 - Determining termination in dynamic environments is hard due to node joining and leaving. In previous studies on termination detection, some structures, such as spanning tree or computational tree, are used. In this work, we present an unstructured termination detection algorithm, which uses a gossip based scheme to cope with scalability and fault-tolerance issues. This approach allows the algorithm not to maintain specific structures even when nodes join and leave during runtime. These dynamic behaviors are prevalent in cloud computing environments and little attention has been paid by existing approaches. To measure the complexity of our proposed algorithm, a new metric, self-centered message complexity is used. Our evaluation over scalable settings shows that an unstructured approach has a significant merit to solve scalability and fault-tolerance problems with lower message complexity over existing algorithms.
AB - Determining termination in dynamic environments is hard due to node joining and leaving. In previous studies on termination detection, some structures, such as spanning tree or computational tree, are used. In this work, we present an unstructured termination detection algorithm, which uses a gossip based scheme to cope with scalability and fault-tolerance issues. This approach allows the algorithm not to maintain specific structures even when nodes join and leave during runtime. These dynamic behaviors are prevalent in cloud computing environments and little attention has been paid by existing approaches. To measure the complexity of our proposed algorithm, a new metric, self-centered message complexity is used. Our evaluation over scalable settings shows that an unstructured approach has a significant merit to solve scalability and fault-tolerance problems with lower message complexity over existing algorithms.
KW - Cloud computing
KW - Gossip
KW - Termination detection
KW - Unstructured algorithm
UR - http://www.scopus.com/inward/record.url?scp=84874220569&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84874220569&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-36424-2_1
DO - 10.1007/978-3-642-36424-2_1
M3 - Conference contribution
AN - SCOPUS:84874220569
SN - 9783642364235
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 1
EP - 12
BT - Architecture of Computing Systems, ARCS 2013 - 26th International Conference, Proceedings
T2 - 26th International Conference on Architecture of Computing Systems, ARCS 2013
Y2 - 19 February 2013 through 22 February 2013
ER -