For context, the problem is basically the one I described in my comment on
CASSANDRA-9649 and for which I suggested reverting CASSANDRA-7801.
Now, I was kind of wrong about reverting
CASSANDRA-7801 since since CASSANDRA-9649 we were relying on ClientState.getTimestamp() to give use timestamp that were unique for the running VM, which meant we can't blindly revert CASSANDRA-7801.
What I think is the simplest solution however is to stop relying on that property (of ClientState.getTimestamp()) for the uniqueness of our ballots, but instead randomize the non-timestamp parts of the ballot for every new ballot. With that, we don't have to revert
CASSANDRA-7801, we just have to ensure that if we use the last known proposal timestamp (i.e. if whomever clock generated that timestamp is "in the future"), we don't persist it in the local clock (this in turn means the timestamp might not be unique in the VM for 2 concurrent paxos operation and hence the need to randomize the rest of the UUID).
I've pushed a patch for this for 2.1. I'll attach branches for 2.2+ with tests tomorrow (but was waiting on the 2.1 results before doing that) but I don't think the modified code has changed since 2.1 so marking ready for review in the meantime.