Algorithm for estimating the execution time of nested transactions on a locally distributed database system

This paper describes an algorithm for estimating the execution time of nested transactions running on a locally distributed database system. We first establish the model of nested transactions and the model of a locally distributed database system. Then we present a non-deterministic algorithm that can evaluate the execution time of a nested transaction using general routing strategies. The last part of the paper analyses the algorithm by presenting solutions to some special cases and the lower and upper bounds of executing time estimation.