Methods and apparatus for a semaphore mechanism in a distributed computing environment are disclosed. A state manager coordinating accesses to objects from distributed clients implements programmatic interfaces for semaphore operations. A client process submits a permit record directed to a semaphore instance protecting a shared resource. The client process receives a representation of permit records associated with the resource. The permit records provide an indication of an order in which permit requests for the resource were processed. The client process uses the permit records to determine whether it has been granted a permit, and if it determines that the permit has been granted, performs operations on the resource.