In this paper, we study the impact of delay constraints on the throughput of a queued multiple-access system. We model the channel as a collision channel with carrier sense to capture the inherent information sharing due to broadcast nature of the wireless channels. Since the queue state information is unknown to other nodes and a delay-bounded communication is desired, we show that a fraction of throughput is lost as protocol overhead. More importantly, we show that there is a tradeoff between protocol overhead and queuing delay; larger delays allowing smaller overheads. In addition, we show that larger network loads can also be used to reduce protocol overhead, which is in direct contrast of the behavior exhibited by commonly used medium access protocols.