cometbft · cason · Feb 20, 2024 · Feb 12, 2024 · Feb 12, 2024 · Feb 12, 2024
diff --git a/spec/consensus/proposer-based-timestamp/README.md b/spec/consensus/proposer-based-timestamp/README.md
@@ -26,14 +26,31 @@ consensus algorithm with *synchronous assumptions*:
 - **Synchronized clocks**: simultaneous clock reads at any two correct validators
 differ by at most `PRECISION`;
 
-- **Bounded message delays**: the end-to-end delay for delivering a message to all correct validators
-is bounded by `MSGDELAY`.
-This assumption is restricted to `Proposal` messages, broadcast by proposers.
+- **Bounded message delays**: the end-to-end delay for delivering a `Proposal`
+  message, broadcast by a correct proposer, to all correct validators is 
+  bounded by `MSGDELAY`.
 
 `PRECISION` and `MSGDELAY` are consensus parameters, shared by all validators,
 that define whether the timestamp of a block is acceptable,
 according with the introduced `timely` predicate.
 
+#### Note on Liveness
+
+Setting too small values for synchronous parameters can compromise,
+possibly in an irreversible way, liveness of consensus.
+This is particularly relevant for the `MSGDELAY` parameter.
+When the `Proposal` end-to-end delay is underestimated or unrealistic, proposed block
+times can be rejected by all correct nodes.
+
+In order to prevent networks with bad parameters from not making progress (that is, 
+remaining at the consensus instance for same height forever), the `MSGDELAY`
+parameter has become adaptive in the implementation.
+This means that the `MSGDELAY` parameter should be interpreted in the form `MSGDELAY(r)`, where `r` is the
+consensus round, with `MSGDELAY(r+1) > MSGDELAY(r)`.
+The original `MSGDELAY` is therefore in practice `MSGDELAY(0)`.
+
+More details and discussion on [issue 2184][issue2184].
+
 ### Timestamp Validation
 
 The `timely` predicate is defined as follows.
@@ -85,17 +102,12 @@ The full solution is detailed and formalized in the [Algorithm Specification][al
 - [Algorithm Specification][algorithm]
 - [TLA+ Specification][proposertla]
 
-### Open issues
+### Issues
 
-- [tendermint/spec#355: PBTS: evidence][issue355]: not really clear the context, probably not going to be solved.
-- [tendermint/spec#372: PBTS: Treat proposal and block parts explicitly in the spec][issue372]
+- [cometbft#2184: PBTS: should synchrony parameters be adaptive?][issue2184]
+- [tendermint/spec#355: PBTS: evidence][issue355]: can we punish Byzantine proposers?
 - [tendermint/spec#377: PBTS: margins for proposal times assigned by Byzantine proposers][issue377]
 
-### Closed issues
-
-- [tendermint/spec#353: Proposer time - fix message filter condition][issue353]
-- [tendermint/spec#370: PBTS: association between timely predicate and timeout_commit][issue370]
-- [tendermint/spec#371: PBTS: should synchrony parameters be adaptive?][issue371]
 
 [main_v1]: ./v1/pbts_001_draft.md
 
@@ -117,3 +129,4 @@ The full solution is detailed and formalized in the [Algorithm Specification][al
 [issue371]: https://github.com/tendermint/spec/issues/371
 [issue372]: https://github.com/tendermint/spec/issues/372
 [issue377]: https://github.com/tendermint/spec/issues/377
+[issue2184]: https://github.com/cometbft/cometbft/issues/2184
diff --git a/spec/consensus/proposer-based-timestamp/pbts-algorithm.md b/spec/consensus/proposer-based-timestamp/pbts-algorithm.md
@@ -53,10 +53,13 @@ It is a temporal requirement, associated with the following
 
 - Synchronized clocks: the values simultaneously read from clocks of any two correct processes differ by at most `PRECISION`;
 - Bounded transmission delays: the real time interval between the sending of a proposal at a correct process and the reception of the proposal at any correct process is upper bounded by `MSGDELAY`.
+  - With the introduction of [adaptive message delays](./pbts-sysmodel.md#pbts-msg-delay-adaptive0),
+    the `MSGDELAY` parameter should be interpreted as `MSGDELAY(r)`, where `r` is the current round,
+    where it is expected `MSGDELAY(r+1) > MSGDELAY(r)`.
-  - With the introduction of [adaptive message delays](./pbts-sysmodel.md#pbts-msg-delay-adaptive0),
-    the `MSGDELAY` parameter should be interpreted as `MSGDELAY(r)`, where `r` is the current round,
-    where it is expected `MSGDELAY(r+1) > MSGDELAY(r)`.
+  - With the introduction of [adaptive message delays](./pbts-sysmodel.md#pbts-msg-delay-adaptive0),
+    the `MSGDELAY` parameter should be interpreted as `MSGDELAY(r)`, where `r` is the round in which the proposal was broadcast and
+    where `MSGDELAY(r+1) > MSGDELAY(r)`.
-  - With the introduction of [adaptive message delays](./pbts-sysmodel.md#pbts-msg-delay-adaptive0),
-    the `MSGDELAY` parameter should be interpreted as `MSGDELAY(r)`, where `r` is the current round,
-    where it is expected `MSGDELAY(r+1) > MSGDELAY(r)`.
+  - With the introduction of [adaptive message delays](./pbts-sysmodel.md#pbts-msg-delay-adaptive0),
+    the `MSGDELAY` parameter should be interpreted as `MSGDELAY(r)`, where `r` is the round in which the proposal was broadcast and
+    where `MSGDELAY(r+1) > MSGDELAY(r)`.
 
 #### **[PBTS-RECEPTION-STEP.1]**
 
-Let `now_p` be the time, read from the clock of process `p`, at which `p` receives the proposed value `v`.
+Let `now_p` be the time, read from the clock of process `p`, at which `p` receives the proposed value `v` of round `r`.
 The proposal time is considered `timely` by `p` when:
 
 1. `now_p >= v.time - PRECISION`

diff --git a/spec/consensus/proposer-based-timestamp/pbts-sysmodel.md b/spec/consensus/proposer-based-timestamp/pbts-sysmodel.md
@@ -71,6 +71,39 @@ proposal message broadcast by correct processes: it is a *worst-case* parameter.
 As message delays depends on the message size, the above requirement implicitly
 indicates that the size of proposal messages is either fixed or upper bounded.
 
+#### **[PBTS-MSG-DELAY-ADAPTIVE.0]**
+
+This specification is written assuming that there exists an end-to-end maximum
+delay `maxMsgDelay` observed in the network, possibly unknown, and
+that the chosen value for `MSGDELAY` is such that `MSGDELAY >= maxMsgDelay`.
+Under this assumption, all properties described in this specification are satisfied.
+
+However, it is possible that in some networks the `MSGDELAY` parameters
+selected by operators is too small, i.e., `MSGDELAY < maxMsgDelay`.
+In order to tolerate this possibility, we propose the adoption of adaptive
+end-to-end delays, namely a relaxation of [PBTS-MSG-DELAY.0] where the
+`MSGDELAY` value increases each time consensus requires a new round.
+In this way, after a number of rounds, the adopted `MSGDELAY` should match the
+actual, but possibly unknown, end-to-end `maxMsgDelay`. 
+This is a typical approach in partial synchronous models.
+
+The adaptive system parameter `MSGDELAY(r)` is defined as follows.
+Lets `p` and `q` be any correct processes:
+
+- If `p` sends a proposal message `m` from round `r` at real time `t` and `q` receives `m` at
+  real time `t'`, then `t < t' <= t + MSGDELAY(r)`.
+
+The adaptiveness is represented by the assumption that the value of the
+parameter increases over rounds, i.e., `MSGDELAY(r+1) > MSGDELAY(r)`.
+The initial value `MSGDELAY(0)` is equal to `MSGDELAY` as in [PBTS-MSG-DELAY.0].
+
+For the sake of correctness and formal verification, if `MSGDELAY` is
+chosen sufficiently large, then the fact that it increments in later rounds
+(i) in practice will never be experienced,
+and (ii) also has no theoretical implications.
+The adaptation (increment) of `MSGDELAY` is only introduced here to handle
+potential misconfiguration.
+
 ## Problem Statement
 
 This section defines the properties of Tendermint consensus algorithm
@@ -148,7 +181,7 @@ Lets `(v, v.time, v.round)` be a proposal, then `v.time` is considered `timely`
 
 1. `proposalReceptionTime(p,v.round)` is set, and
 1. `proposalReceptionTime(p,v.round) >= v.time - PRECISION`, and
-1. `proposalReceptionTime(p,v.round) <= v.time + MSGDELAY + PRECISION`.
+1. `proposalReceptionTime(p,v.round) <= v.time + MSGDELAY(v.round) + PRECISION`.
 
 A correct process only sends a `PREVOTE` for `v` at round `v.round` if the
 associated proposal time `v.time` is considered `timely`.
@@ -264,7 +297,7 @@ then there is a correct process `p` (not necessarily the same above considered)
 
 - `beginRound(p,v.round) <= proposalReceptionTime(p,v.round) <= beginRound(p,v.round+1)` and
 - `v.time <= proposalReceptionTime(p,v.round) + PRECISION` and
-- `v.time >= proposalReceptionTime(p,v.round) - MSGDELAY - PRECISION` 
+- `v.time >= proposalReceptionTime(p,v.round) - MSGDELAY(v.round) - PRECISION` 
 
 That is, a correct process `p` started round `v.round` and, while still at
 round `v.round`, received a `PROPOSAL` message from round `v.round` proposing
@@ -292,7 +325,7 @@ If
 then the proposal `(v, v.time, r)` is accepted by every correct process provided that:
 
 - `min{p is correct : beginRound(p,r)} <= v.time <= max{p is correct : beginRound(p,r)}` and
-- `max{p is correct : beginRound(p,r)} <= v.time + MSGDELAY + PRECISION <= min{p is correct : beginRound(p,r+1)}`
+- `max{p is correct : beginRound(p,r)} <= v.time + MSGDELAY(r) + PRECISION <= min{p is correct : beginRound(p,r+1)}`
 
 The first condition establishes a range of safe proposal times `v.time` for round `r`.
 This condition is trivially observed if a correct proposer `p` sets `v.time` to the time it
@@ -308,7 +341,7 @@ In addition, it requires correct processes to stay long enough in round
 `v.round` so that they can receive the `PROPOSAL` message of round `v.round`.
 It assumed here that the proposer of `v` broadcasts a `PROPOSAL` message at
 time `v.time`, according to its local clock, so that every correct process
-    should receive this message by time `v.time + MSGDELAY + PRECISION`, according
+should receive this message by time `v.time + MSGDELAY(v.round) + PRECISION`, according
 to their local clocks.
 
 Back to [main document][main].