A replicated finite state machine lock service facilitates resource sharing in a distributed system. A lock request from a client identifies a resource and a lock-mode, and requests a leaseless lock on the resource. The service uses client instance identifiers to categorize requests as duplicate, stale, abandoned, or actionable. A lock may be abandoned when a client holding the lock goes down. After a per-client abandonment timer expires, the lock service may treat any exclusive lock granted to the client as abandoned, and treat any non-exclusive lock granted to the client as unlocked. The service tries to notify a lock-holding client if another client requests the same lock, and treats the lock as abandoned if the notification attempt fails. An abandoned read lock is granted to a different client on request. An abandoned write lock is granted or refused depending on whether the requesting client accepts abandoned write locks.