Ultimate Characterizations of the Burst Response of an Interval Searching Algorithm: A Study of a Functional Equation
Philippe Jacquet, Wojciech Szpankowski · SIAM Journal on Computing · 1989
The interval searching algorithm for broadcast communications of Gallager and Tsybakov and Mikhailov is analyzed. Ultimate characterizations of the burst response of the algorithm, that is, when the number of collided packets becomes large is presented. Three quantities are of interest: the conflict resolution interval (CRI); the fraction of the resolved interval (RI); and the number of resolved packets (RP). If n is the multiplicity of a conflict, then it is proved that the mth moments of CRI, RI, and RP are $O(\log ^m n)$, $O(n^{ - m} )$ and $O(1)$, respectively. In addition, for the first two moments of these parameters precise asymptotic approximations are presented. The methodology proposed in this paper is applicable to asymptotic analysis of any problem that can be reduced to a solution of the functional equation$f(x) = 2^s \cdot f({x / 2}) \cdot a(x) + b(x)$ , where s is an integer and $a(x),b(x)$ are given functions.