Cost accounting in the Replay RSpace relating to the matcher

Assumptions

We assume we have a static checker that determines whether a match has a constant cost - for example, matching for true or a plain integer. For those matches that do not have a constant cost, we assign a global constant C as the cost and prohibit any matches that are more costly than this. We also assume that the (not tight) upper bound cost of running the matcher to get a single successful match on a channel will be as if all the produces on that channel that eventually reduced according to the current replay log already existed in the replay rspace, and we ran the matcher over all of them.

Algorithm

We have two cost entries in the log for each comm event: "lower bound" and "higher bound". For comm events involving joins, we will have one "lower bound" and "higher bound" per channel and a "higher bound" for the overall - thus there will be 2*(channel count) + 1 cost entries for a join in total.

We go through all entries in the replay log twice.

(First Run) For comm events involving a single consume, we record the cost of the successful chosen match as "lower bound". For comm events involving a join, we record the cost of the successful chosen match for each channel as the "lower bound" cost for that channel. At the end of the first loop all the "lower bound" costs for each entry are calculated.

(Second Run) For comm events involving a single consume, we sum the "lower bound" of all comm reductions on that channel and say that is the "higher bound". For comm events involving a join, we sum up all the "lower bound" costs of all comm reductions on that channel and assign that as the "higher bound" cost for that channel. We then sum across all the "higher bound" costs for each channel in the join, and that is the "higher bound" cost for the entire comm event with that join.

Optimizations and Analysis

For any comm event on a channel, the "higher bound" cost will be the same as any other comm event on the channel so if you calculate the "higher bound" cost for one comm event on a channel, you don't have to re-sum for another.

There is the obvious downside that you essentially double pay by having to pay for other comm events on the same channel. However if all comm events in the same block do not happen on the same channel, then the "lower bound" cost is the same as the "higher bound" cost. Furthermore, if the same deployer is the one causing comm events on the same channel, which is often the case, the deployer isn't really double paying for another deployer. In general, this solution works well if we keep blocks small and propose often.