For wireless systems in which randomly arriving devices attempt to transmit a fixed payload to a central receiver, we develop a framework to characterize the system throughput as a function of arrival rate and per-user data rate. The framework considers both coordinated transmission (where devices are scheduled) and uncoordinated transmission (where devices communicate on a random access channel and a provision is made for retransmissions). Our main contribution is a novel characterization of the optimal throughput for the case of uncoordinated transmission and a strategy for achieving this throughput that relies on overlapping transmissions and joint decoding. Simulations for a noise-limited cellular network show that the optimal strategy provides a factor of four improvement in throughput compared to slotted aloha. We apply our framework to evaluate more general system-level designs that account for overhead signaling. We demonstrate that, for small payload sizes relevant for machine-to-machine (M2M) communications (200 bits or less), a one-stage strategy, where identity and data are transmitted optimally over the random access channel, can support at least twice the number of devices compared to a conventional strategy, where identity is established over an initial random-access stage and data transmission is scheduled.