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.