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.
|Title of host publication||Proceedings of the 30th International Conference on Distributed Computing Systems|
|Place of Publication||Los Alamitos, CA, USA|
|Publisher||IEEE Computer Society Press|
|Publication status||Published - 2010|
|Event||International Conference on Distributed Computing Systems (ICDCS) - Los Alamitos, CA, USA|
Duration: 1 Jan 2010 → 1 Jan 2010
|Conference||International Conference on Distributed Computing Systems (ICDCS)|
|Period||1/01/10 → 1/01/10|
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.