Text size
  • Small
  • Medium
  • Large
  • Standard
  • Blue text on blue
  • High contrast (Yellow text on black)
  • Blue text on beige

    Communication Traces in the Verification of Distributed Programs

    2nd BCS-FACS Northern Formal Methods Workshop

    Ilkley, UK. 14th - 15th July 1997


    N. Soundarajan


    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.


    PDF filePDF Version of this Paper (119kb)