Original discussion: tendermint/spec#371.

Summary

The issue here is the possibility that the application configures bad (e.g., very conservative) time bounds, resulting in a chain that will halt as proposals will be rejected by all or most of correct nodes. This situation is hard to deal because the synchronous parameters are consensus parameters, which require committing blocks to be updated. Which might become unfeasible if consensus cannot progress due to bad parameters.

There are two synchronous parameters considered by PBTS: PRECISION and MSGDELAY. PRECISION should not be a problem here, as it restricts malicious nodes from proposing timestamps in the future. The MSGDELAY parameter, in its turn, restricts malicious nodes from proposing timestamps "too much in the past". The diagram below can be helpful to understand the use of these parameters to validate proposed timestamps:

By setting a MSGDELAY parameter that is unrealistic (too low), a chain might end up in a situation in which correct validators reject proposals because their timestamps are deemed "too much in the past" because the observed propagation delay for proposals is larger than the configured MSGDELAY parameter.

Adaptive MSGDELAY

The general idea is that we should increase the MSGDELAY parameter adopted by PBTS when we fail to accept proposals in multiple rounds, which may indicate that the value chosen for this parameter was inadequate.

A possible analogy here is timeout_propose, the maximum expected delay for a proposed value (proposal and full block) to reach correct validators. Once a round fails on reaching a decision, the next round considers an increased delay timeout_propose(round - 1) + timeout_propose_delta, which is linearly increased until it represents the actual delay for delivering full proposals to correct validators. The same concept could be adopted for the MSGDELAY parameter.

The original issue several approaches for adaptive synchronous parameters for PBTS. They include a round from which adaptations start being adopted, how we adapt the values (linearly, exponentially) etc. The implemented version (this PR) adopted an exponential increasing of MSGDELAY when more than 10 rounds are needed to decide on a value.

Open questions

1. Do we need adaptive synchrony parameters?
2. If so, how and when we increase the value of MSGDELAY?
3. How we specify/document this approach, making it clear to external components which synchrony parameters were used to validate the timestamp of a given block

Definition of Done

• Mechanism to relax timely verification under certain circumstances is defined
• PBTS: Implement adaptive synchronous parameters for consensus #2432

Documentation:

• docs: document PBTS adaptive delays mechanism #2452
  • ADR 112 describes the implementation of this mechanism
  • PBTS runbook is updated accordingly
  • PBTS documentation is updated accordingly
• PBTS spec: spec: adaptive MSGDELAY parameter included in PBTS spec #2318