Mathematical studies on a transaction's waits and deadlocks in a 2pl environment
The “straw man” analysis is based on the assumption that the accessible unit and locking unit are both a record occurrence (or a tuple); consequently the results cannot be applied when a locking unit is a large granule such as an area, a file, an index (or a data) block. In this study, the probabilities of a transaction's waits and deadlocks are derived when the accessible unit is a data object and the locking unit is a granule. The results can be used to explain a transaction's wait and deadlock situations for (1) various sizes of a granule and (2) different distributions of data objects accessed by a transaction. To determine the degree of consistency between a theoretical result and an experimental test, a simulation model is set, and the experimental results are nearly consistent with the probabilistic model.
Consider a randomized load balancing problem consisting of a large number n of server sites each equipped with K servers. Under the greedy policy, clients randomly probe a site to check whether there is still a server available. If not, d -- 1 other sites are probed and the task is assigned to the site with the fewest number of busy servers. If all the servers are also busy in each of these d -- 1 sites, the task is lost. This short paper analyzes a set of policies, i.e., (L, d) policies, that will occasionally probe additional sites even when there is still a server available at the site that was probed first. Using mean field methods, we show that these policies, that preventively probe other sites, can achieve the same loss probability while requiring a lower overall probe rate.