Another solution to livelock

[drmingdrmer]

Update: 2020-03-07:

This approach works only with a set of instances in which every two of them interfere with each other. See @snaury 's comments below: #14 (comment)

The livelock problem

Epaxos specifies that in an SCC, the lowest seq commands should be executed
first.

And if there is a stream of interfering commands, execution thread needs to wait until walking through the entire SCC, before it could execute any command.
This is the livelock.

The solution provided by epaxos is to prioritize completing old commands over
proposing new commands.

This solution might bring in some latency because we need to stop
proposing a new command to break the command chain.

I've been thinking maybe there is some other way to solve the livelock problem.

We assume that all commands mentioned below interfere with each other.

Ordering

Assume we determine the command order in an SCC by a tuple (seq, replicaID).
Then the first command to execute is the one with the least (seq, replicaID)
in an SCC.

Find the first command safe to execute

Provided with a committed, un-executed, interfering command list
CMDs = {Ra.A, Rb.B, Rc.C ..}(Ra.A is a command owned by replica Ra).

Assume that Ra.A has the least (seq, replicaID).

Define a function replicas(cmds): to extract a list of command owner replica,
e.g.: replicas({Ra.A, Rb.B}) = {Ra, Rb}.

Define allDeps, the union of all dependency of CMDs: allDeps = Ra.A.deps U Rb.B.deps U Rc.C.deps...

If CMDs contains only the least seq commands(with two un-executed interfering command Ra.X and Ra.Y:
if Ra.X.seq < Ra.Y.seq, and Ra.Y is in CMDs, Ra.X.seq must be in CMDs):

1. For an un-executed command X not in CMDs and owned by one of replicas(CMDs), we have:
   X.seq > Ra.A.seq.

   Because X.seq is greater than the seq of its preceding command on a same
   replica.

   Thus X should never be executed before Ra.A.

2. For an un-executed command Y not in CMDs and NOT owned by any of replicas(CMDs),
   if replicas(allDeps) ⊆ replicas(CMDs),
   then Y depends on CMDs.

   Because two committed interfering command U and V have at least one dependency
   relationship.

   Thus Y should never be executed before Ra.A.

With (1) and (2), we have the conclusion
that Ra.A is the command that should be executed first.

The abstract algorithm

Initialize an empty CMDs.
Add the next least (seq, replicaID) command and its deps into CMDs.
Repeat this step until we find a CMDs so that replicas(allDeps) ⊆ replicas(CMDs), then
execute the least command in CMDs.

Thus we could execute command even before the entire SCC committed.

Because the number of replicas is finite and small, this process would finish quickly,
even when there are a lot of interfering commands.

In this way searching for an SCC is no more required and there won't be a livelock problem anymore.

[imoraru]

Yes, I think that works. Thanks for the writeup.

[snaury]

Sorry for asking this, but how do you guarantee you have found the least (seq, replicaID)? If I understand correctly, commands don't have seq finalized until they are committed, which may happen in the order of their seq actually decreasing. So, if a replica observes part of a long (potentially infinite) SCC, with dependencies that are not yet committed, how can you be sure those dependencies won't have seq lower than whatever you have observed so far? For example:

A <------------- B <-------------- C <-- ...
|               ^ |               ^ |
\-> ab1 -> ab2 -/ \-> bc1 -> bc2 -/ \-> ...

I know epaxos technically uses optimized dependencies, but I'm trying to consider a more generic dependency graph, which seems possible to generate with 5 replicas (1 replica proposes A, B, C, ... in such a way that they always conflict pairwise, other replicas propose ab1, ab2, bc1, bc2, ... in such a way that it creates a loop for each pair).

In the above graph, after receiving commits for A, B, ab1 and ab2 (the first loop) is it really possible to know whether or not we have observed the least seq value? It seems like bc1 may end up with smaller or larger seq than these 4 during phase 1.

Could you please explain why (1) would hold in such a case? (e.g. bc1 was proposed by the same replica that proposed ab1 or ab2, such that replicas(allDeps) ⊆ replicas(CMDs) holds, but there is no direct conflict with either, except through B)

I'm probably missing something obvious here, or maybe graph like this is too generic/actually impossible?

[imoraru]

As an aside, I would encourage you not to implement the version of the algorithm that requires "seq". Instead, rely on "deps" alone and ack a command to the client only after the command's dependency graph is finalized (or only after it has been executed). To order commands within an SCC use any order criterion as long as it is consistent across replicas. Without "seq", the algorithm has fewer corner cases and better consistency properties.

[snaury]

I'm not sure it would help with solving livelock due to infinitely growing SCC (without stopping new proposes that is), as using seq as a tie breaker may be complicated, but doesn't seem to be the real issue. The problem I'm trying to understand is when we have an incomplete SCC and there are vertices that depend on that SCC, can we even be certain those vertices won't ever become part of it as we receive more vertices of the graph (assuming worst case scenario where commit messages between replicas are severely delayed and arbitrarily reordered), because execution order may reverse depending on it. I'm probably thinking about dependency graphs that are too general though.

Edit: I actually discovered epaxos after reading a recent paper on bpaxos (there was no seq, but no mention of efficient solutions to livelock problem either, which sparked my interest in finding one)

[imoraru]

Well, that's why I called the observation about seq an aside, not a direct answer to your question.
About your question, though. When you talk about ensuring liveness in a real system, solutions usually revolve around better engineering. A simplistic blunt instrument in this case would be to say that replicas stop pre-accepting new commands as long as the dependency graph for their potential dependencies is larger than a certain threshold size. Replicas would thus wait until all of these dependencies finish committing. If implemented poorly, this could significantly reduce your throughput and increase your latency. If implemented well, this would hopefully kick in only so rarely that you wouldn't see its effect in the 99%ile latency.

That said, I do believe that there could very well be ways to tackle this from a theoretical point of view as well. I haven't thought about this too much, but you could try to reason about which dependencies are really necessary, and which dependencies are superfluous. The critical thing in EPaxos is to guarantee that if two commands interfere with each other, one will be in the other's deps graph. They don't need to be in the same SCC, and as you point out, it's better if they are not. Thus, are there some rules that replicas can use to reason "A must be in deps(B), so I won't add B to deps(A)"? I think so.

[drmingdrmer]

Sorry for asking this, but how do you guarantee you have found the least (seq, replicaID)? If I understand correctly, commands don't have seq finalized until they are committed, which may happen in the order of their seq actually decreasing. So, if a replica observes part of a long (potentially infinite) SCC, with dependencies that are not yet committed, how can you be sure those dependencies won't have seq lower than whatever you have observed so far? For example:

Assumes our discussion is only about interfering commands:

I think what confused you is this step:

Add the next least (seq, replicaID) command and its deps into CMDs.

Let me elaborate on it:

Assumes the least (seq, replicaID) command the executing replica has been seen is X.

For an unseen command Y:

• If X does not depends on Y, then Y must depend on X thus y must have greater seq.
• If X depends on Y, thus Y must be finally added into CMDs.

Thus CMDs must contains the least seq command.

[snaury]

If X does not depends on Y, then Y must depend on X thus y must have greater seq.

I'm not sure how to parse this. Are you talking about direct dependencies, or transitive dependencies as well? I assume direct, since in SCC everything depends on everything, in such case here's a counter example:

• We have 5 replicas, initially replicas 1 and 5 are network partitioned
• Replicas 2, 3, 4 had a series of commands making 100 updates to Z, such that the last command is Z.100 (which should be read as command writing to Z with seq==100)
• Replica 1 gets out of being partitioned and receives proposals for 4 commands in rapid succession:
  • Command A is A := X + D
  • Command B is B := A
  • Command C is C := B
  • Command D is D := C
• We assume some messages are lost, delayed and reordered

The sequence of events is as follows (number before the colon is the replica number):

1: comes out of a network partition
1: A B C D proposed in rapid succession
   initially A.0 <- B.1 <- C.2 <- D.3 (pairwise dependencies)
   and also A.0 <- D.3 because read/write to D
1: sends PreAccept messages to 2, 3, 4 but they are delayed and reordered

2: receives PreAccept(B.1, [A]), sends PreAcceptOK(B.1, [A]), i.e. there is no A yet, no updates
3: receives PreAccept(B.1, [A]), sends PreAcceptOK(B.1, [A]), i.e. there is no A yet, no updates
1: receives above replies, have a fast quorum for B.1, deps=[A], will commit eventually

3: receives PreAccept(C.2, [B]), sends PreAcceptOK(C.2, [B]), i.e. there is no B yet, no updates

3: receives PreAccept(D.3, [A, C]), sends PreAcceptOK(D.3, [A, C]), i.e. conflict with C.2, no updates
4: receives PreAccept(D.3, [A, C]), sends PreAcceptOK(D.3, [A, C]), i.e. there is no C yet, no updates
1: receives above replies, have a fast quorum for D.3, deps=[A, C], will commit eventually

5: comes out of a network partition
5: receives PreAccept(A.0, []), sends PreAcceptOK(A.0, []), no updates
4: receives PreAccept(A.0, []), sends PreAcceptOK(A.101, [Z, D]), updated on conflicts with Z.100 and D.3
1: receives above replies, have a quorum for A.101, deps=[Z, D]
1: runs accept phase for A.101 via 4 and 5, will commit eventually

4: receives PreAccept(B.1, [A]), sends PreAcceptOK(B.102, [A]), but it's too late (B.1 already selected)
4: receives PreAccept(C.2, [B]), sends PreAcceptOK(C.103, [B]), updated because it has B.102 internally
1: receives above replies, have a quorum for C.103, deps=[B]
1: runs accept phase for C.103 via 3 and 4, will commit eventually

Here's a short reference of events over time on each replica:

1: ....ABCD
2: ZZZ  B
3: ZZZ  BCD
4: ZZZ    DABC
5: ........A

Now that replica 5 is out of a network partition, it receives commits in some particular order:

5: receives and executes all Z commands
5: receives A.101, deps=[Z, D], new least command, but needs to wait for D
5: receives D.3, deps=[A, C], new least command, but needs to wait for C
5: receives C.103, deps=[B], not a new least command

Running your algorithm we may decide that D.3 is the least command that needs to be executed, however that is not the case. There's actually a B.1 command in the cycle with the lowest seq that we haven't seen yet. Am I missing something about how seq and your algorithm is supposed to work?

[drmingdrmer]

In epaxos the execution consistency only guarantees order about interfering commands, not unrelated commands:

Execution consistency: If two interfering commands γ and δ are successfully committed (by any replicas) they will be executed in the same order by every replica.

That's why I said:

Assumes our discussion is only about interfering commands:

In your example D does not depend on B thus the order for B and D is not deterministic.

---

I'm not sure how to parse this. Are you talking about direct dependencies, or transitive dependencies as well? I assume direct, since in SCC everything depends on everything, in such case here's a counter example:

Here what I mean is transitively depending, so that a potential minimal seq is always reachable from an interfering command.

[snaury]

In your example D does not depend on B thus the order for B and D is not deterministic.

But it does depend on B (indirectly), and replicas would diverge if this is not taken into account. For example, assume all keys have initial value of 0.

Case 1:

replica sees A, D, C first
executing Z.100: Z := 42
executing D.3:   D := C     // 0
executing A.101: A := Z + D // 42
new least command C would have to wait for C
executing B.1:   B := A     // 42
executing C.103: C := B     // 0
replica has Z = 42, A = 42, B = 42, C = 0, D = 0

Case 2:

replica sees B
executing Z.100: Z := 42
executing B.1:   B := A     // 0
executing D.3:   D := C     // 0
executing A.101: A := Z + D // 42
executing C.103: C := B     // 42
replica has Z = 42, A = 42, B = 0, C = 42, D = 0

Here what I mean is transitively depending, so that a potential minimal seq is always reachable from an interfering command.

Then I'm not sure how it helps with livelocks. Waiting for all transitive dependencies would mean replica needs to see a complete SCC, which may grow indefinitely, hence a livelock.

Anyway, thank you for your answers. I think using some kind of monotonically increasing per-replica propose time as a tie breaker (used for breaking ties only, thus clock drift would only affect latency of long chains of conflicting commands and their dependencies, so not much of an issue) is more promising for solving this problem.

[drmingdrmer]

Update of my previous comment:

As you had the setup with D->A but without D->B, I assumed we were talking about the unoptimized deps, epaxos 4.5 describes the optimization of deps:

Instead of including all interfering instances, we include only N dependencies in each list: the instance number R.i with the highest i for which the current replica has seen an interfering command (not necessarily committed).

• For unoptimized deps, my algorithm should work, because any two interfering commands have a direct depends-on relation.

• For optimized deps, D->A is unnecessary in the setup.

In order to let this algorithm to work with optimized deps, a minor change needs to add to it:

Add the next least (seq, replicaID) command and its deps into CMDs.

Here we need to retrieve all of the unoptimized dependent commands. Back to your steps:

5: receives D.3, deps=[A, C], new least command, but needs to wait for C
5: receives C.103, deps=[B], not a new least command

The optimized deps of D.3 is A,C and needs to expand to A,B,C.

[drmingdrmer]

hi @snaury what about my latest comment?

[snaury]

hi @snaury what about my latest comment?

I don't understand what you mean by any two interfering commands having a direct depends-on relationship. Commands B and D don't interfere, so don't have a relationship in my example. Do you propose expanding relationships during phase 1 or during execution? The former makes it harder to think of a counter example, but I'm not sure there isn't one (having more replicas allows for longer and more out-of-order chains, but it's harder to analyse), besides you would need to prove certain properties for the final committed seq, but I'm not sure what those are. The latter I think would mean you always expand your least seq relationships (each new discovered node brings more transitive dependencies) until you have the complete SCC.

[drmingdrmer]

I don't understand what you mean by any two interfering commands having a direct depends-on relationship.

For two committed interfering command X and Y, there is at least one replica that has both of them.
Thus X depends on Y or Y depends on X or both.

Commands B and D don't interfere, so don't have a relationship in my example.

Yes.

Do you propose expanding relationships during phase 1 or during execution?

During execution.

The former makes it harder to think of a counter example, but I'm not sure there isn't one (having more replicas allows for longer and more out-of-order chains, but it's harder to analyse), besides you would need to prove certain properties for the final committed seq, but I'm not sure what those are.

I think epaxos gives complete proof about the consistency of the committed graph.

The latter I think would mean you always expand your least seq relationships (each new discovered node brings more transitive dependencies) until you have the complete SCC.

It does expand the least seq command, but this loop stops when the set of replicas of CMDs stops growing:

Repeat this step until we find a CMDs so that replicas(allDeps) ⊆ replicas(CMDs), then execute the least command in CMDs.

[snaury]

For two committed interfering command X and Y, there is at least one replica that has both of them.
Thus X depends on Y or Y depends on X or both.

I'm not sure how that helps. Here's another example, we are constructing a graph that looks like this:

A <-> B <-> C <-> D <-> E <-> F
↑                             ⇵
U <-- V <-- W <-- X <-- Y <-- Z

There is a long chain of commands A, B, C, D, E, F conflicting pairwise. There is also a long chain of commands U, V, W, X, Y, Z where U conflicts with A and eventually Z conflicts with F. Here's an incomplete diagram of how proposes/pre-accepts and accepts are spread over time:

1: A u U   C       b B   A  ... E ...
2: B                 B a A  ... D ... F ...
3:       b     v V   B a A
4:   u U       v V      
5: U   U     V   V          ... W ... X ... Y ... Z

Here's a textual description of how these commands are processed and what happens to their seq and deps:

propose    A.0, B.0, U.0
pre-accept u.1 -> A
accept     U.1 -> A
pre-accept b.0
propose    C.0
propose    V.2 -> U
pre-accept v.2 -> U
accept     V.2 -> U
pre-accept b.1 -> A, C
accept     B.1 -> A, C
pre-accept a.2 -> B
accept     A.2 -> B
...

Here we assume that PreAccept messages are sent immediately after command is proposed, but are somehow delayed in transit and may arrive later in time.

Notice we have already accepted these commands:

• A.2 -> B
• B.1 -> A, C
• U.1 -> A
• V.2 -> U

Notice also that replica 2 has never seen (and will never see) any of U, V. Eventually C will be accepted with e.g. seq=3 and replica 2 will see this:

• A.2 -> B
• B.1 -> A, C
• C.3 -> B, D

Replica 2 is not aware of U, and its owner 5 is not in its dependencies (the command that would eventually link A back to U is not even on anyones radar yet, but will be in some distant future). Its least seq, replicaID command order would thus be B.1, A.2, C.3, ..., and maybe eventually U.1, V.2, ...

However on a replica that is aware of U (or waits for a complete SCC, which is prone to livelock) the order would be B.1, U.1, A.2, V.2, etc. Notice how directly conflicting commands A and U are executed in different order on different replicas. This is inconsistent and unsafe.

Yes, there is a replica that sees both A and U, but it doesn't help in my example. There may also be a replica that only sees one branch of the loop.