Concurrent Access to Data Structures.

File structures designed for modern data base systems must allow a high degree of concurrent access. This holds for distributed as well as centralized data bases. Ideally, two processes that access disjoint data are allowed to proceed simultaneously, unhampered by the others presence. However, such processes may interfere due to access path collition, for example at the root of a tree structured file. Elaborate and costly protocols have been developed to guarantee correct operation in concurrently accessed B-trees. It is shown that 2-level file structures allow simpler concurrent access protocols, and present a control scheme that strikes a good compromise between the conflicting goals of simplicity and maximal concurrency. This document proposes a definition of what it means for a file system to be correct and show that the simple and efficient protocol designed is correct. Author