Continuing with the discussion of BFS/DFS… I have been working with Margarita Capretto @mcapretto about Monitoring (see post Monitors), in particular studying new mechanisms, opcodes, etc that allow to effectively implement monitors. We already have some negative results (impossibility) and positive results.
One of the topics we explored is the influence of the scheduler order (BFS, DFS, etc) and we studied different ways to mix BFS and DFS.
We always assume that it is crucial to guarantee legacy (old contracts keep running as usual, assuming that internal operations they invoke run as usual), so no Yolo.
Names and implementation:
- The Tezos scheduler allows to insert operations after the execution of a contract, and to extract the next operation to execute.
- Internally the scheduler maintains a buffer with the pending operations.
- The runtime system uses the scheduler to run a contract until either the buffer is empty or the gas is exhausted or some contract fails (explicitly or balance errors).
- BFS corresponds to the scheduler adding the new operations at the end of the buffer (aka FIFO or queue). This is what Tezos does now.
- DFS would correspond to adding operations at the beginning of the buffer (aka LIFO or stack).
Why not exploring different or mixed ways to insert and extract from the buffer?
-
Mixed First Search (MFS). Operations can generate two lists (with the second lists empty by default for legacy). The operations in the first lists are added at the end of the buffer (BFS) while the operations from the second list are added at the beginning (DFS).
-
Double Buffer First Search (DBFS). The scheduler maintains two buffers, and iterates over one until exhaustion (in a BFS, DFS or MFS, to be discussed) before starting with the second. In our study of monitoring this was explored to run monitors at the end of the external operation (the second buffer would be for monitoring only). This is very useful when combined with capabilities, for example limiting the operations from the second buffer to NOT generate further operations (or even change the storage, etc).
-
Contexts. The idea here is that when an operation is created, it can be labeled to be “framed” with its own buffer of sub-operations (like a push so-to-speak). The semantics of this local buffer of operations is again an orthogonal issue (BFS or DFS or MFS…) but this local buffer will be emptied before continuing with further operations generated by the father operation. This mechanism eases the separation between generated operations, for example to guarantee legacy or to guarantee isolation between operations.
Note that all the ideas above (6. 7. And 8.) still maintain that operations are functions that terminate generating buffer(s) of operations to be scheduled (no call-return in the middle of the function).
