Brief Announcement: The Accuracy of Tree-based Counting in Dynamic Networks
2010 (English)In: PODC 2010: PROCEEDINGS OF THE 2010 ACM SYMPOSIUM ON PRINCIPLES OF DISTRIBUTED COMPUTING, NEW YORK: ASSOC COMPUTING MACHINERY , 2010, 291-292 p.Conference paper (Refereed)
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 under churn, 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 simulations, using a range of network sizes, node degrees, and churn-to-protocol rates, with convincing results.
Place, publisher, year, edition, pages
NEW YORK: ASSOC COMPUTING MACHINERY , 2010. 291-292 p.
Markov model, distributed spanning tree
IdentifiersURN: urn:nbn:se:kth:diva-36023DOI: 10.1145/1835698.1835770ISI: 000286908100060ScopusID: 2-s2.0-77956243165OAI: oai:DiVA.org:kth-36023DiVA: diva2:429963
2010 ACM SYMPOSIUM ON PRINCIPLES OF DISTRIBUTED COMPUTING
QC 201107062011-07-062011-07-062016-05-11Bibliographically approved