Network Model

[saltiniroberto]

The purpose of this issue to do discuss which network model to base the protocol design and analysis on. In the “Correctness Analysis of IBFT” and “Gray Paper” papers the "Eventually Synchronous Network Model" is assumed.

The following network models have been considered in the literature:

• Synchronous network: the maximum latency (time required for a message to reach the recipient) is bounded and known;

• Asynchronous network: the maximum latency is unknown and messages may never be delivered;

• Partially synchronous network: this model, which was first introduced by Dwork et al. (https://groups.csail.mit.edu/tds/papers/Lynch/jacm88.pdf) lies in between the other two. Specifically, there are two possible definitions of partial synchrony.

  • Eventual delivery: messages are guaranteed to be delivered but the maximum latency, while finite, is unknown. To be noted that the name of this network model, “Eventual delivery”, is not actually used in the literature, but it will be used in this issue and other issues in this repo to distinguish it from the “eventually synchronous network model”;
  • Eventually synchronous network: there exists a finite point in time, called global stabilisation time, or GST, after which the message delay is bounded by a finite and constant value. The network is assumed asynchronous before GST, hence messages can be lost (before GST);

The model with the weakest assumptions is the asynchronous network model, followed by the partially synchronous network model and the synchronous network model in this order. Between the two definitions of partial synchrony, eventual synchrony is the one with the weakest assumptions.

We believe that the eventually synchronous network model is the network model to be assumed for this BFT protocol for the following reasons:

• we cannot assume the network model with the weakest assumptions (the asynchronous network model) because no termination is deterministically guaranteed in such a network model as proved by Fisher et al. (https://groups.csail.mit.edu/tds/papers/Lynch/jacm85.pdf) There exist protocols that guarantee probabilistic liveness under asynchrony (e.g. Honey Badger), but, as far as I am aware, they require more communication phases for the best case scenario than protocols designed for the eventually synchronous network model and carry quite a lot of complexity as they require the implementation of a common coin sub-protocol
• we cannot assume that all the messages are eventually delivered (like in the eventual delivery network model) because the Ethereum gossip protocols simply forwards received messages to all other peers. It does not employee any technique/protocol (e.g. waiting for acknowledgment and re-transmitting) to ensure that the message is received at the other hand. Moreover, the underlying TCP only guarantees that the bytes received are identical and in the same order as they were transmitted. It does not guarantee that the data will be eventually received. For example, due to network malfunctioning (or an attacker controlling routers, see https://en.wikipedia.org/wiki/BGP_hijacking for this ) a TCP connection between two peers can drop (TCP terminates the connection if no ACK is received in a given time span). When a new TCP connection is established, the state of the old TCP connection is not transferred to the new one and therefore messages (bytes) that were supposed to be sent via the old TCP connection will never be sent via the new TCP connection and any other successive TCP connection.

The only network model that meets all of the constraints listed above is the eventually synchronous network model. To this effect we note that GPAv1 agrees that the "Eventually Synchronous Network Model" is an appropriate choice: “The definition of the eventually synchronous network applies to the blockchain model and appears to be accurate.” (see bottom of page 1 of GPAv1 feedback).

[drequinox]

Agreed, Eventual synchronous model is OK.

[kubasiemion]

Agreed to be closed