PineWikiSee AttiyaWelch Chapter 2 for details. We'll just give the basic overview here. See also AsynchronousMessagePassing and SynchronousMessagePassing for some older notes based on the I/O automaton model used in LynchBook.
1. Basic message-passing model
We have a collection of n processes p1...p2, each of which has a state consisting of a state from from state set Qi, together with an inbuf and outbuf component representing messages available for delivery and messages posted to be sent, respectively. Messages are point-to-point, with a single sender and recipient: if you want broadcast, you have to pay for it. A configuration of the system consists of a vector of states, one for each process. The configuration of the system is updated by an event, which is either a delivery event (a message is moved from some process's outbuf to the appropriate process's inbuf) or a computation event (some process updates its state based on the current value of its inbuf and state components, possibly adding new messages to its outbuf). An execution segment is a sequence of alternating configurations and events C0,φ1,C1,φ2,..., in which each triple Ciφi+1Ci+1 is consistent with the transition rules for the event φi+1 (see AttiyaWelch for more details on this) and the last element of the sequence (if any) is a configuration. If the first configuration C0 is an initial configuration of the system, we have an execution. A schedule is an execution with the configurations removed.
1.1. Network structure
It may be the case that not all processes can communicate directly; if so, we impose a network structure in the form of a directed graph, where i can send a message to j only if there is an edge from i to j in the graph. Typically we assume that each process knows the identity of all its neighbors.
For some problems (e.g., in peer-to-peer systems or other overlay networks) it may be natural to assume that there is a fully-connected underlying network but that we have a dynamic network on top of it, where processes can only send to other processes that they have obtained the addresses of in some way.
2. Asynchronous model
In an asynchronous model, only minimal restrictions are placed on when messages are delivered and when local computation occurs. A schedule is said to be admissible if (a) there are infinitely many computation steps for each process, and (b) every message is eventually delivered. The first condition (a) assumes that processes do not explicitly terminate, which is the assumption used in AttiyaWelch; an alternative, which we will use when convenient, is to assume that every process either has infinitely many computation steps or reaches an explicit halting state.
2.1. Time complexity
There is no explicit notion of time in the asynchronous model, but we can define a time measure by adopting the rule that every message is delivered and processed at most 1 time unit after it is sent. Formally, we assign time 0 to the first event, and assign the largest time we can to each subsequent event, subject to the rule that if a message m from i to j is created at time t, then the time for the delivery of m from i to j and the time for the following computation step of j are both no greater than j+1. This is consistent with an assumption that message propagation takes at most 1 time unit and that local computation takes 0 time units. Another way to look at this is that it is a definition of a time unit in terms of maximum message delay together with an assumption that message delays dominate the cost of the computation. This last assumption is pretty much always true for real-world networks with any non-trivial physical separation between components, thanks to speed of light limitations.
The time complexity of a protocol (that terminates) is the time of the last event before all processes finish.
2.2. Message complexity
For a protocol that terminates, the message complexity is the total number of messages sent. We can also look at message length in bits, total bits sent, etc., if these are useful for distinguishing our new improved protocol from last year's model.
3. Synchronous systems
A synchronous message-passing system is exactly like an asynchronous system, except we insist that the schedule consists of alternating phases in which (a) every process executes a computation step, and (b) all messages are delivered. The combination of a computation phase and a delivery phase is called a round. Synchronous systems are effectively those in which all processes execute in lock-step, and there is no timing uncertainty. This makes protocols much easier to design, but makes them less resistant to real-world timing oddities. Sometimes this can be dealt with by applying a synchronizer, which transforms synchronous protocols into asynchronous protocols at a small cost in complexity.