Leios transaction-level latency/conflicts

[SupernaviX]

In Leios, a transaction is included in an IB, which is included in an EB, which is certified and included (directly or indirectly) in an RB (at which point the TX has "reached the chain"). So far, our simulations have been assuming very simple transactions which are always valid and never conflict with each other. To develop a better understanding of transaction latency, I'd like to know more about TX-level failure cases.

New transactions reach an IB (potentially multiple IBs) very quickly. When IBs are created, their contents are validated against some specific ledger state (and are re-validated against that ledger state as they're propagated through the network). Transactions are included in IBs in a deterministic order, and will simply not get included if they would introduce conflicts within an IB.

When IBs are included in an EB, they're included in some specific deterministic order. Within an EB, the transactions from two different IBs can conflict; when they do, the "first" transaction wins and the second is "rejected". (If the same transaction was duplicated across multiple IBs, it trivially conflicts with itself.) IBs can be included in multiple EBs, though the same IB cannot appear multiple times within an EB (or within any of the EBs it references).

All of that is just background for my question:

How soon can you be reasonably sure that a TX has been accepted or rejected?

If a transaction has reached an EB without being rejected, it doesn't conflict with anything else in that EB. If that EB is referenced by a later EB, could that later EB introduce conflicts which cause the TX to be rejected? Or can we prevent that with the right serialization order?

If a transaction is included in every certified EB from a particular pipeline, can we be reasonably certain that it will (eventually) be included in an RB without conflicts?

Can forks in the base chain cause previously-accepted Leios transactions to become rejected? I suspect no; certified EBs have plenty of time to propagate through the network, so forks would likely include the same certified EBs as the "real" head. But I'm not a researcher and I don't trust my reasoning on that.

[Saizan]

Ordering of Txs for ledger reconstruction seems quite subtle.

If a transaction has reached an EB without being rejected, it doesn't conflict with anything else in that EB. If that EB is referenced by a later EB, could that later EB introduce conflicts which cause the TX to be rejected? Or can we prevent that with the right serialization order?

In Full leios, EBs from pipeline i+1 do not reference EBs from pipeline i, so when one of each is referenced by a later EB it's quite possible that Txs that looked "settled" for the EB of pipeline i+1 are now rejected in favor of ones from the EB of pipeline i. There's a short window of time where you can't be sure both will be certified, moreover even if they are it's not clear you can count on the fact EBs from earlier pipelines should win the ledger reconstruction ordering: see next point.

Can forks in the base chain cause previously-accepted Leios transactions to become rejected? I suspect no; certified EBs have plenty of time to propagate through the network, so forks would likely include the same certified EBs as the "real" head. But I'm not a researcher and I don't trust my reasoning on that.

Building on the previous example, I think this can happen if the fork happens around the time of the certification for the EB of pipeline i+1, so that one fork picks the EB from pipeline i and the other i+1. At that point of course we will have fairly different ledger states for the forks. Moreover, if we want that a Tx settled in an RB is never rejected in a chain extension, you really have to pay attention to which fork wins, because they have made opposite choices of which EB comes first, which won't be smoothed over by later including a newer EB that references both EBs (see the other discussion for more details).

I am not really an expert in these sort of questions either though, so I am not sure how often you can expect something like this, or how much it impacts the timing for having confidence that a Tx is accepted.