A method implemented in a computer infrastructure having computer executable code tangibly embodied on a computer readable medium. The computer executable code is operable to dynamically adjust quorum requirements for a voting set V of a server cluster, including a plurality of servers, to ensure that a response of the server cluster to a client request remains Byzantine fault tolerant when at least one of: a failed server of the server cluster is replaced with at least one new server, such that a total set S of servers that have ever been members of the server cluster is increased, and an existing server is removed from the voting set V.