A computing resource service provider may operate a data storage service configured to provide data storage for one or more customers of the computing resource service provider. The data storage service may store customer data in one or more replicated state machines, where the replicated state machines comprise a plurality of replicated state machine-shards. The replicated state machine-shards may cause the computer system hosting the replicated state machine-shard to transmit a consensus message to other computer system. The consensus message may include utilization information corresponding to the other computer system. The utilization information may be used to calculate a utilization rate for the replicated state machine usable in block allocation operations.