research-article

Host selection through collective decision

Authors:

Fabrice Saffre,

Aistis SimaitisAuthors Info & Claims

ACM Transactions on Autonomous and Adaptive Systems (TAAS), Volume 7, Issue 1

Article No.: 4, Pages 1 - 16

https://doi.org/10.1145/2168260.2168264

Published: 04 May 2012 Publication History

Abstract

In this article, we present a collective decision-making framework inspired by biological swarms and capable of supporting the emergence of a consensus within a population of agents in the absence of environment-mediated communication (stigmergy). Instead, amplification is the result of the variation of a confidence index, stored in individual memory and providing each agent with a statistical estimate of the current popularity of its preferred choice within the whole population. We explore the fundamental properties of our framework using a combination of analytical and numerical methods. We then use Monte Carlo simulation to investigate its applicability to host selection in the presence of multiple alternatives, a problem found in application migration scenarios. The advantages of self-organization and the use of statistically predictive methods in this context are also discussed.

References

[1]

Ame, J., Halloy, J., Rivault, C., Detrain, C., and Denebourg, J. 2006. Collegial decision making based on social amplification leads to optimal group formation. Proc. Nat. Acad. Sci. USA 103, 5835--5840.

[2]

Ardagna, D., Trubian, M., and Zhang, L. 2007. Sla based resource allocation policies in autonomic environments. J. Paral. Distrib. Comput. 67, 259--270.

Digital Library

[3]

Beckers, R., Deneubourg, J., Goss, S., and Pasteels, J. 1990. Collective decision making through food recruitment. Insectes Sociaux 37, 258--267.

[4]

Bergerud, A. 2000. Ecology and Management of Large Mammals in North America. Prentice Hall, Upper Saddle River, New Jersey, Chapter Caribou.

[5]

Bonabeau, E., Theraulaz, G., Denebourg, J., Aron, S., and Camazine, S. 1997. Self-Organization in social insects. Trends Ecol. Evolut. 12, 188--193.

[6]

Chow, K. and Kwok, Y. 2002. On load balancing for distributed multi-agent computing. IEEE Trans. Paral. Distrib. Syst. 13, 787--801.

Digital Library

[7]

Conradt, L. and Roper, T. 2005. Consensus decision making in animals. Trends Ecol. Evolut. 20, 449--456.

[8]

Couzin, I., Krause, J., Franks, N., and Levin, S. 2005. Effective leadership and decision-making in animal groups on the move. Nature 433, 513--516.

[9]

Csorba, M., Meling, H., Heegaard, P., and P., H. 2009. Foraging for Better Deployment of Replicated Service Components. Lecture Notes in Computer Science, vol. 5523, Springer.

Digital Library

[10]

Dorigo, M. and Stuetzle, T. 2004. Ant Colony Optimization. MIT Press, Cambridge, MA.

Digital Library

[11]

Dyer, F. and T. D., S. 1994. Colony migration in the tropical honey beeapis dorsata f. (hymenoptera: Apidae). Insectes Sociaux 41, 129--140.

[12]

Fischer, M. J., Lynch, N. A., and Paterson, M. S. 1985. Impossibility of distributed consensus with one faulty process. J. ACM 32, 2, 374--382.

Digital Library

[13]

Fu, C. and Xu, C. 2005. Service migration in distributed virtual machines for adaptive grid computing. In Proceedings of the International Conference on Parallel Processing. IEEE Computer Society, 358--365.

Digital Library

[14]

Gueron, S. and Levin, S. 1993. Self-Organization of front patterns in large wildebeest herds. J. Theor. Biol. 165, 541--552.

[15]

Gupta, S. and Srimani, P. 2003. Adaptive core selection and migration method for multicast routing in mobile ad hoc networks. IEEE Trans. Paral. Distrib. Syst. 14, 27--38.

Digital Library

[16]

Handl, J. and Meyer, B. 2002. Improved ant-based clustering and sorting in a document retrieval interface. In Proceedings of Parallel Problem Solving from Nature. Vol. 7.

Digital Library

[17]

Heimfarth, T. and Janacik, P. 2006. Ant based heuristic for os service distribution on ad-hoc networks. Biol. Inspired Coop. Comput. 75--84.

[18]

Heusse, M., Guerin, S., Snyers, D., and Kuntz, P. 1998. Adaptive agent-driven routing and load balancing in communication networks. Adv. Complex Syst. 1, 234--257.

[19]

Holdo, R., Holt, R., and Fryxell, J. 2009. Opposing rainfall and plant nutritional gradients best explain the wildebeest migration in the serengeti. Amer. Natural. 173, 431--445.

[20]

Kennedy, J., Eberhart, R., and Shi, Y. 2001. Swarm Intelligence. Morgan Kaufmann, San Francisco.

Digital Library

[21]

Koshi, K., Hiltunen, M., and Jung, G. 2009. Performance aware regeneration in virtualized multitier applications. In Proceedings of the DSN09 Workshop on Proactive Failure Avoidance, Recovery and Maintenance (PFARM). IEEE Computer Society.

[22]

Lindauer, M. 1951. Bienentänze in der schwarmtraube. Naturwissenschaften 38, 509--513.

[23]

Lindauer, M. 1953. Bienentänze in der schwarmtraube ii. Naturwissenschaften 40, 379--385.

[24]

Lindauer, M. 1955. Schwarmbienen auf wohnungssuche. Zeitschrift Fuer Vergleichende Physiologie 37, 263--324.

[25]

Mallon, E., Pratt, S., and Franks, N. 2001. Individual and collective decision-making during nest selection by the ant leptothorax albipennis. Behav. Ecol. Sociobiol. 50, 352--359.

[26]

Messig, M. and Goscinski, A. 2007. Autonomic system management in mobile grid environments. In Proceedings of the 5th Australasian Symposium on Grid Computing and e-Research. Vol. 68. 49--58.

Digital Library

[27]

Montresor, A., Meling, H., and Babaoglu, O. 2002. Messor: Load-balancing through a swarm of autonomous agents. In Agents and Peer-to-Peer Computing, 125--137.

Digital Library

[28]

Musunoori, S. B. and Horn, G. 2007. Application service placement in stochastic grid environments using learning and ant-based methods. Multiagent Grid Syst. 3, 1, 19--41.

Digital Library

[29]

Parker, C. A. and Zhang, H. 2009. Cooperative decision-making in decentralized multiple-robot systems: the best-of-n problem. IEEE/ASME Trans. Mechatron. 14, 2, 240--251.

[30]

Pease, M., Shostak, R., and Lamport, L. 1980. Reaching agreement in the presence of faults. J. ACM 27, 2, 228--234.

Digital Library

[31]

Peysakhov, M., Dugan, C., Jodi, P. J., and Regli, W. 2006. Quorum sensing on mobile ad-hoc networks. In Proceedings of the 5th International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS'06). 1104--1106.

Digital Library

[32]

Pratt, S. C., Sumpter, D. J., Mallon, E. B., and Franks, N. R. 2005. An agent-based model of collective nest choice by the ant temnothorax albipennis. Animal Behav. 70, 5, 1023--1036.

[33]

Saffre, F., Mailleux, A., and Deneubourg, J. L. 2000. Exploratory recruitment plasticity in a social spider (anelosimus eximius). J. Theor. Biol. 205, 37--46.

[34]

Saffre, F., Tateson, R., Halloy, J., Shackleton, M., and Deneubourg, J. L. 2009. Aggregation dynamics in overlay networks and their implications for self-organised distributed applications. Comput. J. 52, 4, 397--412.

Digital Library

[35]

Schaerf, A., Shoham, Y., and Tennenholtz, M. 1995. Adaptive load balancing: A study in multi-agent learning. J. Artif. Intell. Res. 2, 475--500.

[36]

Seeley, T. 2003. Consensus building during nest-site selection in honey bee swarms: The expiration of dissent. Behav. Ecol. Sociobiol. 53, 417--424.

[37]

Seeley, T. and Buhrman, C. 1999. Group decision making in swarms of honey bees. Behav. Ecol. Sociobiol. 45, 19--31.

[38]

Seeley, T., Camazine, S., and Sneyd, J. 1991. Collective decision-making in honey bees: How colonies choose among nectar sources. Behav. Ecol. Sociobiol. 28, 227--290.

[39]

Seeley, T. and Morse, R. 1978. Nest site selection by the honey bee apis mellifera. Insectes Sociaux 25, 323--337.

[40]

Seeley, T. and Visscher, P. 2004. Group decision making in nest-site selection by honey bees. Apidologie 35, 101--116.

[41]

Shen, K., Tang, H., and Yang, T. 2002. A flexible qos framework for cluster-based network services. In Proceedings of the USENIX Annual Technical Conference.

[42]

Sumpter, D. and Pratt, S. 2009. Quorum responses and consensus decision making. Philosoph. Trans. Roy. Soc. B 364, 743--753.

[43]

Wolf, J. and Yu, P. 2001. On balancing the load in a clustered web farm. ACM Trans. Internet Technol. 1, 231--261.

Digital Library

Cited By

Eisentraut JKelmendi EKřetínský JWeininger M(2022)Value iteration for simple stochastic gamesInformation and Computation10.1016/j.ic.2022.104886285:PBOnline publication date: 1-May-2022
https://dl.acm.org/doi/10.1016/j.ic.2022.104886
Hildmann HEledlebi KSaffre FIsakovic A(2021)The Swarm Is More Than the Sum of Its DronesDevelopment and Future of Internet of Drones (IoD): Insights, Trends and Road Ahead10.1007/978-3-030-63339-4_1(1-55)Online publication date: 16-Feb-2021
https://doi.org/10.1007/978-3-030-63339-4_1
Ashok PKřetínský JWeininger M(2019)PAC Statistical Model Checking for Markov Decision Processes and Stochastic GamesComputer Aided Verification10.1007/978-3-030-25540-4_29(497-519)Online publication date: 12-Jul-2019
https://doi.org/10.1007/978-3-030-25540-4_29
Show More Cited By

Index Terms

Host selection through collective decision
1. Computing methodologies
  1. Artificial intelligence
    1. Distributed artificial intelligence
      1. Multi-agent systems

Recommendations

Collective decision with 100 Kilobots: speed versus accuracy in binary discrimination problems

Achieving fast and accurate collective decisions with a large number of simple agents without relying on a central planning unit or on global communication is essential for developing complex collective behaviors. In this paper, we investigate the speed ...
Coalitions of malicious intelligent agents

In this paper, we propose a model of pro-social and antisocial behaviour within and between agent coalitions. We analyse benevolent, selfish, and malevolent agents as generic types of pro-social and antisocial agents. We show that social attitudes must ...
Concepts, challenges, and prospects on Multiagent Data Warehousing (MADWH) and Multiagent Data Mining (MADM)

Multiagent Data Warehousing (MADWH) and Multiagent Data Mining (MADM) presents a multidimensional agent-oriented approach for brain modelling and decision making based on the hypothesis that a brain system consists of a society of semiautonomous neural ...

Comments

Information & Contributors

Information

Published In

cover image ACM Transactions on Autonomous and Adaptive Systems

ACM Transactions on Autonomous and Adaptive Systems Volume 7, Issue 1

Special section on formal methods in pervasive computing, pervasive adaptation, and self-adaptive systems: Models and algorithms

April 2012

365 pages

ISSN:1556-4665

EISSN:1556-4703

DOI:10.1145/2168260

Issue’s Table of Contents

Copyright © 2012 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: 04 May 2012

Accepted: 01 June 2011

Revised: 01 July 2010

Received: 01 October 2009

Published in TAAS Volume 7, Issue 1

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

Mark Shackleton and Mike Fisher
BI Innovate and Design

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

7
Total Citations
View Citations
321
Total Downloads

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

Reflects downloads up to 05 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Eisentraut JKelmendi EKřetínský JWeininger M(2022)Value iteration for simple stochastic gamesInformation and Computation10.1016/j.ic.2022.104886285:PBOnline publication date: 1-May-2022
https://dl.acm.org/doi/10.1016/j.ic.2022.104886
Hildmann HEledlebi KSaffre FIsakovic A(2021)The Swarm Is More Than the Sum of Its DronesDevelopment and Future of Internet of Drones (IoD): Insights, Trends and Road Ahead10.1007/978-3-030-63339-4_1(1-55)Online publication date: 16-Feb-2021
https://doi.org/10.1007/978-3-030-63339-4_1
Ashok PKřetínský JWeininger M(2019)PAC Statistical Model Checking for Markov Decision Processes and Stochastic GamesComputer Aided Verification10.1007/978-3-030-25540-4_29(497-519)Online publication date: 12-Jul-2019
https://doi.org/10.1007/978-3-030-25540-4_29
Wu BZhou XJin QLin FLeung H(2017)Analyzing Social Roles Based on a Hierarchical Model and Data Mining for Collective Decision-Making SupportIEEE Systems Journal10.1109/JSYST.2014.238661111:1(356-365)Online publication date: Mar-2017
https://doi.org/10.1109/JSYST.2014.2386611
Saffre FHildmann HDeneubourg J(2017)Can individual heterogeneity influence self-organised patterns in the termite nest construction model?Swarm Intelligence10.1007/s11721-017-0143-812:2(101-110)Online publication date: 28-Oct-2017
https://doi.org/10.1007/s11721-017-0143-8
Chen TForejt VKwiatkowska MParker DSimaitis A(2013)Automatic verification of competitive stochastic systemsFormal Methods in System Design10.1007/s10703-013-0183-743:1(61-92)Online publication date: 16-Feb-2013
https://doi.org/10.1007/s10703-013-0183-7
Chen TForejt VKwiatkowska MParker DSimaitis A(2012)Automatic verification of competitive stochastic systemsProceedings of the 18th international conference on Tools and Algorithms for the Construction and Analysis of Systems10.1007/978-3-642-28756-5_22(315-330)Online publication date: 24-Mar-2012
https://dl.acm.org/doi/10.1007/978-3-642-28756-5_22

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.

Figures

Tables

Media

View Issue’s Table of Contents