Introduction
In a standard distributed computing environment, the presence of message-delaying attackers (Communication delays or failures) introduces communication uncertainty. Three communication models are broadly defined for the distributed systems consensus problem.
Synchronous Communication model
The synchronous model defines a known finite time range ⊿ for message delivery, and an attacker can only cause a delay of at most ⊿ in the delivery of a message. In other words, when a sender sends a message, it is guaranteed to be received by the other party within a certain time ⊿. This ⊿ is known to all participants.
In real systems, this synchronization model is impractical. The reason for this is that there is known to be no upper bound on delays and temporary failures.
Asynchronous Communication model
In the asynchronous model, only final delivery is guaranteed for message delivery, and an attacker can delay message delivery for any finite amount of time.
This asynchronous model does not allow for any assumptions to be made in the consensus algorithm. Some consensus algorithms are available for the asynchronous model, but they have very strict restrictions.
Partial synchronous communication model
The partial synchronous model lies between the synchronous and asynchronous models. In addition to the known finite time range ⊿, there is an event called GST (global stabilization time). In the partial synchronous model, a message sent at time t will be stabilized at time max(x,GST)+⊿. In other words, the system operates in the asynchronous model up to GST and in the synchronous model after GST. The GST event must occur after an unknown finite time for the attack.
In other words, this partial synchronization model behaves the same as the synchronization model in most cases. However, sometimes network delays, temporary failures, or clock errors mean that the upper bound is exceeded. We do not know how long the network will wait if network delays, temporary failures, or clock errors occur (equal to the asynchronous model).
Top comments (4)
Do you plan to explain the relationship between the fault detector and these communication model?
Thank you for your comment and follow up.
I had not planned to write an article on fault detectors.
However, it is interesting and closely related to this topic, so I thought I would write about it.
I will probably finish it within a month, so please follow me until then!
Awesome! A combination of these three abstractions, process, link, and fault detector, models an entire distributed system and is useful to classify distributed consensus algorithms. For example, Paxos is a well-known consensus algorithm for the fail-noisy class (= crash-stop process + perfect link + eventually perfect failure detector). I recommend this book for details: link.springer.com/book/10.1007/978...
Updated.