  A multiple access system with bursty data arrivals to the terminals is
considered. The users are frame-synchronized, with variable sized packets
independently arriving in each slot at every transmitter. Each packet needs to
be delivered to a common receiver within a certain number of slots specified by
a maximum delay constraint. The key assumption is that the terminals know only
their own packet arrival process, i.e. the arrivals at the rest of the
terminals are unknown to each transmitter, except for their statistics. For
this interesting distributed multiple access model, we design novel online
communication schemes which transport the arriving data without any outage,
while ensuring the delay constraint. In particular, the transmit powers in each
slot are chosen in a distributed manner, ensuring at the same time that the
joint power vector is sufficient to support the distributed choice of
data-rates employed in that slot. The proposed schemes not only are optimal for
minimizing the average transmit sum-power, but they also considerably
outperform conventional orthogonal multiple access techniques like TDMA.
