Hostname: page-component-7b7567c8c-fvjsw Total loading time: 0 Render date: 2026-11-16T14:44:00.966Z Has data issue: false hasContentIssue false

On a functional equation arising in the analysis of a protocol for a multi-access broadcast channel

Published online by Cambridge University Press:  01 July 2016

Guy Fayolle*
Affiliation:
INRIA
Philippe Flajolet*
Affiliation:
INRIA
Micha Hofri*
Affiliation:
Technion-Israel Institute of Technology
*
∗INRIA, Domaine de Voluceau, BP 103, 78153 Le Chesnay Cedex, France.
∗INRIA, Domaine de Voluceau, BP 103, 78153 Le Chesnay Cedex, France.
∗∗Computer Science Department, Technion–Israel Institute of Technology, Haifa 32000, Israel.

Abstract

We analyse a stack protocol of the Capetanakis–Tsybakov–Mikhailov type for resolving collisions in a random multiple-access channel. We obtain a functional equation for the generating function of the expected collision resolution interval (CRI) durations, which is non-local with a non-commutative iteration semigroup. Using Mellin transform techniques and geometric properties of the iteration semigroup we show that for arrival rates smaller than a fixed threshold, the mean CRI duration for n initial colliders is asymptotically proportional to n. Ergodicity conditions are also demonstrated.

Information

Type
Research Article
Copyright
Copyright © Applied Probability Trust 1986 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Article purchase

Temporarily unavailable