Synchronization in Concurrent Algorithms

本研究的目的是研究并发（可能是分布式）算法中的同步。这种算法涉及许多独立的任务或事务，这些任务或事务周期性地相互同步。不幸的是，同步会降低性能，因为任务必须彼此等待。本文将研究通过减少同步来提高性能的技术，并对与同步相关的异步算法的结构进行建模。同步的一个主要原因是需要并发任务来访问共享数据。数据通常以完整性约束为特征，并且通常要求这些约束在任务查看的所有状态中都为真。本研究分为三个相关问题。我们将研究如何使用语义来删除自动执行共享数据更新的要求。一种将更新分解为更小的单元的策略正在被研究，这些单元可以与其他任务的执行交织在一起，从而减少同步延迟，同时保持完整性约束。目前正在研究增加并发性和违反完整性约束之间的权衡。将同步放宽到允许违规的程度，但不允许数据的状态偏离正在研究的约束持有的状态太远。再次强调的是提高访问共享数据的异步算法的性能。最后，将研究与同步相关的异步算法的结构，以查看是否可以根据所涉及的同步量对算法进行比较。

The objective of the research is to investigate synchronization in concurrent - perhaps distributed - algorithms. Such algorithms involve a number of independent tasks, or transactions, which synchronize with one another periodically. Unfortunately, synchronization impairs performance since tasks must wait for one another. Techniques for improving performance by reducing synchronization will be investigated and the structure of an asynchronous algorithm as it relates to synchronization will be modelled. A major cause for synchronization is the need for concurrent tasks to access shared data. Data is frequently characterized by integrity constraints and it is generally required that these be true in all states viewed by the tasks. The research divides into three related problems. The use of semantics to remove the requirement that updates to shared data be performed atomically will be investigated. A strategy for decomposing updates into smaller units which can be interleaved with the execution of other tasks, hence reducing synchronization delays while maintaining integrity constraints is being studied. The tradeoff between increased concurrency and integrity constraint violation is under study. Relaxing synchronization to the extent of permitting violations but not allowing the state of the data to deviate too far from one in which the constraints hold is being studied. Once again the emphasis is on improving the performance of asynchronous algorithms which access shared data. Finally, the structure of an asynchronous algorithm as it relates to synchronization will be studied to see whether algorithms can be compared on the basis of the amount of synchronization involved.