Adam2: Reliable Distribution Estimation in Decentralised Environments

Abstract

To enable decentralised actions in very large distributed systems, it is often important to provide the nodes with global knowledge about the values of attributes across all nodes. This paper shows how, given an attribute whose values are distributed across a large decentralised system, each node can efficiently estimate the statistical distribution of these values. Simulations using heavily skewed real-world node attribute distributions show that our estimation methods outperform the state-of-the-art heuristics by an order of magnitude with an average error of 0.05% and a maximum error of 2%. To obtain this accuracy, each node sends on average just 120 kB of data independent of the system size. Our algorithms also achieve this accuracy in the presence of heavy churn of system membership. Furthermore, our algorithm enables self-tuning by continuously estimating the accuracy of its own distribution approximation.

Download

• The paper, in PDF (328,489 bytes)
• See also: the XtreemOS Project.

Bibtex Entry

@InProceedings{,
  author = 	 {Jan Sacha and Jeff Napper and Corina Stratan 
                  and Guillaume Pierre},
  title = 	 {Adam2: Reliable Distribution Estimation in 
                  Decentralised Environments},
  booktitle = 	 {Proceedings of the 30th IEEE International Conference 
                  on Distributed Computing Systems (ICDCS)},
  year = 	 {2010},
  month = 	 jun
}