Thinking about it, your algorithm also does not sound crash-resilient. Specifically, unless you're doing round-trip confirmations, you can easily have different replicas with different (possibly overlapping, possibly disjoint, in weird patterns) sets of changesets applied within a batch. If you have asynchronous replication at all you probably already have to deal with any issues arising from "gaps" in replication on some of the replicas for a single version, but if you don't, be aware that it can be very tricky to deal with properly on recovery. Specifically, if the master applies different transactions (within a batch) to different replicas, then goes down, and you elect a replica that only saw some of the transactions, and there can't be gaps, it's relatively easy to identify which replica is most up-to-date and make that one the leader. But if there can be gaps, there's the possibility that different nodes have different transactions applied, so you'll have to make sure any gaps are filled in before you elect a new leader.

Still, with a total order, it's not that bad, because it's easy to identify gaps; with your algorithm, however, there's no total order between changesets within or across batches (at least, none that I can see in your algorithm), so you won't have any way of knowing whether there are gaps (at least, not without doing something silly like broadcasting every changeset)! Adding a total order seems like the easiest way to resolve that, but like I said even that case can be tricky. Also, your algorithm doesn't specify that replicas which receive changesets with batch ids with gaps in them wait to apply them until the gap is filled in (which means they have to know when the previous batch is done), or alternately that before a batch with a new id can be sent from the master all replicas must have synchronously applied all changes within the old batch. I think something like that is a requirement here in order for there not to be potential conflicts on your replicas during replication even if the master doesn't crash.

IMO, doing exactly your algorithm but delaying replication or transaction confirmation until a specified amount of time has passed (say 10 ms), then synchronously sending the entire changeset and incrementing the batch id (aka group commit) is a much better idea. You exchange marginally worse latency (and more bursty network usage) for a far less complex update scenario (yes, you're back to having a total ordering on writes at replicas you need to follow, but you can include multiple changesets in the batch). You can also have your master monitor number of writes and only turn on group commit if there's unusually high write volume.

(Also, belatedly reading one of your other comments more carefully, I'm fairly confident commitCount will also not work correctly if changesets can be applied out of order on different replicas, even if there was no data loss, since the same commitCount could include different sets of changesets at any one time).