Dovetailing (computer science)

From Wikipedia, the free encyclopedia

Dovetailing is a technique in algorithm design (such an algorithm is sometimes referred to as a dovetailer). It refers to interleaving different computations, performing them, in a sense, simultaneously.

To illustrate, consider performing a search in a tree in a breadth-first, rather than depth-first manner. This preference is useful when the tree potentially contains a path of infinite length - if a depth-first search (DFS) was used, part of the tree would potentially never be explored. Accordingly a breadth-first search (BFS) is used, which visits nodes according to their distance from the root. This avoids the problem caused by a depth-first search moving down an infinite path.

Now the BFS approach of visiting each child on the same level of the tree is like performing a single step for every program. The DFS approach is like running one program at a time, moving to the next only when it is fininished running (which may take an infinite amount of time).

In the case of an infinite number of programs, all potentially infinitely long, neither the BFS or DFS would be sufficient to ensure progress on all programs. Instead, the following technique can be used: perform the first step of the first program; next, perform the first step of the second program and the second step of the first program; next, perform the first step of the third program, the second step of the second program, and the third step of the first program, and so on.

Etymology: 1. The term might have come from card shuffling. 2. This technique is known as dovetailing in analogy with the interleaving ends of a dovetail joint in woodworking.