We present the following algorithms, each characterized roughly in terms of the factor by which it slows down the computation being checked. In each case, memory usage is increased by roughly the same factor, unless otherwise stated. This algorithm checks programs with locks, with a slowdown factor of kL , where k is the maximum number of locks held simultaneously, and L is the maximum number of combinations of locks held during accesses to any particular location. This algorithm checks programs with locks, with a slowdown factor of only k . This algorithm checks programs with guard statements, with a slowdown factor of lg k , where k is the maximum number of simultaneously guarded memory blocks.
Space usage is increased by a constant factor.