Efficient randomized test-and-set implementations

作     者：Giakkoupis, George Woelfel, Philipp 

作者机构：INRIA Rennes France Univ Calgary Calgary AB Canada 

出 版 物：《DISTRIBUTED COMPUTING》 (分布式计算)

年 卷 期：2019年第32卷第6期

页      面：565-586页

核心收录：

学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：We thank Dan Alistarh for pointing out Styer and Peterson’s Ω (log n) space lower bound for deadlock-free leader election . We also thank the anonymous reviewers for their helpful feedback 

主　　题：Distributed computer systems 

摘      要：We study randomized test-and-set (TAS) implementations from registers in the asynchronous shared memory model with n processes. We introduce the problem of group election, a natural variant of leader election, and propose a framework for the implementation of TAS objects from group election objects. We then present two group election algorithms, each yielding an efficient TAS implementation. The first implementation has expected max-step complexity O(log* k) in the location-oblivious adversary model, and the second has expected max-step complexity O(log log k) against any read/write-oblivious adversary, where k = n is the contention. These algorithms improve the previous upper bound by Alistarh and Aspnes (in: Proceedings of the 25th International Symposium on Distributed Computing, 2011) of O(log log n) expected max-step complexity in the oblivious adversary model. We also propose a modification to a TAS algorithm devised by Alistarh, Attiya, Gilbert, Giurgiu, and Guerraoui (in: Proceedings of the 24th International Symposium on Distributed Computing, DISC 2010) for the strong adaptive adversary, which improves its space complexity from super-linear to linear, while maintaining its O(log n) expected max-step complexity. We then describe how this algorithm can be combined with any randomized TAS algorithm that has expected max-step complexity T (n) in a weaker adversary model, so that the resulting algorithm has O(log n) expected max-step complexity against any strong adaptive adversary and O(T (n)) in the weaker adversary model. Finally, we prove that for any randomized 2-process TAS algorithm, there exists a schedule determined by an oblivious adversary such that with probability at least 1/4t one of the processes needs at least t steps to finish its TAS operation. This complements a lower bound by Attiya and Censor-Hillel (SIAM J Comput 39(8):3885-3904, 2010) on a similar problem for n = 3 processes.