{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,22]],"date-time":"2026-08-22T01:01:02Z","timestamp":1787360462047,"version":"build-2736575974"},"reference-count":18,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[1989,8]]},"abstract":"<jats:p>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.<\/jats:p>","DOI":"10.1137\/0218054","type":"journal-article","created":{"date-parts":[[2005,2,24]],"date-time":"2005-02-24T06:32:44Z","timestamp":1109226764000},"page":"777-791","source":"Crossref","is-referenced-by-count":8,"title":["Ultimate Characterizations of the Burst Response of an Interval Searching Algorithm: A Study of a Functional Equation"],"prefix":"10.1137","volume":"18","author":[{"given":"Philippe","family":"Jacquet","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Wojciech","family":"Szpankowski","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,13]]},"reference":[{"key":"R1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1984.1056956"},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1979.1056093"},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4899-2691-3"},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-82456-2_16"},{"key":"R5","unstructured":"R. Gallager,  Conflict resolution in a random access broadcast network,  Proc. AFOSR Workshop in Communication Theory and Applications,  1978,  74\u201376"},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1145\/3828.214125"},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1145\/23005.23006"},{"key":"R8","volume-title":"Applied and computational complex analysis. Vol. 2","author":"Henrici Peter","year":"1977"},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1109\/TCOM.1986.1096639"},{"key":"R10","unstructured":"P. Jacquet, W. Szpankowski,  Ultimate characterizations of the burst response of interval searching algorithm, CSD TR-711, Purdue University, West Lafayette, IN,  1987"},{"key":"R11","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0022669"},{"key":"R12","volume-title":"The art of computer programming. Volume 3","author":"Knuth D.","year":"1973"},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1137\/0608021"},{"key":"R14","doi-asserted-by":"publisher","DOI":"10.1007\/BF00264363"},{"key":"R15","first-page":"259","volume":"14","author":"Tsybakov B. S.","year":"1978","journal-title":"Problem Inform. Transmission"},{"key":"R16","first-page":"305","volume":"16","author":"Tsybakov B. S.","year":"1980","journal-title":"Problem Inform. Transmission"},{"key":"R17","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-13345-3_48"},{"key":"R18","doi-asserted-by":"publisher","DOI":"10.1137\/0215032"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/0218054","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:44:36Z","timestamp":1787337876000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/0218054"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1989,8]]},"references-count":18,"journal-issue":{"issue":"4","published-print":{"date-parts":[[1989,8]]}},"alternative-id":["10.1137\/0218054"],"URL":"https:\/\/doi.org\/10.1137\/0218054","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[1989,8]]}}}