Abstract
The distributed aggregation of simple aggregates such as minima/maxima, counts, sums and averages have been studied in the past and are important tools for distributed algorithms and network coordination. Nonetheless, this kind of aggregates may not be comprehensive enough to characterize biased data distributions or when in presence of outliers, making the case for richer estimates.
This work presents Spectra, a distributed algorithm for the estimation of distribution functions over large scale networks. The estimate is available at all nodes and the technique depicts important properties: robustness when exposed to high levels of message loss, fast convergence speed and fine precision in the estimate. It can also dynamically cope with changes of the sampled local property and with churn, without requiring restarts. The proposed approach is experimentally evaluated and contrasted to a competing state of the art distribution aggregation technique.
Chapter PDF
Similar content being viewed by others
Keywords
- Cumulative Distribution Function
- Large Scale Network
- Fast Convergence Speed
- Message Loss
- Interpolation Interval
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Almeida, P.S., Baquero, C., Farach-Colton, M., Jesus, P., Mosteiro, M.A.: Fault-Tolerant Aggregation: Flow-Updating Meets Mass-Distribution. In: Fernàndez Anta, A., Lipari, G., Roy, M. (eds.) OPODIS 2011. LNCS, vol. 7109, pp. 513–527. Springer, Heidelberg (2011)
Borges, M., Jesus, P., Baquero, C., Almeida, P.S.: Spectra: Robust estimation of distribution functions in networks. Tech. Rep. CoRR abs/1204.1373v1, HASLab / INESC TEC & Universidade do Minho (2012), http://arxiv.org/abs/1204.1373v1
Cheng, S., Li, J., Ren, Q., Yu, L.: Bernoulli Sampling Based (ε, δ)-Approximate Aggregation in Large-Scale Sensor Networks. In: 29th IEEE Conference on Information Communications (INFOCOM), pp. 1–9 (2010)
Ganesh, A.J., Kermarrec, A.M., Le Merrer, E., Massoulié, L.: Peer counting and sampling in overlay networks based on random walks. Distributed Computing 20(4), 267–278 (2007)
Haridasan, M., van Renesse, R.: Gossip-based Distribution Estimation in Peer-to-Peer Networks. In: 7th International Conference on Peer-To-Peer Systems (IPTPS). USENIX Association (2008)
Jelasity, M., Montresor, A.: Epidemic-style proactive aggregation in large overlay networks. In: Proceedings of the 24th International Conference on Distributed Computing Systems (ICDCS 2004), pp. 102–109. IEEE Computer Society (2004)
Jelasity, M., Montresor, A., Babaoglu, O.: Gossip-based aggregation in large dynamic networks. ACM Transactions on Computer Systems 23(3), 219–252 (2005)
Jesus, P., Baquero, C., Almeida, P.S.: Fault-Tolerant Aggregation for Dynamic Networks. In: 29th IEEE Symposium on Reliable Distributed Systems, pp. 37–43 (2010)
Jesus, P., Baquero, C., Almeida, P.S.: A Survey of Distributed Data Aggregation Algorithms. Tech. Rep. CoRR abs/1110.0725, HASLab / INESC TEC & Universidade do Minho (2011), http://arxiv.org/abs/1110.0725
Lynch, N.A.: Distributed algorithms, pp. 17–23. Kaufmann Publishers Inc. (1996)
Sacha, J., Napper, J., Stratan, C., Pierre, G.: Adam2: Reliable distribution estimation in decentralised environments. In: 2010 IEEE 30th International Conference on Distributed Computing Systems (ICDCS), pp. 697–707 (June 2010)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2012 IFIP International Federation for Information Processing
About this paper
Cite this paper
Borges, M., Jesus, P., Baquero, C., Almeida, P.S. (2012). Spectra: Robust Estimation of Distribution Functions in Networks. In: Göschka, K.M., Haridi, S. (eds) Distributed Applications and Interoperable Systems. DAIS 2012. Lecture Notes in Computer Science, vol 7272. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-30823-9_8
Download citation
DOI: https://doi.org/10.1007/978-3-642-30823-9_8
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-30822-2
Online ISBN: 978-3-642-30823-9
eBook Packages: Computer ScienceComputer Science (R0)