The Accuracy of Tree-based Counting in Dynamic Networks

Details The Accuracy of Tree-based Counting in Dynamic Networks The Accuracy of Tree-based Counting in Dynamic Networks

2010-04-26

arxiv.org/abs/1004.4559v1

Computer Science

Distributed, Parallel, and Cluster Computing

15 pages, 3 figures

Scientific paper

Tree-based protocols are ubiquitous in distributed systems. They are flexible, they perform generally well, and, in static conditions, their analysis is mostly simple. Under churn, however, node joins and failures can have complex global effects on the tree overlays, making analysis surprisingly subtle. To our knowledge, few prior analytic results for performance estimation of tree based protocols under churn are currently known. We study a simple Bellman-Ford-like protocol which performs network size estimation over a tree-shaped overlay. A continuous time Markov model is constructed which allows key protocol characteristics to be estimated, including the expected number of nodes at a given (perceived) distance to the root and, for each such node, the expected (perceived) size of the subnetwork rooted at that node. We validate the model by simulation, using a range of network sizes, node degrees, and churn-to-protocol rates, with convincing results.

Affiliated with

Also associated with

No associations

Rating

The Accuracy of Tree-based Counting in Dynamic Networks does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with The Accuracy of Tree-based Counting in Dynamic Networks, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The Accuracy of Tree-based Counting in Dynamic Networks will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-32608