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 sys...