Repeatable and portable message-passing programs

Abstract

A fundamental issue in the use of message-passing systems is the creation of repeatable and portable programs. Repeatable program behavior is critical for debugging message-passing programs, while portability is essential for efficient software development. This paper makes two main contributions. First, it defines a set of program executions (called safe executions) that are guaranteed to be repeatable and portable. Safe program executions are defined for applications that utilize both blocking and nonblocking send and receive primitives, synchronous and asynchronous sends, and receives that select on the basis of source and/or tag values. To the best of our knowledge, this is the first time that conditions for repeatable and portable executions have been created for such rich message-passing models. Second, this paper gives precise characterizations of safe executions. The safety of an execution is shown to depend on the message-ordering properties of the underlying communication system, and two different message-ordering properties are examined in detail. In addition to providing insight into safe executions, these characterizations lead to polynomial time algorithms that determine whether or not an execution is safe. In the near future, we plan to use these results to create software that will automatically determine the safety of an execution from a trace of its communication events, thus greatly aiding the development of portable applications.