A multiple access protocol that is particularly suitable for cellular Internet access and satellite-based networks with on-board processing is developed. The basic idea is that when a user wishes to send a message, it transmits with a probability p/sub access/ that depends on the load on the channel. Under conditions of low load, the probability p/sub access/ approaches 1, while at high load p/sub access/ is relatively low. This media access control protocol guarantees high channel utilization at high load, as well as low delay at low load periods. Using the statistical usage of the shared channel, the load is estimated with certain uncertainty. Our analysis shows that using the statistical usage of the shared channel, the optimal access probability can be well estimated for a broad class of load distribution patterns. In addition, we propose to use a central station to broadcast the value of p/sub access/ in networks with poor collision detection capability, or long feedback delay. The proposed method is particularly suitable for shared channels with poor collision detection capability, under conditions of bursty traffic and a large number of users. Examples for such channels are the reservation channel in satellite-based networks with on-board processing, and the control channel in cellular networks. Hence, the proposed method can be used for cellular Internet access and for accessing public satellite-based networks. The broadcast mechanism that already exists in such networks can be used to inform the users the dynamic access probability.