On the throughput of degenerate intersection and first-come first-served collision resolution algorithms
Shivendra S. Panwar, Don Towsley, Jack K. Wolf · IEEE Transactions on Information Theory · 1985
It is shown that, for a ternary feedback random access channel with a Poisson arrival process,0.5is an upper bound to the throughput for all "degenerate intersection" algorithms (DIA's) and first-come first-served algorithms (FCFSA's). As a by-product, the nested FCFSA with the largest throughput is found for the random access channel with a Bernoulli arrival process with parameterp. Forp \geq 0.018, this algorithm has the highest throughput over all DIA's and FCFSA's. Lastly, it is shown that. for some values ofp, a non-DIA, non-FCFSA has a higher throughput than the optimum DIA or FCFSA.