> If you can sacrifice more, you can get Single Paxos

What do you mean? Single Decree Paxos is linearizable so it's consistent. When the multi-key updates are necessary - they can be implemented with client-side transactions such as 2PC, RAMP or Percolator.

Even with Raft we in the same situation. Once the data overgrows the size of one machine we need to shard them. As a result some keys can live on different shards and we need cross shards transactions to do multi-key updates :)