TY - JOUR
T1 - Waiting in concurrent algorithms
AU - Taubenfeld, Gadi
N1 - Publisher Copyright:
© 2018, Springer-Verlag GmbH Austria, part of Springer Nature.
PY - 2019/1/17
Y1 - 2019/1/17
N2 - Between the two extremes, lock-based algorithms, which involve “a lot of waiting”, and wait-free algorithms, which are “free of locking and waiting”, there is an interesting spectrum of different levels of waiting. This unexplored spectrum is formally defined and its properties are investigated. New progress conditions, called k-waiting, for k≥ 0 , which are intended to capture the “amount of waiting” of processes in asynchronous concurrent algorithms, are introduced. To illustrate the utility of the new conditions, they are used to derive new lower and upper bounds, and impossibility results for well-known basic problems such as consensus, election, renaming and mutual exclusion. Furthermore, the relation between waiting and fairness is explored.
AB - Between the two extremes, lock-based algorithms, which involve “a lot of waiting”, and wait-free algorithms, which are “free of locking and waiting”, there is an interesting spectrum of different levels of waiting. This unexplored spectrum is formally defined and its properties are investigated. New progress conditions, called k-waiting, for k≥ 0 , which are intended to capture the “amount of waiting” of processes in asynchronous concurrent algorithms, are introduced. To illustrate the utility of the new conditions, they are used to derive new lower and upper bounds, and impossibility results for well-known basic problems such as consensus, election, renaming and mutual exclusion. Furthermore, the relation between waiting and fairness is explored.
KW - Consensus
KW - Election
KW - Enabled process
KW - Enabling step
KW - Locks
KW - Mutual exclusion
KW - Renaming
KW - Synchronization
KW - Wait-freedom
KW - k-waiting
UR - http://www.scopus.com/inward/record.url?scp=85045910063&partnerID=8YFLogxK
U2 - 10.1007/s00607-018-0618-5
DO - 10.1007/s00607-018-0618-5
M3 - ???researchoutput.researchoutputtypes.contributiontojournal.article???
AN - SCOPUS:85045910063
SN - 0010-485X
VL - 101
SP - 39
EP - 57
JO - Computing (Vienna/New York)
JF - Computing (Vienna/New York)
IS - 1
ER -