Technical Report CS0237

Title: On The Capacity of a Collision Channel under Stack-Based Collision Resolution Algorithm
Authors: Guy Fayolle and Micha Hofri
Abstract: The Capetanakis-Tsybakov-Mikhailov (CTM) Collision Resolution Algorithm and several cognate varieties has baen suggested for the management of a single communications medium, for an infinite population of message generators. We analyse the performance of these algorithms under state independent message arrival processes. The only quantity that is actually computed is the expected time the algorithms require to resolve a collision involving a given number of messages, and this is sufficient to find the maximum traffic the channel will bear with finite delay. In a companion paper [3J we analyse the functional equations developed here and also perform asymptotic analysis.

Key words and phrases: Collision Channel, CSMA, Feedback Channel, Local network, channel capacity, collision resolution.

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 (, rather than to the URL of the PDF or PS files directly. The latter URLs may change without notice.

To the list of the CS technical reports of 1982
To the main CS technical reports page

Computer science department, Technion