THE COl\'IPI.JEXll~Y OF DIS)'I~lBUTED CONC'URRENCYCONTI{OL*

We present a romal framework for distributed databases, and we study the complexity of the concurrency control problem in this framework. Our transactions arc partially ordered set5, of actions, as opposed to the strai.ght-line progratDS of the centraliz~d case. The concurrency cont.rol algorithm, or scheduler, is itself a distributed program. Three notions of perfonnance of the schlcduler are studied and interrelated: (i) its parallelism, (ii) the conlputational complexity of the problems it needs to solve, and (iii) the cost of communication between the various parts of the scheduler. We show that the nutnber of messages necessary and sufficient to support a given level of parallelism is equal to the minmax vaiuc of a combinatorial game. We show that this ganle is PSPACE-complete. It follows that, unless NP= PSPACE, a scheduler cannot siInultaneously minimize communication and be COlYlputationally efficient. This result, we argue, captures the quantunI jump in complcxity of the transition from centralized to distributed concurrcncy control problems.