论文标题
具有sublogarithmic RMR复杂性的可收回，可流产和自适应相互排斥
Recoverable, Abortable, and Adaptive Mutual Exclusion with Sublogarithmic RMR Complexity
论文作者
论文摘要
我们介绍了同时可流产的第一个可回收的相互排除（RME）算法，适应点的争夺，并且具有sublogarithmic rmr复杂性。我们的算法具有$ o（\ min（k，\ log_w n））$ rmr段落的复杂性和$ o（f + \ min（k，k，\ log_w n））$ rmr super-passage复杂性，其中$ k $是concrustrent contruntrent controperes（point contention），$ w $是clipsisters and $ pripters和$ f的尺寸（点数），$ w $是$ f ins and $ f ins and $ f。根据$ w =θ（\ log n）$的标准假设，这些边界转化为worst-case $ o（\ frac {\ log n} {\ log \ log \ log \ log n}）$ vassage复杂度和$ o（f + \ frac {\ log n}我们的关键构件是： * A $ D $ - 过程可流产的RME算法，对于$ d \ leq W $，带有$ o（1）$ passage复杂性和$ o（1+f）$ super-passage复杂性。我们通过使用Fetch-and-Add（FAA）原始性获得此算法，与使用Fetch-and商店（FAS/SHAP）的RME上的先前工作不同。 *一种通用转换，将$ b <w $的通道复杂性转换为可流行的RME算法，转换为可流产的RME锁定，而通道复杂度为$ O（\ min（k，b））$。
We present the first recoverable mutual exclusion (RME) algorithm that is simultaneously abortable, adaptive to point contention, and with sublogarithmic RMR complexity. Our algorithm has $O(\min(K,\log_W N))$ RMR passage complexity and $O(F + \min(K,\log_W N))$ RMR super-passage complexity, where $K$ is the number of concurrent processes (point contention), $W$ is the size (in bits) of registers, and $F$ is the number of crashes in a super-passage. Under the standard assumption that $W=Θ(\log N)$, these bounds translate to worst-case $O(\frac{\log N}{\log \log N})$ passage complexity and $O(F + \frac{\log N}{\log \log N})$ super-passage complexity. Our key building blocks are: * A $D$-process abortable RME algorithm, for $D \leq W$, with $O(1)$ passage complexity and $O(1+F)$ super-passage complexity. We obtain this algorithm by using the Fetch-And-Add (FAA) primitive, unlike prior work on RME that uses Fetch-And-Store (FAS/SWAP). * A generic transformation that transforms any abortable RME algorithm with passage complexity of $B < W$, into an abortable RME lock with passage complexity of $O(\min(K,B))$.
