DocumentCode
2646423
Title
A distributed algorithm solving CSPs with a low communication cost
Author
Prcovic, N.
Author_Institution
CERMICS-INRIA, Sophia Antipolis, France
fYear
1996
fDate
16-19 Nov. 1996
Firstpage
454
Lastpage
455
Abstract
We present a distributed algorithm which finds all solutions of constraint satisfaction problems. Based on the backtrack algorithm, it spreads subtrees of the search tree over processes running in parallel. The work is equitably shared among the processes while the communication cost remains low. We show that the speedup of the resolution is asymptotically linear as the number of variables increases.
Keywords
communication complexity; constraint handling; distributed algorithms; tree searching; CSPs; backtrack algorithm; communication cost; constraint satisfaction problems; distributed algorithm; low communication cost; parallel processes; search tree; subtrees; Computer networks; Costs; Distributed algorithms; Distributed computing; Load management; Parallel processing; Tree data structures;
fLanguage
English
Publisher
ieee
Conference_Titel
Tools with Artificial Intelligence, 1996., Proceedings Eighth IEEE International Conference on
Conference_Location
Toulouse, France
ISSN
1082-3409
Print_ISBN
0-8186-7686-7
Type
conf
DOI
10.1109/TAI.1996.560781
Filename
560781
Link To Document