Reasoning with geometric information in digital space

摘要

Concurrency requires consistency and correctness. Isothetic rectangles can be used as a geometrical technique to verify a safe and deadlock free schedule for concurrent nodes. However, the known algorithms for concurrency using isothetic rectangles require the prior knowledge of the system behavior. We provide a new mechanism to use isothetic rectangles without this limitation. The discrete nature of isothetic rectangles provides an opportunity for inter-diagrammatic reasoning. Inter-Diagrammatic Reasoning (IDR) can be easily computed on a parallel machine, and has a complexity of O(n) for most of the iso-rectangles problems where the best known algorithm was O(n log n) in Euclidean geometry. This new framework will also allow dynamic mode of operation in calculating the closure of a set of iso-rectangles; rather than restricting the solution to static systems where all required resources must be reserved in advance.