[twokei]

It would be possible if say for example, the database was fully replicated in a masterless fashion.

The tradeoff is slower writes (there are ways to make it so that the more nodes you replicate across, write latency won't be affected!).

Reads will scale linearly for the more nodes you replicate across.

So, the novelty in some sense is fast replication of data in a masterless fashion (without any leader such as, for example in Raft or Paxos).

If this protocol was surprisingly simple (which dumbs down the complexity of the software significantly), would you pay for this sort of database?

[SamReidHughes]

Yeah, no, the database being replicated "in a masterless fashion" doesn't help. The problem is that under some network partition conditions, you can't do some writes or any writes, unless you want to sacrifice resilience and/or consensus.

[twokei]

Why wouldn't there be failures only under a complete network partition? So long as one node in one partition may communicate with another node in another partition, then writes may still be performed.

Availability would be what is sacrificed in the advent that a node is partitioned away from the main network.

[SamReidHughes]

Only when that's true of those two nodes and no other disjoint subset of nodes.