A termination detection algorithm for a general model of distributed 
computations where processes communicate over asynchronous non-FIFO channels 
is presented. It has O(mn) message complexity if the control network is a 
ring, a (spanning) tree, or a general undirected graph and O(m) message 
complexity on star networks and complete networks. Several variants of the 
basic principle are discussed, one of which is a symmetric version where any 
process can start the algorithm independently from the other processes. 
Preliminary experimental results show that far less control messages than 
indicated by the worst case behavior are usually generated. In a distributed 
puzzle-solving system used as a test application only about sqrt(m) control 
messages have been counted. The constraint based puzzle-solving method is 
explained and several test cases are reported.