Having produced parachain blocks retracted is the very least detrimental to throughput of the chain, but also harms user and developer experience:

• Worst case, blocks gets retracted, transaction becomes invalid, user has to issue a new one.
• Having a transaction in a block, is already some proof of validity, under the
  assumption that we trust collators.
• Having a transaction in a block, which got backed (off-chain), provides even
  higher level of security.

In general the block will move up in assurance over time, but if it happens
frequently that a block after all just gets discarded, the benefit this property
vanishes and one actually has to wait for definite finality, which takes the
longest.

The following is a kind of unordered list of things that can cause a parachain block to not make it + solutions to it.

Speculative Availability

Give availability more time, to enhance likelihood of cores getting freed on
time:

• Factor out provisioner logic to get backable candidates
• Reuse that code in availability-distribution to already fetch scheduled
  cores and then backable candidates from prospective parachains
• Add fetch tasks for these (with the leaf it was scheduled in)
• Profit

Immunity to relay chain forks

Either:

Build on slightly older relay parents

• Simple
• Can be made pretty robust, if we choose relay parents which have been
  finalized already.
• Also provides some resilience against relay chain reorgs.

• But: Latency with regards to message processing is added.

Build on all forks

• No additional latency

• More resources on the collator (likely fine, as block building is mostly
  single core, hence additional cores are free)
• More complexity: One does not only need to track one fork, but multiple.
• More work for the relay chain.

Avoid relay parents becoming obsolete

Allow relay parents that survive longer than the claim queue length. Then the
runtime would still accept those candidates if in the current claim queue the
parachain still has assignments on the core. This way, if e.g. a block producer does not
produce a block, the parachain would merely slow down a bit, but not get its
blocks discarded.

Update: We will punt on this for now.

Session boundaries

Even with above optimizations, session boundaries would still make relay parents
obsolete. A simple fix would be for collators to anticipate the session change
and stop producing candidates that would end up getting backed in the last block of the session.

Core Changes

With above "Avoid relay parents becoming obsolete", this would not work if the
parachain still has a core assigned, but it is different now. This is not easy
to fix in the current design, luckily it should also have very little impact:

• Chains which need high levels of reliability, should aim to keep their core
  mappings stable.
• With the above, you only run into issues if a block producer messes up exactly
  at that rare occasion you changed your core mapping. Given that we have
  pretty solid 6s block times, the chances for this happening seem acceptable.

Reliable Collator Protocol

We want to make validator - collator connections as reliable as possible to
ensure produced blocks also end up getting validated in a timely manner.