Abstract

The scale-free graphs were proposed as a generic and universal model of network topologies that exhibit power-law distributions in the connectivity of network nodes. In recent years various complex networks were identified as having a scale-free structure. 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 nogood values during the search for a solution. In this article we analyze the distribution of nogood values to agents and the way how to use the information from the nogood; that is called the nogood processor technique. We examine the effect of nogood processor for networks that have a scale-free structure aiming to develop search algorithms specialized for scale-free networks of constraints, algorithms that require minimum costs for obtaining the solution. We develop a novel way for distributing nogood values to agents, thus obtaining a new hybrid search technique that uses the information from the stored nogoods. The experiments show that it is more effective for several families of asynchronous techniques; we perform tests with the model running on a cluster of computers. Also, we examine the effect of synchronization of agents' execution and of processing messages by packets in scale-free networks.

Keywords

MSC

68T42

Cite this article

@article{cai-2059,
  author  = {Ionel Muscalagiu and Horia Emil Popa and Viorel Negru},
  title   = {Improving the Performances of Asynchronous Search Algorithms in Scale-Free Networks Using the Nogood Processor Technique},
  journal = {Computing and Informatics},
  volume  = {34},
  number  = {1},
  pages   = {254--274},
  year    = {2015},
  issn    = {1335-9150},
  url     = {https://cai.type.sk/content/2015/1/improving-the-performances-of-asynchronous-search-algorithms-in-scale-free-networks-using-the-nogood-processor-technique/}
}
Download .bib