{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:30:32Z","timestamp":1787340632748,"version":"build-2736575974"},"reference-count":20,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[1985,2]]},"abstract":"<jats:p>We present a formal framework for distributed databases, and we study the complexity of the concurrency control problem in this framework. Our transactions are partially ordered sets of actions, as opposed to the straight-line programs of the centralized case. The concurrency control algorithm, or scheduler, is itself a distributed program. Three notions of performance of the scheduler are studied and interrelated: (1) its parallelism, (2) the computational complexity of the problems it needs to solve and (3) the cost of communication between the various parts of the scheduler. We show that the number of messages necessary and sufficient to support a given level of parallelism is equal to the minimax value of a combinatorial game. We show that this game is PSPACE-complete. It follows that, unless $\\text{NP} = \\text{PSPACE}$, a scheduler cannot simultaneously minimize communication and be computationally efficient. This result, we argue, captures the quantum jump in complexity of the transition from centralized to distributed concurrency control problems.<\/jats:p>","DOI":"10.1137\/0214004","type":"journal-article","created":{"date-parts":[[2005,2,24]],"date-time":"2005-02-24T06:25:35Z","timestamp":1109226335000},"page":"52-74","source":"Crossref","is-referenced-by-count":3,"title":["The Complexity of Distributed Concurrency Control"],"prefix":"10.1137","volume":"14","author":[{"given":"Paris C.","family":"Kanellakis","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Christos H.","family":"Papadimitriou","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,13]]},"reference":[{"key":"R1","doi-asserted-by":"publisher","DOI":"10.1145\/356842.356846"},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1145\/320128.320131"},{"key":"R3","doi-asserted-by":"crossref","unstructured":"Ashok K. Chandra, Larry J. Stockmeyer,  Alternation,  17th Annual Symposium on Foundations of Computer Science (Houston, Tex., 1976), Long Beach, Calif.,  1976, 98\u2013108. IEEE Comput. Soc 58:251070473.68043","DOI":"10.1109\/SFCS.1976.4"},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1145\/360363.360369"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1145\/321978.321989"},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1145\/359576.359585"},{"key":"R7","unstructured":"P. C. Kanellakis,  The complexity of concurrency control for distributed databases,  1981, MIT\/LCS\/TR-269, Aug."},{"key":"R8","doi-asserted-by":"crossref","unstructured":"H. T. Kung, C. H. Papadimitriou,  An optimality theory of database concurrency control,  Proc. 1979 SIGMOD,  116\u2013126","DOI":"10.1145\/582095.582114"},{"key":"R9","doi-asserted-by":"crossref","unstructured":"R. E. Ladner,  The complexity of problems in systems of communicating sequential processes,  Proc. 11th ACM Symposium on Theory of Computing,  1979,  214\u2013223","DOI":"10.1145\/800135.804415"},{"key":"R10","doi-asserted-by":"publisher","DOI":"10.1145\/359545.359563"},{"key":"R11","doi-asserted-by":"publisher","DOI":"10.1145\/322154.322158"},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(82)91034-8"},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1145\/320251.320260"},{"key":"R14","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(78)90045-4"},{"key":"R15","doi-asserted-by":"crossref","unstructured":"R. S. Stearns, P. M. Lewis, D. J. Rosenkrantz,  Concurrency control for database systems,  17th Annual Symposium on Foundations of Computer Science (Houston, Tex., 1976), IEEE Comput. Soc., Long Beach, Calif.,  1976,  19\u201332 57:14666","DOI":"10.1109\/SFCS.1976.12"},{"key":"R16","doi-asserted-by":"publisher","DOI":"10.1145\/320071.320076"},{"key":"R17","volume-title":"Principles of database systems","author":"Ullman Jeffrey D.","year":"1982"},{"key":"R18","doi-asserted-by":"crossref","unstructured":"M. Yannakakis, C. H. Papadimitriou, H. T. Kung,  Locking policies: safety and freedom from deadlock,  Proc. 20th Foundations of Computer Science Conference,  1979,  283\u2013287","DOI":"10.1109\/SFCS.1979.22"},{"key":"R19","doi-asserted-by":"crossref","unstructured":"A. C. Yao,  Some complexity questions related to distributive computing,  Proc. 11th ACM Symposium on Theory of Computing,  1979,  209\u2013213","DOI":"10.1145\/800135.804414"},{"key":"R20","unstructured":"Eden Project Proposal: Research in Integrated Distributed Computing, Dept. of Computer Science, Univ. Washington, Pullman, TR 80-10-1, October 1980"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/0214004","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:42:09Z","timestamp":1787337729000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/0214004"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1985,2]]},"references-count":20,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1985,2]]}},"alternative-id":["10.1137\/0214004"],"URL":"https:\/\/doi.org\/10.1137\/0214004","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[1985,2]]}}}