A time-slotted multiple access system with bursty data arrivals to the terminals is considered, where variable sized packets independently arrive in each slot at every transmitter. Each packet is required to be delivered to a common receiver within a certain number of slots specified by a maximum delay constraint. 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 probability distributions. For this interesting distributed multiple access model, we design novel online communication schemes which transport the arriving data without any outage, while respecting the delay constraint. In particular, the users choose their respective transmit powers 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 are not only optimal in minimizing the average transmit sum power, but they also considerably outperform conventional orthogonal multiple access techniques like time-division multiple access. An optimal scheme for a multiple access channel with arrivals and time-varying fading is also presented, under a unit slot delay constraint.