Communication analysis of distributed programs

Article type: Research Article

Authors: Simmons, Sharon | Edwards, Dennis | Kearns, Phil

Affiliations: Department of Computer Science, University of West Florida, 11000 University Parkway, Pensacola, FL 32503, USA | Department of Computer Science, The College of William & Mary, Post Office Box 8795, Williamsburg, VA 23185, USA

Note: [] Corresponding author: Sharon Simmons, Tel.: +1 850/473 7349; Fax: +1 850/857 6056; E-mail: ssimmons@cs.uwf.edu

Abstract: Capturing and examining the causal and concurrent relationships of a distributed system is essential to a wide range of distributed systems applications. Many approaches to gathering this information rely on trace files of executions. The information obtained through tracing is limited to those executions observed. We present a methodology that analyzes the source code of the distributed system. Our analysis considers each process's source code and produces a single comprehensive graph of the system's possible behaviors. The graph, termed the partial order graph (POG), uniquely represents each possible partial order of the system. Causal and concurrent relationships can be extracted relative either to a particular partial order, which is synonymous to a single execution, or to a collection of partial orders. The graph provides a means of reasoning about the system in terms of relationships that will definitely occur, may possible occur, and will never occur. Distributed assert statements provide a means to monitor distributed system executions. By constructing the POG prior to system execution, the causality information provided by the POG enables run-time evaluation of the assert statement without relying on traces or addition messages.

Journal: Scientific Programming, vol. 14, no. 2, pp. 151-170, 2006