Abstract
DisCSPs are composed of agents that manage variables which are connected by constraints, various algorithms for solving DisCSPs are searching through this network of constraints. The scale-free graphs have been proposed as a generic and universal model of network topologies that exhibit power-law distributions in the connectivity of network nodes. Little research was done concerning the network structure for DisCSP and in particular for scale-free networks. The asynchronous searching techniques are characterized by the occurrence of the nogood values during the search for the solution. In this article we analyzed the distribution of nogood values to agents and the way to use the information stored in the nogood, what we will call the nogood processor technique. We examine the effect of nogood processor for networks that have a scale-free structure. We develop a novel way for the distribution of nogood values to agents, the experiments show that it is more effective for several families of asynchronous techniques.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Armstrong, A., Durfee, E.: Dynamic Prioritization of Complex Agents in Distributed Constraint Satisfaction Problems. In: Proceedings of the 15th IJCAI, Nagoya, Japan, pp. 620–625 (1997)
Barabasi, A.L., Albert, A.L.: Emergence of scaling in random networks. Science 286, 509–512 (1999)
Albert, R., Barabási, A.-L.: Statistical mechanics of complex networks. Rev. Mod. Phys. 74, 47–97 (2002)
Densmore, O.: An exploration of power-law networks (2009), http://backspaces.net/sun/PLaw/index.html
Hirayama, K., Yokoo: The Effect of Nogood Learning in Distributed Constraint Satisfaction. In: Proceedings of the 20th IEEE International Conference on Distributed Computing Systems (ICDCS 2000), pp. 169–177 (2000)
Meisels, A.: Distributed Search by Constrained Agents: algorithms, performance, communication, pp. 105–120. Springer, London (2008)
Muscalagiu, I., Jiang, H., Popa, H.E.: Implementation and evaluation model for the asynchronous techniques: from a synchronously distributed system to a asynchronous distributed system. In: Proceedings of the 8th SYNASC Conference, Timisoara, pp. 209–216 (2006)
Muscalagiu, I., Cretu, V.: Improving the Performances of Asynchronous Algorithms by Combining the Nogood Processors with the Nogood Learning Techniques. Journal ”INFORMATICA” 17(1) (2006)
Okimoto, T., Iwasaki, A., Yokoo, M.: Effect of DisCSP variable-ordering heuristics in scale-free networks. Multiagent and Grid Systems 8, 127–141 (2012)
Yokoo, M., Durfee, E.H., Ishida, T., Kuwabara, K.: The distributed constraint satisfaction problem: formalization and algorithms. IEEE Transactions on Knowledge and Data Engineering 10(5), 673–685 (1998)
Wilensky, U.: NetLogo itself:NetLogo. Center for Connected Learning and Computer-Based Modeling, Evanston (1999), http://ccl.northwestern.edu/netlogo/
MAS NetLogo Models-a, http://discsp-netlogo.fih.upt.ro/
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer International Publishing Switzerland
About this paper
Cite this paper
Muscalagiu, I., Popa, H.E., Negru, V. (2014). The Impact of the “Nogood Processor” Technique in Scale-Free Networks. In: Zavoral, F., Jung, J., Badica, C. (eds) Intelligent Distributed Computing VII. Studies in Computational Intelligence, vol 511. Springer, Cham. https://doi.org/10.1007/978-3-319-01571-2_20
Download citation
DOI: https://doi.org/10.1007/978-3-319-01571-2_20
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-01570-5
Online ISBN: 978-3-319-01571-2
eBook Packages: EngineeringEngineering (R0)