University of Illinois Urbana-Champaign

Decentralized Schemes for Size Estimation in Large and Dynamic Groups

Kostoulas, Dionysios; Psaltoulis, Dimitrios; Gupta, Indranil; Briman, Ken; Demers, Al

Content Files
Decentralized Schemes for Size Estimation in Large and Dynamic Groups.pdf

Permalink

https://hdl.handle.net/2142/10972

Description

Title
Decentralized Schemes for Size Estimation in Large and Dynamic Groups
Author(s)
  • Kostoulas, Dionysios
  • Psaltoulis, Dimitrios
  • Gupta, Indranil
  • Briman, Ken
  • Demers, Al
Issue Date
2005-02
Keyword(s)
distributed systems
Date of Ingest
2009-04-17T16:17:40Z
Abstract
Large-scale and dynamically changing distributed systems such as the Grid, peer-to-peer overlays, etc., need to collect several kinds of global statistics in a decentralized manner. In this paper, we tackle a specific statistic collection problem called Group Size Estimation, for estimating the number of non-faulty processes present in the global group at any given point of time. We present two new decentralized algorithms for estimation in dynamic groups (i.e., where processes are constantly joining and crashing), analyze the algorithms, and experimentally evaluate them using real-life traces. One scheme is active: it spreads a gossip into the overlay first, and then samples the receipt times of this gossip at different processes. The second scheme is passive: it measures the density of processes when their identifiers are hashed into a real interval. Both schemes have low latency, scalable per-process overheads, and provide high levels of probabilistic accuracy for the estimate. They are implemented as part of a size estimation utility called PeerCounter that can be incorporated modularly into standard peer-to-peer overlays. We present experimental results from both the simulations and the PeerCounter utility, running on a cluster of 33 Linux servers. The studies measure and compare microbenchmarks for these approaches in static groups, as well as in dynamic groups with significant turnaround (arrival and departure) of processes - the latter experiments are driven by real-life traces.
Type of Resource
text
Genre of Resource
Technical Report
Permalink
http://hdl.handle.net/2142/10972
Copyright and License Information
You are granted permission for the non-commercial reproduction, distribution, display, and performance of this technical report in any format, BUT this permission is only for a period of 45 (forty-five) days from the most recent time that you verified that this technical report is still available from the University of Illinois at Urbana-Champaign Computer Science Department under terms that include this permission. All other rights are reserved by the author(s).

Owning Collections

Research and Tech Reports - Computer Science PRIMARY