Abstract
Approximate counting is a probabilistic algorithm for keeping track of large numbers of events by means of a counter of limited range. In this paper we present an analysis of this algorithm using the elementary theory of martingales. The methods are also applicable to the analysis of the counter which occurs in the exponential back off protocol
†This research was supported in part by a grant from the Air Force Office of Scientific Research (AFOSR 82-0167) and was carried out at INRIA (France) while the author held the position of “Professeur Invite” in Project Meval under the direction of Guy Fayolle
†This research was supported in part by a grant from the Air Force Office of Scientific Research (AFOSR 82-0167) and was carried out at INRIA (France) while the author held the position of “Professeur Invite” in Project Meval under the direction of Guy Fayolle
Notes
†This research was supported in part by a grant from the Air Force Office of Scientific Research (AFOSR 82-0167) and was carried out at INRIA (France) while the author held the position of “Professeur Invite” in Project Meval under the direction of Guy Fayolle