Patent attributes
A database service may store data on behalf of clients in multiple replicas on respective computing nodes in different availability zones. The service may employ a lease based protocol to select a master replica for a replica group that does not depend on an external service, but is managed by client processes executing on the database hosts themselves. To assume the role of a primary (writable) master for a database table, a master host may acquire a lease by updating a lease record for the table that is maintained in a consistent data store. If the master host fails to renew the lease within a pre-determined lease period, it may revert to read-only mode, and a secondary master host, having determining (based on the lease record) that the primary master no longer holds the lease, may assume the role of primary master by acquiring the lease and making itself writable.