TY - JOUR
T1 - Active and passive techniques for group size estimation in large-scale and dynamic distributed systems
AU - Kostoulas, Dionysios
AU - Psaltoulis, Dimitrios
AU - Gupta, Indranil
AU - Birman, Kenneth P.
AU - Demers, Alan J.
N1 - Funding Information:
This work was supported in part by DARPA AFOSR and in part by NSF (and by NSF CAREER Grant CNS-0448246).
Funding Information:
Dionysios Kostoulas completed his Master of Science from the Department of Computer Science in the University of Illinois at Urbana-Champaign in 2005. He was a recipient of the Graduate Student Fellowship from Lilian Voudouris Foundation (2004–2005), a Fulbright Scholar (2003–2004), a Triantafyllou Scholar (2003–2004), and received a Graduate Student Scholarship from the Gerondelis Foundation (2003–2004).
PY - 2007/10
Y1 - 2007/10
N2 - This paper presents two solutions to a distributed statistic collection problem, called Group Size Estimation. These algorithms are intended for large-scale and dynamic distributed systems such as Grids, peer-to-peer overlays, etc. Each algorithm estimates (both in a one-shot and continuous manner) the number of non-faulty processes present in the global group. The first active scheme samples receipt times of gossip messages, while the second passive scheme calculates the density of process identifiers when hashed to a real interval. Our analysis, trace-driven simulation and deployment on a 33-node Linux cluster study and compare the latencies, scalability, and accuracy of these schemes.
AB - This paper presents two solutions to a distributed statistic collection problem, called Group Size Estimation. These algorithms are intended for large-scale and dynamic distributed systems such as Grids, peer-to-peer overlays, etc. Each algorithm estimates (both in a one-shot and continuous manner) the number of non-faulty processes present in the global group. The first active scheme samples receipt times of gossip messages, while the second passive scheme calculates the density of process identifiers when hashed to a real interval. Our analysis, trace-driven simulation and deployment on a 33-node Linux cluster study and compare the latencies, scalability, and accuracy of these schemes.
KW - Algorithm design and analysis
KW - Epidemics
KW - Group size estimation
KW - Large-scale distributed systems
KW - Probabilistic protocols
UR - http://www.scopus.com/inward/record.url?scp=34547770894&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=34547770894&partnerID=8YFLogxK
U2 - 10.1016/j.jss.2007.01.014
DO - 10.1016/j.jss.2007.01.014
M3 - Article
AN - SCOPUS:34547770894
SN - 0164-1212
VL - 80
SP - 1639
EP - 1658
JO - Journal of Systems and Software
JF - Journal of Systems and Software
IS - 10
ER -