论文标题
大型物体有效的通用构造
An Efficient Universal Construction for Large Objects
论文作者
论文摘要
本文介绍了L-UC，这是一种通用结构，可有效地以候补的方式实现大状态的动态对象。 L-UC的步骤复杂性为O（n+kW），其中n是过程的数量，k是间隔的争论（即操作执行间隔期间的最大活动过程数量），W是对模拟对象的顺序实现进行操作的最差时间的时间复杂性。 L-UC有效地实现了大小可以动态变化的对象。它通过有效处理状态大且可以动态变化或实现更好的步骤复杂性的对象来改善以前的通用结构。
This paper presents L-UC, a universal construction that efficiently implements dynamic objects of large state in a wait-free manner. The step complexity of L-UC is O(n+kw), where n is the number of processes, k is the interval contention (i.e., the maximum number of active processes during the execution interval of an operation), and w is the worst-case time complexity to perform an operation on the sequential implementation of the simulated object. L-UC efficiently implements objects whose size can change dynamically. It improves upon previous universal constructions either by efficiently handling objects whose state is large and can change dynamically, or by achieving better step complexity.
