Distributed lock service

Design a general-purpose distributed lock service (a Chubby/etcd-style coordination primitive) that many internal teams will use for leader election, config rendezvous, and mutual exclusion around non-idempotent operations. Requirements: locks must be safe (no two holders believe they hold the same lock in a way that can corrupt data), highly available (survive losing a minority of nodes), support tens of thousands of locks and ~100k lock ops/sec, give clients fast lock acquisition in their home region, and degrade safely when a client is partitioned from the service (the client must stop acting as holder, not keep going). Cover the data model, how you keep the lock state consistent, lease vs session semantics, the notification mechanism for 'lock released', and what you hand the client so a slow/paused holder can't corrupt the protected resource.