History of Research on Random Access

Random Access schemes dynamically assign radio resources to a large set of users, each with relatively bursty traffic.

Prof. Boris Tsybakov describes the history of the development of random access algorithms.

Long version. 5'10" Short version. 2'30"	Although the problem of random access was recognized long before in secret military documents, the academic research gained momentum in the severities with Norman Abramson's paper proposing the ALOHA scheme. The ALOHA scheme had disadvantages. The feedback information on whether a message arrived successfully or not could be used much more efficiently and the system could become unstable. Several improved schemes have been proposed since then. The first one was the tree algorithm. Later came the stack algorithm.	Links to relevant text pages: Random Access. ALOHA, and its Stability. Stack Algorithm.
	Tsybakov conceived the simple basic concept of the Stack algorithm but initially he had great difficulty analyzing its performance theoretically. Vvedenskaya realized how an infinite set of linear equations describing delay and throughput could be solved. Several important papers followed, but the optimum random access scheme, that performs close to the theoretical limits has not yet been found.	Links to relevant text pages: Bibliography. Vvedenskaya.
	Not all problems concerning the existing schemes have been solved. For wireless communication there are particular problems posed by the unreliable channel. Because of intercell interference, noise and fading, it is difficult to distinguish between empty slots and message collisions.	Links to relevant text pages: Propagation. Multipath Fading. Cellular reuse for packet data.