Recent years have seen tremendous growth in the deployment of Wireless Local Area Networks (WLANs). An important design issue in such networks is that of distributed scheduling. The lack of centralized control leads to multiple users competing for channel access. This leads to significant throughput degradation. Existing approaches, such as the slotted Aloha protocol and IEEE 802.11 DCF, also fail to provide differentiated service to users. The upcoming IEEE 802.11e Enhanced DCF incorporates additional mechanisms to provide support for service differentiation. However, the level of differentiation achieved with these mechanisms is difficult to quantify. In this paper, we propose a class of distributed scheduling algorithms, Regulated Contention Medium Access Control (RCMAC), which provides dynamic prioritized access to users for service differentiation in a quantifiable manner. Furthermore, by regulating multi-user contention, RCMAC achieves higher throughput when traffic is bursty, as is typically the case. In addition to WLANs, the basic concepts of RCMAC have applications in ad hoc networks and emerging sensor networks.