We discuss a low-cost consistency protocol for replicated metadata in cluster-based storage systems. Our goal in maintaining the consistency is to minimize the efforts for porting applications from single systems to the cluster-based environment. The access patterns to the replicated metadata in recent cluster-based storage systems offer a new opportunity for strong consistency without sacrificing performance in common cases. We design and implement a protocol for the atomicity, serialization and recovery of operations in the face of arbitrary sequences of failures. The correctness of the protocol is checked with randomized failure injections into a prototype implementation. We measure the impact of the consistency protocol on the performance and scalability of an example cluster-based file system. The measurement of micro benchmarks shows that the protocol adds little overhead to common operations; while the measurement of trace-based operation mixes shows a speedup of 15.7 in a cluster of 16 nodes.