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

fYear

1991

fDate

9-10 May 1991

Firstpage

103

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;

fLanguage

English

Publisher

ieee

Conference_Titel

Communications, Computers and Signal Processing, 1991., IEEE Pacific Rim Conference on

Conference_Location

Victoria, BC

Print_ISBN

0-87942-638-1

Type

conf

DOI

10.1109/PACRIM.1991.160692

Filename

160692