Tournaments for mutual exclusion: verification and concurrent complexity

被引：5
|
作者：
Hesselink, Wim H. [1 ]
机构：
[1] Univ Groningen, Johann Bernoulli Inst Math & Comp Sci, POB 407, NL-9700 AK Groningen, Netherlands
来源：
FORMAL ASPECTS OF COMPUTING | 2017年 / 29卷 / 05期
关键词：
Mutual exclusion; UNITY; Concurrency; Shared variables; Concurrent complexity; ALGORITHM;
D O I：
10.1007/s00165-016-0407-x
中图分类号：
TP31 [计算机软件];
学科分类号：
081202 ; 0835 ;
摘要：
Given a mutual exclusion algorithm MXd for threads, a mutual exclusion algorithm for threads can be built in a tree of degree d with N leaves, with the critical section at the root of the tree. This tournament solution seems obviously correct and efficient. The present note proves the correctness, and formalizes the efficiency in terms of concurrent complexity by means of Bounded Unity. If the tree is balanced, the throughput is logarithmic in N. If moreover MXd satisfies FCFS (first-come first-served), the worst case individual delay of the tournament algorithm is of order N. This is optimal.
引用
收藏
页码：833 / 852
页数：20
相关论文
共 50 条
  • [11] Recoverable mutual exclusion
    Golab, Wojciech
    Ramaraju, Aditya
    DISTRIBUTED COMPUTING, 2019, 32 (06) : 535 - 564
  • [12] Recoverable Mutual Exclusion
    Golab, Wojciech
    Ramaraju, Aditya
    PROCEEDINGS OF THE 2016 ACM SYMPOSIUM ON PRINCIPLES OF DISTRIBUTED COMPUTING (PODC'16), 2016, : 65 - 74
  • [13] Highly concurrent group mutual exclusion algorithms based on ticket orders
    Takamura, M
    Igarashi, Y
    IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS, 2004, E87D (02) : 322 - 329
  • [14] Randomized mutual exclusion with sub-logarithmic RMR-complexity
    Danny Hendler
    Philipp Woelfel
    Distributed Computing, 2011, 24 : 3 - 19
  • [15] Randomized mutual exclusion with sub-logarithmic RMR-complexity
    Hendler, Danny
    Woelfel, Philipp
    DISTRIBUTED COMPUTING, 2011, 24 (01) : 3 - 19
  • [16] Mutual exclusion by four shared bits with not more than quadratic complexity
    Hesselink, Wim H.
    SCIENCE OF COMPUTER PROGRAMMING, 2015, 102 : 57 - 75
  • [17] From Mutual Exclusion to Group Mutual Exclusion: A Token-Based General Scheme
    Swaroop, Abhishek
    Singh, Awadhesh Kumar
    2012 2ND IEEE INTERNATIONAL CONFERENCE ON PARALLEL, DISTRIBUTED AND GRID COMPUTING (PDGC), 2012, : 645 - 650
  • [18] Construction and Formal Verification of a Fault-Tolerant Distributed Mutual Exclusion Algorithm
    Shishkin, Evgeniy
    PROCEEDINGS OF THE 16TH ACM SIGPLAN INTERNATIONAL WORKSHOP ON ERLANG (ERLANG '17), 2017, : 1 - 12
  • [19] Randomized Abortable Mutual Exclusion with Constant Amortized RMR Complexity on the CC Model
    Giakkoupis, George
    Woelfel, Philipp
    PROCEEDINGS OF THE ACM SYMPOSIUM ON PRINCIPLES OF DISTRIBUTED COMPUTING (PODC'17), 2017, : 221 - 229
  • [20] Group Mutual Exclusion Based on Priorities
    Cenci, Karina M.
    Ardenghi, Jorge R.
    JOURNAL OF COMPUTER SCIENCE & TECHNOLOGY, 2011, 11 (01): : 21 - 26
12345