Asynchronous Algorithms and Concurrency Control

本研究致力于提高异步算法的性能。这些算法涉及许多独立的活动，这些活动通常访问公共数据。活动必须彼此同步，以确保数据保持一致。不幸的是，同步会降低性能。这项研究的总体目标是开发减少同步要求的技术。大部分研究将关注数据库系统中的并发控制，并将重点放在乐观算法上。这类算法基于很少需要同步的假设。它们允许活动以异步方式执行，并在检测到应该同步活动的情况时依赖于回滚。因此，回滚是主要的成本，所提议的研究的目标之一是开发降低其发生概率的技术。其中包括使用有关活动的语义信息，使用特殊技术来处理频繁访问的数据区域(热点)，以及使用在将活动表示为Prolog程序时可以收集的有关该活动的信息。将乐观算法应用于复制的数据库是另一个感兴趣的领域。这类数据库是为了改善故障情况下数据的可用性而提出的，也可以用来提高性能。最后，将研究在某些共享数据结构上执行非原子更新的策略。其目标是确保异步执行的读取器始终正确运行。

This research is concerned with improving the performance of asynchronous algorithms. These algorithms involve a number of independent activities which generally access common data. Activities must synchronize with one another to insure that data is kept consistent. Unfortunately, synchronization impairs performance. The overall goal of the research is to develop techniques for reducing synchronization requirements. Much of the research will be concerned with concurrency control in database systems and will focus on optimistic algorithms. Such algorithms are based on the assumption that synchronization is rarely needed. They allow activities to execute in an asynchronous fashion and rely on rollback if situations are detected in which activities should have synchronized. Thus, rollback is the major cost and one goal of the proposed research is to develop techniques for reducing the probability of its occurence. These include the use of semantic information about activities, the use of special techniques for handling heavily accessed regions of the data (hotspots), and the use of information that can be gathered about an activity when it is formulated as a Prolog program. The application of optimistic algorithms to replicated databases is another area of interest. Such databases have been proposed to improved the availability of data in failure situations and can also serve to enhance performance. Finally, research will be done on strategies for performing non-atomic updates on certain shared data structures. The goal is to guarantee that readers, which execute asynchronously, always function correctly.