Highly-fair bakery algorithm using symmetric tokens

被引：4
作者：
Aravind, Alex A. [1 ]
机构：
[1] Univ No British Columbia, Comp Sci Program, Prince George, BC V2L 5P2, Canada
来源：
INFORMATION PROCESSING LETTERS | 2010年 / 110卷 / 23期
关键词：
Concurrency; Distributed algorithm; Mutual exclusion; Bakery algorithm; Fairness; Bounded timestamps;
D O I：
10.1016/j.ipl.2010.09.004
中图分类号：
TP [自动化技术、计算机技术];
学科分类号：
0812 ;
摘要：
This note proposes a new version of the bakery algorithm that: (i) assures fair tie-breaking when two or more processes choose same token number; and (ii) bounds the token numbers within the range vertical bar-n, n vertical bar. The algorithm is simple and uses one additional shared bit. (C) 2010 Elsevier B.V. All rights reserved.
引用
收藏
页码：1055 / 1060
页数：6
相关论文
共 16 条
[1]  
Abraham U., 1993, P CONC SPEC PROGR WO, P7
[2]  
Ben-Ari, 2006, PRINCIPLES CONCURREN
[3]  
Ben-Ari M., 2008, Principles of the Spin Model Checker
[4]   SOLUTION OF A PROBLEM IN CONCURRENT PROGRAMMING CONTROL [J].
DIJKSTRA, EW .
COMMUNICATIONS OF THE ACM, 1965, 8 (09) :569-&
[5]  
FISHER KJ, 1989, ACM TOPLAS, V11, P90
[6]   BOUNDED TIME-STAMPS [J].
ISRAELI, A ;
LI, M .
DISTRIBUTED COMPUTING, 1993, 6 (04) :205-209
[7]   NEW SOLUTION OF DIJKSTRAS CONCURRENT PROGRAMMING PROBLEM [J].
LAMPORT, L .
COMMUNICATIONS OF THE ACM, 1974, 17 (08) :453-455
[8]   EMBEDDED MULTICORE PROCESSORS AND SYSTEMS [J].
Levy, Markus ;
Conte, Thomas M. .
IEEE MICRO, 2009, 29 (03) :7-9
[9]  
Lynch N., 1996, Distributed Algorithms
[10]   STARVATION-FREE SOLUTION TO THE MUTUAL EXCLUSION PROBLEM [J].
MORRIS, JM .
INFORMATION PROCESSING LETTERS, 1979, 8 (02) :76-80
12