Example distributed storage systems, replication managers, and methods provide barriers for dependent data operations among sharded data stores. Shard operation logs may be associated with different shards and storage nodes. Dependent data operations may be identified in each shard and data operation entries corresponding to dependency sets for those dependent data operations may be determined. Log-based operations may be executed by delaying execution of the dependent data operations in all shards until the dependency set data operations in all shards are completed.