Title :
A distributed implementation of the branch and bound search
Author :
Young, Eric ; Li, Kin F.
Author_Institution :
Dept. of Electr. & Comput. Eng., Victoria Univ., BC, Canada
Abstract :
A local area network of cooperating sites is ideal for the type of problems that can be decomposed in such a way that individual tasks do not require up-to-date global information and their individual solutions will still converge. Using replicated postboards as the communication structure to house sometimes inconsistent information, a distributed implementation of the branch and bound search was studied. The behavior and the efficiency of both the algorithm and the system are analyzed. In addition, two categories of distributed anomalies are identified as a result of the inconsistent information; the stale anomaly and the duplication anomaly. It is concluded that if means are devised to deal with these anomalies, reasonable performance can be obtained
Keywords :
distributed processing; local area networks; search problems; LAN; algorithm; branch and bound search; communication structure; distributed anomalies; distributed testbed; duplication anomaly; inconsistent information; local area network; performance; replicated postboards; stale anomaly; workstations; Algorithm design and analysis; Communication system control; Control systems; Costs; Distributed computing; Power engineering computing; Power system interconnection; Random access memory; Testing; Workstations;
Conference_Titel :
Communications, Computers and Signal Processing, 1991., IEEE Pacific Rim Conference on
Conference_Location :
Victoria, BC
Print_ISBN :
0-87942-638-1
DOI :
10.1109/PACRIM.1991.160692
