R. F. DeMara, Y. Tseng, and A. Ejnioui, 
" Tiered Algorithm for Distributed Process Termination Detection," submitted to 
IEEE Transactions on Parallel and Distributed Systems on September 28, 2004 and 
available as UCF Technical Report UCF-ECE-0402 online at 
http://netmoc.cpe.ucf.edu:8080/internal/yearReportsDetail.jsp?year=2004&id=0402 

Abstract:
This paper presents the Tiered Algorithm for time-efficient and message-
efficient detection of process termination in distributed environments. It 
relies on process production and consumption invariants that are preserved 
regardless of execution interleaving order and/or potential race conditions due 
to unpredictable network transit times. In particular, the use of a global 
invariant that indicates equality between process production and consumption at 
each level of process nesting is shown to correctly detect termination for a 
broad range of scenarios. By considering each level of process nesting, the 
Tiered Algorithm reduces execution overhead at participating nodes while 
exchanging relatively few synchronization messages. The Tiered Algorithm is 
validated by developing an inductive proof of correctness for arbitrary process 
spawning hierarchies. Correctness is also demonstrated in the presence of 
launch-in-transit hazards whereby processes are created dynamically based on 
run-time conditions and executed remotely. The performance of the Tiered 
Algorithm is compared to three existing detection termination schemes with 
comparable capabilities, namely the CV, LTD, and Credit Algorithms. For 
synchronization of T tasks terminating in E epochs of idle processing, the 
Tiered Algorithm is shown to have O(E) message count complexity and O(T lg T) 
message bit complexity while incurring detection latency corresponding to only 
integer addition and comparison operations.