Technical Report CS0777

TR#:CS0777
Class:CS
Title: A LOWER BOUND ON WAIT-FREE COUNTING.
Authors: S. Moran and G. Taubenfeld
PDFCS0777.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 wait-free counting protocol, assuming that the basic atomic operation of a process is a read-modify-write 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 wait-free 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.

CopyrightThe 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/cgi-bin/tr-info.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

Computer science department, Technion
admin