Improving the Performances of Asynchronous Search Algorithms in Scale-Free Networks Using the Nogood Processor Technique

Authors

  • Ionel Muscalagiu The "Politehnica" University of Timisoara, The Faculty of Engineering of Hunedoara
  • Horia Emil Popa West University of Timișoara, The Faculty of Mathematics and Informatics
  • Viorel Negru West University of Timișoara, The Faculty of Mathematics and Informatics

Keywords:

Agents, distributed constraint programming, asynchronous search break techniques, scale-free networks, nogood messages

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.

Downloads

Download data is not yet available.

Downloads

Published

2015-06-19

How to Cite

Muscalagiu, I., Popa, H. E., & Negru, V. (2015). Improving the Performances of Asynchronous Search Algorithms in Scale-Free Networks Using the Nogood Processor Technique. COMPUTING AND INFORMATICS, 34(1), 254–274. Retrieved from https://www.cai.sk/ojs/index.php/cai/article/view/2059

Issue

Section

Special Section Articles