TR#:  CS0777 
Class:  CS 
Title:  A LOWER BOUND ON WAITFREE
COUNTING. 
Authors:  S. Moran and G. Taubenfeld 
CS0777.pdf  
Abstract: 
A counting protocol (mod m) consists of shared memory bits  referred to as the counter  and of a procedure for incrementing the counter value by 1 (mod m). The procedure may be executed by many processes concurrently. It is required to satisfy a very weak correctness requirement, namely: the counter is required to show a correct value only in quiescent states  states in which no process is incrementing the counter. Special cases of counting protocols are ``counting networks'' [AHS91] and ``concurrent counters'' [MTY92]. We consider the problem of implementing a waitfree counting protocol, assuming that the basic atomic operation of a process is a readmodifywrite on a single bit. Let flip(Pr) be the maximum number of times a single increment operation changes the counter bits in a counting protocol Pr. Our main result is: In any waitfree counting protocol Pr which counts modulo m,m divides 2^{Flip(Pr)}. Thus, Flip(Pr) \Geq \Log M and m is the power of 2. By a result of [MTY92] the above lower bound on Flip(Pr) is tight. This result provides interesting generalizations of lower bounds and impossibility results for counting and smoothing networks.

Copyright  The above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information 
Remark: Any link to this technical report should be to this page (http://www.cs.technion.ac.il/users/wwwb/cgibin/trinfo.cgi/1993/CS/CS0777), rather than to the URL of the PDF files directly. The latter URLs may change without notice.
To the list of the CS technical reports of 1993
To the main CS technical reports page