Adam2: Reliable Distribution Estimation in Decentralised Environments

J. Sacha, J.M. Napper, C. Stratan, G.E.O. Pierre

Research output: Chapter in Book / Report / Conference proceedingConference contributionAcademicpeer-review

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.
Original languageEnglish
Title of host publicationProceedings of the 30th International Conference on Distributed Computing Systems
Place of PublicationLos Alamitos, CA, USA
PublisherIEEE Computer Society Press
Pages697-707
ISBN (Print)9780769540597
Publication statusPublished - 2010
EventInternational Conference on Distributed Computing Systems (ICDCS) - Los Alamitos, CA, USA
Duration: 1 Jan 20101 Jan 2010

Conference

ConferenceInternational Conference on Distributed Computing Systems (ICDCS)
Period1/01/101/01/10

Fingerprint Dive into the research topics of 'Adam2: Reliable Distribution Estimation in Decentralised Environments'. Together they form a unique fingerprint.

  • Cite this

    Sacha, J., Napper, J. M., Stratan, C., & Pierre, G. E. O. (2010). Adam2: Reliable Distribution Estimation in Decentralised Environments. In Proceedings of the 30th International Conference on Distributed Computing Systems (pp. 697-707). Los Alamitos, CA, USA: IEEE Computer Society Press.