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 条
[21]   A visit to mutual exclusion in seven dates [J].
Raynal, Michel ;
Taubenfeld, Gadi .
THEORETICAL COMPUTER SCIENCE, 2022, 919 :47-65
[22]   Fast mutual exclusion by the Triangle algorithm [J].
Hesselink, Wim H. ;
Buhr, Peter A. ;
Dice, David .
CONCURRENCY AND COMPUTATION-PRACTICE & EXPERIENCE, 2018, 30 (04)
[23]   Opportunistic Mutual Exclusion [J].
Srinivasan, Karthi ;
Moses, Yoram ;
Manohar, Rajit .
2023 28TH IEEE INTERNATIONAL SYMPOSIUM ON ASYNCHRONOUS CIRCUITS AND SYSTEMS, ASYNC, 2023, :1-9
[24]   Superstabilizing mutual exclusion [J].
Herman, T .
DISTRIBUTED COMPUTING, 2000, 13 (01) :1-17
[25]   Mutual Exclusion in MANETs Using Quorum Agreements [J].
Sharma, Bharti ;
Bhatia, Ravinder Singh ;
Singh, Awadhesh Kumar .
PROCEEDINGS OF THE NATIONAL ACADEMY OF SCIENCES INDIA SECTION A-PHYSICAL SCIENCES, 2016, 86 (02) :169-186
[26]   A mutual exclusion algorithm with optimally bounded bypasses [J].
Alagarsamy, K .
INFORMATION PROCESSING LETTERS, 2005, 96 (01) :36-40
[27]   Symmetric Tokens based Group Mutual Exclusion [J].
Aravind, Alex .
49TH INTERNATIONAL CONFERENCE ON PARALLEL PROCESSING WORKSHOP PROCEEDINGS, ICPP 2020, 2020,
[28]   Mutual Exclusion and its Variants Survey in MANETs [J].
Gupta, Nikhil ;
Khana, Ashish ;
Gupta, Sagar ;
Aggarwal, Prashant .
PROCEEDINGS OF THE 10TH INDIACOM - 2016 3RD INTERNATIONAL CONFERENCE ON COMPUTING FOR SUSTAINABLE GLOBAL DEVELOPMENT, 2016, :912-917
[29]   The Average Message Complexity Analysis for Different Distributed Mutual Exclusion Site-tolerant Ways [J].
Li, MeiAn ;
Li, Wei ;
Ma, Dong .
ACHIEVEMENTS IN ENGINEERING MATERIALS, ENERGY, MANAGEMENT AND CONTROL BASED ON INFORMATION TECHNOLOGY, PTS 1 AND 2, 2011, 171-172 :675-678
[30]   Correctness and concurrent complexity of the Black-White Bakery Algorithm [J].
Hesselink, Wim H. .
FORMAL ASPECTS OF COMPUTING, 2016, 28 (02) :325-341
12345