New Proposal Timeouts

[isheff]

As presently designed, Heterogeneous Paxos needs time-outs before proposals are re-sent (to ensure liveness). This is equivalent to time-outs for choosing new leaders in Tendermint. How do we want to choose time-outs?

In "always-committing" chains, we can start exponentially growing time windows at the time of the last commit, and then assume they will eventually be big enough. Unfortunately, in "lazy" chains that only append blocks when there is demand, this means that if there is not demand for a while, there will be HUGE time windows by the time there is a proposal. If a round (or leader) fails, we then have to wait a long time to re-try.

Alternatively, constant time windows have a different problem: if the window is too short, we'll be timing out and re-proposing too fast to get anything done, and if it's too long, we run unnecessarily slowly.

Solutions include:

• do the whole thing with shared randomness and probabilistic termination (not sure how to do this)
• figure out some more clever clock sync setup that can reset time windows
• reach some kind of consensus even when there is no demand to reset time windows
  • hopefully this work can be shared across multiple chains, or it will be unnecessarily burdensome.

Related: Tendermint's discussion on empty blocks: https://github.com/tendermint/tendermint/issues/5911

Related: Jacob's Slack thread: https://heliax.slack.com/archives/C02AHU18CTG/p1637242390019000

[cwgoes]

Hmm, is there a reason we can't just keep the timeouts as-is when we aren't running consensus rounds?

In "lazy mode", the acceptors shouldn't be sending any message at all (except transactions which might prompt existing lazy mode), right?