本記事はdev.toから移植しました．

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