DIB—A Distributed Implementation of Backtracking

Raphael Finkel, Udi Manber

Research output: Contribution to journalArticlepeer-review

95 Scopus citations

Abstract

DIB is a general-purpose package that allows a wide range of applications such as recursive backtrack, branch and bound, and alpha-beta search to be implemented on a multicomputer. It is very easy to use. The application program needs to specify only the root of the recursion tree, the computation to be performed at each node, and how to generate children at each node. In addition, the application program may optionally specify how to synthesize values of tree nodes from their children's values and how to disseminate information (such as bounds) either globally or locally in the tree. DIB uses a distributed algorithm, transparent to the application programmer, that divides the problem into subproblems and dynamically allocates them to any number of (potentially nonhomogeneous) machines. This algorithm requires only minimal support from the distributed operating system. DIB can recover from failures of machines even if they are not detected. DIB currently runs on the Crystal multicomputer at the University of Wisconsin-Madison. Many applications have been implemented quite easily, including exhaustive traversal (N queens, knight's tour, negamax tree evaluation), branch and bound (traveling salesman) and alpha-beta search (the game of NIM). Speedup is excellent for exhaustive traversal and quite good for branch and bound.

Original languageEnglish
Pages (from-to)235-256
Number of pages22
JournalACM Transactions on Programming Languages and Systems (TOPLAS)
Volume9
Issue number2
DOIs
StatePublished - Mar 20 1987

Keywords

  • Backtracking
  • branch and bound
  • distributed algorithms
  • localarea networks
  • networks of workstations

ASJC Scopus subject areas

  • Software

Fingerprint

Dive into the research topics of 'DIB—A Distributed Implementation of Backtracking'. Together they form a unique fingerprint.

Cite this