On the performance of protocols for collecting responses over a multiple-access channel

Abstract

A generalization of the multiple access problem is considered where it is necessary to identify a subset of the ready users, not all. The problem is motivated by several response collection applications that arise in distributed computing and database systems. In these applications, a collector is interested in gathering a set of responses from a number of potential respondents. The collector and respondents communicate over a shared channel. Three collection objectives are defined, and a suite of protocols that can be used to achieve these objectives is investigated. The protocols are based on the use of polling, time division multiple access (TDMA) and group testing. Using a binomial respondent model, the performance of the protocols is analyzed and, where possible, optimized. The main concern is with cost measures that reflect the computational load placed on the system, as well as the delay incurred for achieving a particular objective.