Is memoization a plausible option for pulsers?

[nfrisby]

The "obvious" approach to Issue IntersectMBO/ouroboros-consensus#1255 is for Consensus to call the tick function more often, instead of only when blocks arrive. There are some remaining subtleties (eg which state to forecast from in the ChainSync client and minting logic), but the main idea is that the ledger interface wouldn't need to change --- Consensus should just call it more often.

However, Consensus has "over-specified" its types somewhat, such that ledger states must evolve according to a strict tick -> apply -> tick -> apply -> ... schema. So we'd have to re-architect things a bit/dilute those types.

Also, various threads read the ledger state at various times, "on demand". For example, the ChainSync client doesn't necessarily use the latest ledger state when forecasting. If the cost of forecasting is improved by incremental ticking of the ledger state you're forecasting from, then the ChainSync clients would need to be using ledger states that have been incrementally ticked as the clock advances.

There are more trade-offs to consider here, since the current ChainSync client is not necessarily forecasting from the tip of its selection, eg if the peer has sent headers that branch off from a previous block. (Moreover, we anticipate changing it to forecast from the tip of the immutable selection, ie k blocks back. So maybe we'd need to also be ticking that ledger state?) The minting logic, on the other hand, does do its forecasts from the tip of the node's selection --- that's probably the one everyone immediately imagines, and it wouldn't be too bad to handle that as a special case.

Let me try to sketch the challenge another way. Suppose we do change Consensus so that it's constantly ticking and updating the ledger state at the tip of its selection, as the wall clock changes. This would improve latency in the minting logic (aka "the leadership check"), for example. If the next block extends our selection, then it would also improve latency in validating that next block. But suppose that instead the next block is a fork (even just one block deep). Then all of the ticking we did of our selection was for not: we weren't ticking the one-older ledger state, which is the one we need to use to validate the new block(s).

---

This Issue is to ask for the Ledger Team to consider an alternative approach to the incremental ticking that would avoid the above complaints/concerns on the Consensus side. I'll sketch the idea, and then you can shoot it down :D

• When creating a pulser, also create an (unforced) stream of thunks that represent the pieces of work to be done.
• The pulser merely chooses how many thunks to force.

The desired upshot is this: all of the existing Consensus code would not need to change. Consensus would merely add a new thread that wakes up every second and ticks the ledger state at the tip of the node's selection to the slot of the current wall clock. That would force the thunks, and then classic memoization would ensure that anytime the other threads tick and/or forecast any (recent) ledger state, it'll be fast since those thunks will have already been evaluated.

---

To summarize:

Q1) Will repeatedly forecasting (at most 3k/f slots) from some ledger state ever pay costs that would have been eliminated by incrementally ticking that ledger state before forecasting from it?

Q2) Do you have any openness to relying on memoization in the pulsers, so that repeatedly ticking/forecasting from some ledger state will only pay the pulser costs once?

Q3) Please don't ignore the short fork scenario. (This is a re-quest-ion, I suppose 😁.)

Let's convene to see where our options are at after you've replied to the above questions.

[nfrisby]

I'll assign to @lehins for now, but delegation is an option, of course.