论文标题
带有本地读取的复制对象的参数化算法
Parameterized algorithm for replicated objects with local reads
论文作者
论文摘要
我们考虑实现可线化对象的问题，这些对象支持读取和读取模式 - 写入（RMW）操作，并在消息通讯系统中使用流程崩溃。由于在许多系统中，阅读操作远远超过了RMW操作，因此我们对强调阅读操作效率的实施感兴趣。 我们为部分同步系统提供了一种参数化算法，其中进程可以访问在$ε$之内同步的外部时钟。使用此算法，每个读取操作都是局部的（直观地，它不会触发消息）。如果读取与冲突的RMW并不同时发生，则立即执行没有等待的情况；此外，即使有同时冲突的RMW，最糟糕的案例也很少延迟。例如，可以设置算法的参数，以确保每个读取都需要$ε$的时间。据我们所知，这是第一个在我们在这里假设的部分同步系统中实现此键的第一种算法。我们的参数化算法概括了Chandra等人的基于（非参数化的）租赁算法。 [6]最差的读取时间为$3δ$，其中$δ$是最大消息延迟。 该算法的参数可用于权衡阅读和RMW操作的最差时间。它们还可以用来利用以下事实：在许多消息通讯系统中，大多数消息的延迟是小于最大消息延迟〜$δ$的大小订单：例如，可以设置参数，以便在“良好”时期中，消息延迟为$δ^*^*^*^* \ llδ$，读取最多需要$ $ $ $ $ $ $3Δ*
We consider the problem of implementing linearizable objects that support both read and read-modify-write (RMW) operations in message-passing systems with process crashes. Since in many systems read operations vastly outnumber RMW operations, we are interested in implementations that emphasize the efficiency of read operations. We present a parametrized algorithm for partially synchronous systems where processes have access to external clocks that are synchronized within $ε$. With this algorithm, every read operation is local (intuitively, it does not trigger messages). If a read is not concurrent with a conflicting RMW, it is performed immediately with no waiting; furthermore, even with a concurrent conflicting RMW, a read experiences very little delay in the worst-case. For example, the algorithm's parameters can be set to ensure that every read takes $ε$ time in the worst-case. To the best of our knowledge this is the first algorithm to achieve this bound in the partially synchronous systems that we assume here. Our parametrized algorithm generalizes the (non-parameterized) lease-based algorithm of Chandra et al. [6] where the worst-case time for reads is $3δ$, where $δ$ is the maximum message delay. The algorithm's parameters can be used to trade-off the worst-case times for read and RMW operations. They can also be used to take advantage of the fact that in many message-passing systems the delay of most messages is order of magnitudes smaller than the maximum message delay~$δ$: for example, the parameters can be set so that, in "nice" periods where message delays are $δ^* \ll δ$, reads take at most $ε$ time while RMWs take at most $3 δ^*$ time.
