Message delay and Asynchronous DisCSP search

• Autorzy: Zivan R. , Meisels A.
• Języki publikacji: EN

Abstrakty

EN

Distributed constraint satisfaction problems (DisCSPs) are composed of agents, each holding its own variables, that are connected by constraints to variables of other agents. Due to the distributed nature of the problem, message delay can have unexpected effects on the behavior of distributed search algorithms on DisCSPs. This has been shown in experimental studies of asynchronous backtracking algorithms [1, 9]. To evaluate the impact of message delay on the run of DisCSP search algorithms, a model for distributed performance measures is presented. The model counts the number of non concurrent constraints checks, to arrive at a solution, as a non concurrent measure of distributed computation. A simpler version measures distributed computation cost by the number of non-concurrent steps of computation. An algorithm for computing these distributed measures of computational effort is described. The realization of the model for measuring performance of distributed search algorithms is a simulator which includes the cost of message delays. The performance of two asynchronous search algorithms is measured on randomly generated instances of DisCSPs with delayed messages. The Asynchronous Weak Commitment (AWC) algorithm and Asynchronous Backtracking (ABT). The intrinsic reordering process of AWC dictates a need for a more complex count of non-concurrent steps of computation. The improved counting algorithm is also needed for Dynamic ordered ABT. The delay of messages is found to have a strong negative effect on AWC and a smaller effect on dynamically ordered ABT.

Słowa kluczowe

EN

distributed constraint satisfaction; search; distributed AI

• Wydawca: Polish Academy of Sciences, Committee of Automatic Control and Robotics
• Czasopismo: Archives of Control Sciences
• Rocznik: 2006
• Tom: Vol. 16, no. 2
• Strony: 221--242
• Opis fizyczny: Bibliogr. 16 poz., rys.

Twórcy

autor

Zivan R.

autor

Meisels A.

• Department of Computer Science, Ben-Gurion University of the Negev, Beer-Sheva, 84-105, Israel,

Bibliografia

• [1] R. BEJAR, C. DOMSHLAK, C. FERNANDEZ, K. GOMES, B. KRISHNAMACHARI, B.SELMAN and M.VALLS: Sensor networks and distributed csp: communication, computation and complexity. Artificial Intelligence, 161(1-2), (2005), 117-148.
• [2] C. BESSIERE, A. MAESTRE, I. BRIT° and P. MESEGUER: Asynchronous backtracking without adding links: a new member in the abt family. Artificial Intelligence, 161( I -2), (2005), 7-24.
• [3] R. DECHTER: Constraints Processing. Morgan Kaufman, 2003.
• [4] L. LAMPORT: Time, clocks, and the ordering of events in distributed system. Communication of the ACM, 2, (1978), 95-114.
• [5] N. A. LYNCH: Distributed Algorithms. Morgan Kaufmann Series, 1997.
• [6] A. MEISELS, I. RAZGON, E. KAPLANSKY and R. ZIVAN: Comparing performance of distributed constraints processing algorithms. In Proc. AAMAS-2002 Workshop on. Distributed Constraint Reasoning DCR, Bologna, (2002), 86-93.
• [7] P. PROSSER: An empirical study of phase transitions in binary constraint satisfaction problems. Artificial Intelligence, 81 (1996), 81-109.
• [8] M. C. SILAGHI: Asynchronously Solving Problems with Privacy Requirements. PhD thesis, Swiss Federal Institute of Technology (EPFL), 2002.
• [9] M. C. SILAGHI and B. FALTINGS: Asynchronous aggregation and consistency in distributed constraint satisfaction. Artificial Intelligence, 161(1-2), 2, (2005), 5-54.
• [10] B. M. SMITH; Locating the phase transition in binary constraint satisfaction problems. Artificial Intelligence, 81 (1996), 155-181.
• [11] G. SOLOTOREVSKY, E. GUDES and A. MEISELS: Modeling and solving distributed constraint satisfaction problems (dcsps). In Constraint Processing-96,New Hamphshire, (1996) 561-2.
• [12] M. YOKOO: Asynchronous weak-commitment search for solving distributed constraint satisfaction problems. In Proc. 1st Int. Conf on Const. Prop:, Cassis, France, (1995), 88-102.
• [13] M. YOKOO: Algorithms for distributed constraint satisfaction problems: A review. Autonomous Agents & Multi-Agent Sys., 3 (2000), 198-212.
• [14] R. ZIVAN and A. MEISELS: Synchronous vs asynchronous search on discsps. In Proc. 1st European Workshop on Multi Agent System, EUMAS, Oxford, (2003).
• [15] R. ZIVAN and A. MEISELS: Concurrent dynamic backtracking for distributed csps. In CP-2004, Toronto, (2004), 782-7.
• [16] R. ZIVAN and A. MEISELS: Dynamic ordering for asynchronous backtracking on discsps. In CP-2005, Sigtes (Barcelona), (2005), 32-46.