Synchronous model: is taking steps simultaneously equivalent to having fixed upper bounds for communication/processing delays?

Question

I've just started reading about theory of distributed systems and am a bit confused. There seem to be two ways of defining a synchronous distributed system and I'm not sure whether they are equivalent.

Lynch, in her book Distributed Algorithms (p. 5) writes

The synchronous model: This is the simplest model to describe, to program, and to reason about. We assume that components take steps simultaneously, that is, that execution proceeds in synchronous rounds.

Several other sources, in contrast, define the synchronous model in terms of known upper bounds for computation and communication delays. For instance, Cachin et al. in their book Introduction to Reliable and Secure Distributed Programming (pp. 45-46) write

[...] a synchronous system comes down to assuming the following properties:

Synchronous computation. There is a known upper bound on processing delays. That is, the time taken by any process to execute a step is always less than this bound. [...]

Synchronous communication. There is a known upper bound on message transmission delays. That is, the time period between the instant at which a message is sent and the instant at which the message is delivered by the destination process is smaller than this bound.

Even Lynch herself, in a paper she cowrote with Dwork and Stockmeyer (Consensus in the Presence of Partial Synchrony) also uses a definition similar to the one by Cachin et al.:

[...] it might be assumed that there is a fixed upper bound $\Delta$ on the time for messages to be delivered (communication is synchronous) and a fixed upper bound $\Phi$ on the rate at which one processor’s clock can run faster than another’s (processors are synchronous), and that these bounds are known a priori and can be "built into" the protocol.

Are these synchronous models equivalent? For instance, is an impossibility result in one also an impossibility result in the other, and vice versa? And is the minimum number of nodes necessary to tolerate a given failure (e.g., byzantine or crash) the same, whether we define synchronous to mean that processes proceed in synchronized steps or whether we define it as meaning that transmission and computation delays are upper bounded and known?

Answer 1

All of these are, generally speaking, called "synchronous models", they are pretty similar to each other, and especially in the context of fault-tolerant algorithms they are very different from "asynchronous models".

However, please note that there is no such thing as the synchronous model. Even if you define a message-passing model in which all nodes execution proceeds in synchronous rounds and all nodes start simultaneously, this does not yet completely define the model of computing. To have a well-defined model of distributed computing, you will need to specify, e.g., the following aspects:

• assumptions on the underlying network topology (complete network? path? cycle? grid? bounded-degree graph? arbitrary graph?)
• what kind of local information the nodes have in the beginning (unique identifiers? an upper bound on the network size?)
• what is the communication model (maximum message size? can you send different messages to each neighbour in the same round or are you limited to e.g. broadcast operations? can you receive messages from different neighbours in the same round or do you have collisions? how can you address your neighbours?)
• what kind of computers you have as your nodes (finite state machines? Turing machines? arbitrary functions? any limitations on time or space used per round? any limitations on space used between rounds? can you use randomness?).

These aspects can be much more important than the specific definitions of "synchrony", especially if you are interested in computability.

But let us put these issues aside, let us assume we have already precisely defined some synchronous model of computing (and let us also assume that it is a fairly strong model, e.g., we have unique identifiers and unlimited local computation). Let us now try to see whether the precise definition of "synchrony" would make any difference.

If you only care about computability, the precise definition of "synchrony" is not important. Also, if you are only interested in the number of communication rounds needed to solve a problem (and you define a "communication round" appropriately so that it makes sense also in the bounded-delay model), the models are also equivalent up to constant factors. In essence, you can simply use the alpha synchroniser: all nodes count rounds from 1, all messages include round counters, and each node proceeds to round $i+1$ once it has received all messages from round $i$ (and you use timeouts to detect nodes that have crashed).

Things get more complicated if you also care about e.g. the total number of bits that you need to transmit. In essence, in the "strict" synchronous model you can easily use silence to send information (e.g., be silent for $x$ rounds and then send a 1-bit message ≈ send number $x$). Here is a simple example of a problem that can be solved this way:

• the underlying graph is a path and all nodes need to determine how far they are from the nearest endpoint.

If all nodes start simultaneously and computation proceeds in synchronous rounds, it is sufficient to propagate a 1-bit token from the endpoints towards the middle. All nodes can locally count how many rounds it takes before they receive the token. In total, in a path of length $n$, you will send approximately $n$ messages, each of them containing just one bit.

However, if you have bounded delays, it gets pretty tricky to solve this problem with $O(n)$ 1-bit messages. You can still use periods of silence to send information, but you will need to waste a lot of time to do that (a naive solution has an exponential time complexity).