In this paper, we present a catalog of application interaction patterns with the corresponding message ordering and execution rules for Byzantine fault tolerance computing. For each pattern, a set of rules are defined to determine whether or not an inbound message should be ordered and in what particular order, and which set of messages should be delivered sequentially, concurrently, or selectively concurrently under various scenarios. This catalog could serve as the design patterns for constructing practical Byzantine fault tolerance applications that may use much more sophisticated system models than the basic client-server state machine model. The set of patterns will make it easier and less error-prone when applying the Byzantine fault tolerance techniques for practical systems, in particular, Web based applications.