Communication Traces in the Verification of Distributed Programs

Two types of communication traces, channel traces and process traces, have been used in the literature in dealing with distributed programs. Specifications and proofs in channel-trace systems are usually considered to be simpler than in systems based on process traces. But channel traces do not contain information about the relative order of communication along different channels of a process which can lead to incompleteness of the channel-trace based axiom systems. Several attempts have been made to overcome the incompleteness by adding new axioms to these systems. We show with simple examples that these axioms do not by themselves solve the incompleteness problem. Effectively, process traces or some equivalent thereof is necessary to achieve completeness. We also consider the possibility of adding new communications to the processes to include more information in the channel traces.