TY - JOUR
T1 - Threshold counters with increments and decrements
AU - Busch, Costas
AU - Demetriou, Neophytos
AU - Herlihy, Maurice
AU - Mavronicolas, Marios
N1 - Funding Information:
A preliminary version of this work appears in the Proceedings of the 6th International Colloquium on Structural Information and Communication Complexity, pp. 47–61, Proceedings in Informatics 5, Carleton Scienti5c, Lacanau, France, June=July 1999. This work has been supported by NSF grant DMS-9505949. ∗Corresponding author. E-mail address: mavronic@turing.cs.ucy.ac.cy (M. Mavronicolas). 1Part of the work was performed while at Department of Computer Science, Brown University. 2Part of the work was performed while at Department of Computer Science and Engineering, University of Connecticut.
PY - 2002/1/6
Y1 - 2002/1/6
N2 - A threshold counter is a shared data structure that assumes integer values. It provides two operations: Increment changes the current counter value from v to v+1, while Read returns the value [v/w], where v is the current counter value and w is a fixed constant. Thus, the Read operation returns the "approximate" value of the counter to within the constant w. Threshold counters have many potential uses, including software barrier synchronization. Threshold networks are a class of distributed data structures that can be used to construct highly-concurrent, low-contention implementations of shared threshold counters. In this paper, we give the first proof that any threshold network construction of a threshold counter can be extended to support a Decrement operation that changes the counter value from v to v-1.
AB - A threshold counter is a shared data structure that assumes integer values. It provides two operations: Increment changes the current counter value from v to v+1, while Read returns the value [v/w], where v is the current counter value and w is a fixed constant. Thus, the Read operation returns the "approximate" value of the counter to within the constant w. Threshold counters have many potential uses, including software barrier synchronization. Threshold networks are a class of distributed data structures that can be used to construct highly-concurrent, low-contention implementations of shared threshold counters. In this paper, we give the first proof that any threshold network construction of a threshold counter can be extended to support a Decrement operation that changes the counter value from v to v-1.
KW - Decrements
KW - Distributed computing
KW - Increments
KW - Threshold and weak threshold networks
KW - Threshold counters
UR - http://www.scopus.com/inward/record.url?scp=0037028443&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0037028443&partnerID=8YFLogxK
U2 - 10.1016/S0304-3975(01)00113-X
DO - 10.1016/S0304-3975(01)00113-X
M3 - Article
AN - SCOPUS:0037028443
SN - 0304-3975
VL - 270
SP - 811
EP - 826
JO - Theoretical Computer Science
JF - Theoretical Computer Science
IS - 1-2
ER -