Techniques for medium access control. Some techniques include receiving, at a first computing device, a solicitation for at least a first medium access request that specifies at least one time period for transmitting the first medium access request to the second computing device; encoding the first medium access request at least in part by using a compressive sensing encoding technique to obtain a first encoded medium access request; and transmitting the first encoded medium access request to the second computing device during the at least one time period specified in the received solicitation.