ON THE PERFORMANCE OF PROTOCOLS FOR COLLECTING RESPONSES OVER A MULTIPLE-ACCESS CHANNEL

We consider a generalisation of the multiple sc cess problem where it is necessary to identify a subset of the ready users, not all. The pro blem is motivated by several ''response collection'' applications that arise in distributed computing and database systems. In these applica tions, a collector is interested in gathering a set of responses from a number of potential respondents. The collector and respondents commu nicate over a shared channel. We define three collection objectives an d investigate a suite of protocols that can be used to achieve these o bjectives. The protocols are based on the use of Polling, TDMA, and Gr oup Testing. Using a binomial respondent model we analyse and, where a pplicable, optimise the performance of the protocols. Our concern is w ith cost measures that reflect the computational load placed on the sy stem, as well as the delay incurred for achieving a particular objecti ve.