Concurrency, BFS vs DFS (and a proposal)

I would like to continue the discussion about concurrency/BFS vs DFS, as described

  1. I understand that moving to message passing (all effects are final
    before operations are executed) solves the problems of
    control-flow in Ethereum. An alternative would be to have
    call-return without effects (only fail/no-fail) or limited effects
    after the return. This limited call-return enables useful patterns
    like defensive programming using monitors/runtime-verification as
    pointed out in

    In a nutshell, one can write “checkers” (even written by independent
    developers as a wrapper) that inspect the effect of the whole smart
    contract invocation and decide to accept or abort.

  2. Is there any reason beyond sharding to prefer BFS over DFS? Again,
    DFS is more natural to think about and it would another way to
    implement monitors.

    I would like to suggest an alternative to sharding that can be used
    both in DFS and in BFS (effectively making DFS efficient). Ideally,
    if one knew the effects of all sub-operation generated by a
    contract many call sequences (whose semantics are sequential) could
    be run in parallel. However, Without formally proven contracts this
    is not feasible.

    But, inspired by optimistic concurrency control, one can just
    assume that calls are independent and run them in parallel. Since
    the effects are of course known after the execution, one can check
    after the facto whether the parallelization was to optimistic, and
    (if necessary) re-run the whole tree (this time with more knowledge).

    By the way, this method of run-and-check can be used with
    BFS+tickets. In my view, as discussed in
    Contract signatures since
    tickets have an immediate global effect (e.g PUNCH) this would
    jeopardize sharding (as an operation can depend on whether a
    previous operation PUNCHED a shared ticket).

What do you think?

1 Like

An alternative would be to have
call-return without effects (only fail/no-fail)

See Adding Read-Only Calls for a discussion on this topic.

I think BFS will become an “obvious” choice, if we think about Tezos operations in terms of ACID transactions. Tezos already provides isolation (each new operation and its spawned operations are executed in isolation from the other operations in the pool) and durability (once a block is baked, the operation result cannot be lost).

Tezos solves atomicity for the following cases:

  • Individual contract call (individual transaction) atomically updates state of the single contract
  • A contract can spawn a list of operations to invoke other contracts. Such a list can be considered a composite transaction (composed of a sequence of individual transactions). BFS order guarantees that the composite transaction will not be interleaved with the operations from other composite transactions.

However, each operation can depend on the state of exactly one contract. What if we want to express calculation that still updates the state of the called contract, but depends on data from other contracts on the chain? Currently, the only available option is continuation passing style (CPS) entry points; Read-Only Calls are also proposed.
But those techniques introduce their own problems that violate composite transaction consistency. There is a detailed analysis and some proposed solutions here.

Monitors are an interesting feature, but it looks like they do not address multi-contract interactions.

I think it is an interesting idea, very similar to software transactional memory (STM).

I am not sure I understand. In my understanding BFS breaks this notion of atomicity (DFS does not). If an operation A spawns two further operations B and C, BFS does not guarantee that B (and its suboperations say B1 B2) execute ACID with respect to C and its suboperations (say C1 and C2). If B, B1, B2, C, C1, C2 punch tickets (for example, which is a global shared resource, and therefore has visible effect across oprations), the BFS order is B,C,B1,B2,C1,C2. Therefore the atomicity of B+subops with respect to C+subops os broken. The DFS order would have been B,B1,B2,C,C1,C2 which does preserve atomicity.

I want to understand why BFS is preferred over DFS (is it only efficiencty/sharding?) because there is a price to pay in BFS: atomicity, etc.

Am I missing something?

I am not sure I understand. In my understanding BFS breaks this notion of atomicity (DFS does not).

In your example, if operation A spawns operations B and C, [B,C] become a composite transaction. BFS guarantees that [B, C] will not be interleaved with any other operations (like [B, B1, B2, C]). I think about a composite transaction as a sequence of updates of multiple contracts that transitions one global consistent state to another global consistent state. The global state may be inconsistent in the middle of the composite transaction, thus injecting operations in the middle of a composite transaction will make them operate on inconsistent state.

Let’s imagine some kind of accounting application where each account contract maintains its own balance and supports debit and credit operations. There is also a banker contract with transfer operation. To fulfill a transfer, banker contract spawns two operations to debit and credit two accounts:
[transfer_op, debit_a, credit_b]. When executed, the global state (total balance of all accounts) is consistent before the operation debit_a and after the operation credit_b, but it is inconsistent in between. If contract A, spawns some operations depending on the state of the contract B using DFS order ([transfer_op, debit_a, a1, a2, credit_b]), those operations will access inconsistent global state.
If a1 or a2 operations involve balance of the contract B or a combination of balances A and B, they will operate on inconsistent state.