More Web Proxy on the site http://driver.im/

research-article

A self-organization mechanism based on cross-entropy method for P2P-like applications

Authors:

Abdolhossein Sarrafzadeh,

Liang ZhangAuthors Info & Claims

ACM Transactions on Autonomous and Adaptive Systems (TAAS), Volume 5, Issue 4

Article No.: 15, Pages 1 - 31

https://doi.org/10.1145/1867713.1867716

Published: 19 November 2010 Publication History

Abstract

P2P-like applications are quickly gaining popularity in the Internet. Such applications are commonly modeled as graphs with nodes and edges. Usually nodes represent running processes that exchange information with each other through communication channels as represented by the edges. They often need to autonomously determine their suitable working mode or local status for the purpose of improving performance, reducing operation cost, or achieving system-level design goals. In order to achieve this objective, the concept of status configuration is introduced in this article and a mathematical correspondence is further established between status configuration and an optimization index (OI), which serves as a unified abstraction of any system design goals. Guided by this correspondence and inspired by the cross-entropy algorithm, a cross-entropy-driven self-organization mechanism (CESM) is proposed in this article. CESM exhibits the self-organization property since desirable status configurations that lead to high OI values will quickly emerge from purely localized interactions. Both theoretical and experimental analysis have been performed. The results strongly indicate that CESM is a simple yet effective technique which is potentially suitable for many P2P-like applications.

References

[1]

Altman, E., Jimenez, T., and Koole, G. 2001. On optimal call admission control in resource-sharing system. IEEE Trans. Comm. 49, 9, 1659--1668.

[2]

Androutsellis-Theotokis, S. and Spinellis, D. 2004a. A survey of peer-to-peer content distribution technologies. ACM Comput. Surv. 36, 4, 335--371.

Digital Library

[3]

Androutsellis-Theotokis, S. and Spinellis, D. 2004b. A survey of peer-to-peer content distribution technologies. ACM Comput. Surv. 36, 4, 335--371.

Digital Library

[4]

Angluin, D., Aspnes, J., Diamadi, Z., Fischer, M. J., and Peralta, R. 2004. Computation in networks of passively mobile finite-state sensors. In Proceedings of the 23rd Annual ACM Symposium on Principles of Distributed Computing. 290--299.

Digital Library

[5]

Bäck, T. and Schwefel, H. P. 1993. An overview of evolutionary algorithms for parameter optimization. Evolut. Comput. 1, 1, 1--23.

Digital Library

[6]

Bonabeau, E., Dorigo, M., and Theraulaz, G. 1999. Swarm Intelligence: From Natural to Artificial Systems. Oxford University Press.

[7]

Bridgewater, J. S. A., Boykin, P. O., and Roychowdhury, V. P. 2007. Balanced overlay networks (bon): An overlay technology for decentralized load balancing. IEEE Trans. Parallel Distrib. Syst. 18, 8, 1122--1133.

Digital Library

[8]

Chakravarti, A. J., Baumgartner, G., and Lauria, M. 2005. The organic grid: Self-Organizing computation on a peer-to-peer network. IEEE Trans. Syst. Man Cybernet. 35, 3, 373--384.

Digital Library

[9]

Chen, G., Low, C. P., and Yang, Z. H. 2008. Coordinated services provision in peer-to-peer environments. IEEE Trans. Parallel Distrib. Syst. 19, 4, 433--446.

Digital Library

[10]

Cicirello, V. A. and Smith, S. F. 2004. Wasp-like agents for distributed factory coordination. Auton. Agents Multi-Agent Syst. 8, 237--266.

Digital Library

[11]

Cuenca-Acuna, F. M. and Nguyen, T. D. 2004. Self-managing federated services. In Proceedings of the 23rd IEEE International Symposium on Reliable Distributed Systems.

Digital Library

[12]

Fogel, D. B. 1995. Evolutionary Computation: Toward a New Philosophy of Machine Intelligence. IEEE Press, New York.

Digital Library

[13]

Forestiero, A., Mastroianni, C., and Meo, M. 2009. Self-Chord: A bio-inspired algorithm for structured p2p systems. In Proceedings of the 9th IEEE International Symposium on Cluster Computing and the Grid.

Digital Library

[14]

Gedik, B. and Liu, L. 2005. A scalable peer-to-peer architecture for distributed information monitoring applications. IEEE Trans. Comput. 54, 6, 767--782.

Digital Library

[15]

Ghanea-Hercock, R. A., Wang, F., and Sun, Y. 2006. Self-Organizing and adaptive peer-to-peer network. IEEE Trans. Syst. Man Cybernet. B 36, 6, 1230--1236.

Digital Library

[16]

Goldberg, D. E. 1989. Genetic Algorithms in Search, Optimization, and Machine Learning. Addison-Wesley Professional.

Digital Library

[17]

Goldsrmidt, G. and Yemin, Y. 1995. Decentralizing control and intelligence in network management. In Proceedings of the 4th International Symposium on Integrated Network Management.

Digital Library

[18]

Gu, X. and Nahrstedt, K. 2006. Distributed multimedia service composition with statistical qos assurances. IEEE Trans. Multimed. 8, 1, 141--151.

Digital Library

[19]

Gu, X., Wen, Z., and Yu, P. S. 2007. BridgeNet: An adaptive multi-source stream dissemination overlay network. In Proceedings of the 26th IEEE International Conference on Computer Communications (InfoCom. 2586--2590.

[20]

Gupta, R., Sekhri, V., and Somani, A. K. 2006. Compup2p: An architecture for internet computing using peer-to-peer networks. IEEE Trans. Parall. Distrib. Syst. 17, 11, 1306--1320.

Digital Library

[21]

Heegaard, P. E., Helvik, B. E., and Wittner, O. J. 2008. The cross entropy ant system for network path management. Telektronikk 104, 01, 19--40.

[22]

Jin, H., Ning, X., and Chen, H. 2006. Efficient search for peer-to-peer information retrieval using semantic small world. In Proceedings of Internation Conference on World Wide Web Poster (WWW). 1003--1004.

Digital Library

[23]

Karger, D. R. and Ruhl, M. 2004. Simple efficient load balancing algorithms for peer-to-peer systems. In Proceedings of the 16th Annual ACM Symposium on Parallelism in Algorithms and Architectures.

Digital Library

[24]

Kempe, D., Dobra, A., and Gehrke, J. 2003. Gossip-based computation of aggregate information. In Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science.

Digital Library

[25]

Keyani, P., Larson, B., and Senthil, M. 2002. Peer pressure: Distributed discovery from attacks in peer-to-peer systems. In Proceedings of the International Workshop on Peer-to-Peer Computing. 306--320.

Digital Library

[26]

Kleinberg, J. 2000. The small-world phenomenon: An algorithmic perspective. In Proceedings of the 32nd ACM Symposium on Theory of Computing.

Digital Library

[27]

Ko, S. Y., Gupta, I., and Jo, Y. 2008. A new class of nature-inspired algorithms for self-adaptive peer-to-peer computing. ACM Trans. Auton. Adapt. Syst. 3, 3.

Digital Library

[28]

Ledlie, J., Taylor, J. M., Serban, L., and Seltzer, M. 2002. Self-Organization in peer-to-peer systems. In Proceedings of the 10th Workshop on ACM SIGOPS European Workshop. 125--132.

Digital Library

[29]

Li, M., Lee, W., and Sivasubramaniam, A. 2004. Semantic small world: An overlay network for peer-to-peer search. In Proceedings of the 12th IEEE International Conference on Network Protocols (ICNP).

Digital Library

[30]

Liang, J., Gu, X., and Nahrstedt, K. 2007. Self-configuring information management for large-scale service overlays. In Proceedings of the 26th IEEE International Conference on Computer Communications (InfoCom). 472--480.

[31]

Lua, E. K., Crowcroft, J., Pias, M., Sharma, R., and Lim, S. 2005. A survey and comparison of peer-to-peer overlay network schemes. IEEE Comm. Surv. Tutor. 7, 2, 72--93.

Digital Library

[32]

Manku, G. S., Bawa, M., and Raghavan, P. 2003. Symphony: Distributed hashing in a small world. In Proceedings of the 4th USENIX Symposium on Internet Technologies and Systems (USITS).

Digital Library

[33]

Martello, S. and Toth, P. 1990. Knapsack Problems: Algorithms and Computer Implementations. John Wiley & Sons.

Digital Library

[34]

Medina, A., Lakhina, A., Matta, I., and Byers, J. 2001. BRITE: An approach to universal topology genration. In Proceedings of the IEEE International Symposium on Modeling, Analysis, and Simulation of Computer and Telecommunications Systems.

Digital Library

[35]

Mu, S., Chi, C. H., Liu, L., and Wang, H. G. 2006. Object placement and caching strategies on AN. P2P^&ast;. In Advances in Web-Age Information Management. Springer, 182--192.

Digital Library

[36]

Nocedal, J. and Wright, S. 2009. Numerical Optimization. Springer.

[37]

Pandurangan, G., Raghavan, P., and Upfal, E. 2001. Building low-diameter P2P networks. In Proceedings of the 42nd IEEE Symposium on Foundations of Computer Science. 492--499.

Digital Library

[38]

Papadimitriou, C. H. and Steiglitz, K. 1998. Combinatorial Optimization: Algorithms and Complexity. Dover Publications.

Digital Library

[39]

Prokopenko, M., Gerasimov, V., and Tanev, I. 2006. Evolving spatiotemporal coordination in a modular robotic system. In Proceedings of the 9th International Conference on the Simulation of Adaptive Behavior, S. Nolfi et al., Eds. 558--569.

Digital Library

[40]

Ramaswamy, L., Gedik, B., and Liu, L. 2005. A distributed approach to node clustering in decentralized peer-to-peer networks. IEEE Trans. Parall. Distrib. Syst. 16, 9, 814--829.

Digital Library

[41]

Ravindra, G., Kumar, S., and Chintada, S. 2009. Distributed media transcoding using a p2p network of set top boxes. In Proceedings of the 6th IEEE Consumer Communications and Networking Conference.

Digital Library

[42]

Rubinstein, R. Y. and Kroese, D. P. 2004. The Cross-Entropy Method, A Unified Approach to Combinatorial Optimization, Monte-Carlo Simulation and Machine Learning. Springer.

Digital Library

[43]

Rubinstein, R. Y. and Melamed, B. 1998a. Efficient Simulation and Modeling. John Wiley & Sons.

[44]

Rubinstein, R. Y. and Melamed, B. 1998b. Modern Simulation and Modeling. Wiley-Interscience.

[45]

Rudin, W. 1976. Principles of Mathematical Analysis, 3rd Ed. McGraw-Hill.

[46]

Stoica, I., Morris, R., Liben-Nowell, D., Karger, D. R., Kaashoek, M. F., Dabek, F., and Balakrishnan, H. 2003. Chord: A scalable peer-to-peer lookup protocol for internet applications. IEEE/ACM Trans. Netw. 11, 1, 17--32.

Digital Library

[47]

Su, M. S., Thulasiraman, K., and Das, A. 2002. A scalable on-line multilevel distributed network fault detectioflonitoring system based on the snmp protocol. In Proceedings of the IEEE Global Telecommunications Conference. 1960--1964.

[48]

Wittner, O., Heegaard, P. E., and Helvik, B. E. 2003. Scalable distributed discovery of resource paths in telecommunication networks using cooperative ant-link agents. In Proceedings of the Congress on Evolutionary Computation. 1456--1465.

[49]

Yalagandula, P. and Dahlin, M. 2004. A scalable distributed information management system. In Proceedings of the Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications. 379--390.

Digital Library

[50]

Yao, X. and Xu, Y. 2006. Recent advances in evolutionary computation. Int. J. Comput. Sci. Techn. 21, 1, 1--18.

[51]

Zhang, H., Goel, A., and Govindan, R. 2004. Using the small-world model to improve Freenet performance. Comput. Netw. 46, 555--574.

Digital Library

[52]

Zlochin, M., Birattari, M., Meuleau, N., and Dorigo, M. 2004. Model-Based search for combinatorial optimization: A critical survey. Ann. Oper. Res. 131, 1-4, 373--395.

Cited By

Chen GSarrafzadeh APang S(2013)Service Provision Control in Federated Service Providing SystemsIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2012.15024:3(587-600)Online publication date: 1-Mar-2013
https://dl.acm.org/doi/10.1109/TPDS.2012.150
Chen GPang SSarrafzadeh ABan TInoue D(2012)SDE-Driven service provision controlProceedings of the 19th international conference on Neural Information Processing - Volume Part I10.1007/978-3-642-34475-6_32(260-268)Online publication date: 12-Nov-2012
https://dl.acm.org/doi/10.1007/978-3-642-34475-6_32

Recommendations

The MACODO organization model for context-driven dynamic agent organizations

Today's distributed applications such as sensor networks, mobile multimedia applications, and intelligent transportation systems pose huge engineering challenges. Such systems often comprise different components that interact with each other as peers, ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Autonomous and Adaptive Systems

ACM Transactions on Autonomous and Adaptive Systems Volume 5, Issue 4

November 2010

117 pages

ISSN:1556-4665

EISSN:1556-4703

DOI:10.1145/1867713

Issue’s Table of Contents

Copyright © 2010 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 19 November 2010

Accepted: 01 August 2010

Revised: 01 July 2010

Received: 01 July 2009

Published in TAAS Volume 5, Issue 4

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
402
Total Downloads

Downloads (Last 12 months)6
Downloads (Last 6 weeks)1

Reflects downloads up to 26 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Chen GSarrafzadeh APang S(2013)Service Provision Control in Federated Service Providing SystemsIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2012.15024:3(587-600)Online publication date: 1-Mar-2013
https://dl.acm.org/doi/10.1109/TPDS.2012.150
Chen GPang SSarrafzadeh ABan TInoue D(2012)SDE-Driven service provision controlProceedings of the 19th international conference on Neural Information Processing - Volume Part I10.1007/978-3-642-34475-6_32(260-268)Online publication date: 12-Nov-2012
https://dl.acm.org/doi/10.1007/978-3-642-34475-6_32

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents