Evaluate the impact of async, out of order replication

[adsharma]

https://github.com/adsharma/raft/blob/master/raft/states/leader.py#L168-L180

This loop can send out new log entries before it has received acks from followers. This is not validated for correctness by TLA+ implementation of the raft protocol. See on_response_received() in the same file where acks are processed and leader commitIndex is advanced.

It's possible that multiple followers ack log entry at index 9, but do not agree on log entry at index 7.

The current implementation uses uuids to assign a unique ID to each AppendEntriesRPC. When it receives an ack, it looks up a cache of the uuid -> AppendEntriesRPC to discover which particular log entries were acked. It then advances matchIndex here:

https://github.com/adsharma/raft/blob/master/raft/states/leader.py#L102-L105

It's not clear that this is safe. It's possible that some previous log entries haven't been matched yet if there is packet loss.

We also need to think about all the failure cases, network partition, leader rejoining etc.