Consensus, async, Ae : What does it all mean and where does it matter?

[jlpell]

@dirvine

I Claim no as worst case we have N=3f+1+2 (i.e. “range” of N is 3f+1 >= N <=3f+1+2)

A minor follow-up note here:

I found a problem with my previous post and updated the 3 constraint equations for each impossibility result. Your (N=3f+1+2) plan satisfies Alternative #1 above for strong crash tolerance and weak byzantine tolerance. It is equivalent to (N >= 2bf + cf + 1) for bf=2 and cf=4. As you have already pointed out, given the interval between (n=3f+1) and (N=3(f+1)+1), this puts a cap on cf, where (cf <= bf+2). TLDR; I’m basically just trying to describe what you’ve been saying in terms of the simple (N >= 2*bf + cf + 1) constraint I showed above.

[Toivo]

@dirvine

Part 2 of this deep dive will go into the business logic of membership and then how it all ties together.

I am writing and rewriting it to get clarity. I suspect I will attack it in a few steps.

1. A stable size single-section network (i.e. a section that tries to maintain it’s size under churn)
2. A growing network (introduce splits)
3. A growing network that limits growth to when it’s needed and how.

These all introduce interesting elements.

1. Attacks the join queue and selection of nodes
2. Attacks the splitting logic (and tries to make it natural)
3. Attacks the limiting logic.

Each introduces a new event type to consider deeply.

Anything brewing in regards to this part 2?

[dirvine]

We are doing a ton of work with stateright to confirm a few points. It’s looking very promising for this though.

[Toivo]

I was meaning more about you writing more about it, not where the project is at. I enjoyed the previous part a lot, because there was discussion about the basic logics of it all, and not so much via technical implementations. Something to think about for me, (digestible) food for brain.

[dirvine]

No worries, hopefully soon I can have clarity to write it up in a way that is hopefully interesting and provable. If we can provide these great claims with proofs that people can run for themselves then it will be comforting for all.

There’s more to it as we investigate and right now I am looking at more simplifications where we use no signatures at all, no section chain and even no Ae. Instead it’s all very dynamic and reproducible. Makes heavy use of DBC payments for data validity too. All in all it’s the most exciting thing for me to be able to have a model checker confirm these suspicions. It’s way better than me trying to explain it to folk.

It’s a lot to do with the fact decisions are made by a group, the group changes over time, but it’s always the oldest nodes. Them changing and seeing changes at different times allow us to so some really powerful things, like right now we are looking to prove that a group A B can go to A B C and then back to AB. Normally that breaks consistency models (CRDT etc.) And we need logical clocks. But no, I don’t think we do and the reason is simple. A B → then went to A B + C joining → A B C → A B + C leaving → A B. So there is a progression, i.e. we never went back to A B where C could rejoin, (it’s dead Jim). This is subtle but interesting, A B looks like it went A B then back to A B, but in reality it does not. A B had another member C that was not an elder, then it was (even if it just joined) and then it died, it’s no longer in any part of the network, it cannot age to C again. It’s a parrot glued on a stick and is no more.

Anyway, there is a ton of that thinking and challenging of current state of art, but all because we are using group based decisions in a p2p network where we trust only majority. So no trust in single nodes. That majority is like using a logical clock, but from another angle it’s not, it’s better as it’s based on nodes only able to leave after they join and also different elders will see these events at different times, but they must all coalesce to the current stable set when the churn slows down.

That would seem that a doublespend can happen as this madness is occurring, but so far we have shown it just does not happen. It’s a very interesting labs project this one.

I have long suffered from people thinking it cannot be that simple, it will definitely not work, but unable to prove it won’t work and me unable to prove it will, till now!

[VaCrunch]

@dirvine

Anyway, there is a ton of that thinking and challenging of current state of art, but all because we are using group based decisions in a p2p network where we trust only majority. So no trust in single nodes. That majority is like using a logical clock, but from another angle it’s not, it’s better as it’s based on nodes only able to leave after they join and also different elders will see these events at different times, but they must all coalesce to the current stable set when the churn slows down.

Sounds like a possible replacement framework for Congress, or Parliament.

[Toivo]

@dirvine

But no, I don’t think we do and the reason is simple. A B → then went to A B + C joining → A B C → A B + C leaving → A B. So there is a progression, i.e. we never went back to A B where C could rejoin, (it’s dead Jim). This is subtle but interesting, A B looks like it went A B then back to A B, but in reality it does not. A B had another member C that was not an elder, then it was (even if it just joined) and then it died, it’s no longer in any part of the network, it cannot age to C again.

Am I understanding it correctly:

1. There is A B, and they know about each other. They don’t know about C (as they have not seen it)
2. C joins.
3. There is A B C and they all know about each other.
4. C leaves.
5. There is A B and they know C was, and is no more.

Now if C tries to come back, A B can say “no you can’t”. This means the node ID that C was known with, can’t come back. But the hardware (and IP, etc.) , that was previously known as C, can apply to come back to the network with new ID as a new node, beginning from the bottom of the ranks?

[dirvine]

No memory or state. So if the whole network was only A and B then C joined and left it could rejoin again as there are no other nodes. This is really network startup, but normally it’s not like this.

When the networks up and running then C needs to start as an infant once more as we have forgotten him…

This is nice as we don’t need the network to remember stuff (have state) and that feels good to me.

[Toivo]

@dirvine

No memory or state.

But how can the nodes know which of them are the oldest then? They need to know in which order they appeared, no?

[JPL]

This is where the stable set comes in. To get into the stable set you need to have first gone through a number of relocations in the node age process. The stable set has a simple ‘first-seen’ ranking order since node age no longer applies. The first-seen seven nodes in the stable set are the elders and those that arrived later are adults, again ranked on first-seen.

If C is an elder and it gets booted, the highest ranking adult is promoted to take its place and C has to start again as an infant.

[Toivo]

That’s clear, but how come:

@JPL

a simple ‘first-seen’ ranking order

is not memory or state? I think there must be a list of the order the nodes joined somewhere?

(And I guess this “order” is “order as seen by a majority”, as any other order cannot exist, because there is no one viewpoint where to put things in order.)

Imagine a game, where people enter room one by one, and the rule is that the seven people who arrived first can decide what they do. Now, if those people, inlcuding the seven first ones, have alzheimers disease and no one can remember who the first seven were, how can they play?

I guess this is just about semantics. Like, is “knowledge” different from “memory” etc.

[Toivo]

A friend told me that in Portugal they have a habit that when a people goes to a crowded bus stop, she yells “Last one?”, and then the one who arrived before her replies “Here!”. And that’s how they order people before going in to bus. Everyone knows the one before and after.

In Finland we “do” it totally differently: Everyone tries to position him/herself at the bus stop so, that the door of the bus stops right in front of you. Then we go in in whichever order follows from that.

She was looked at quite harshly in Portugal, when applying the finnish way, when she didn’t know better.

[dirvine]

@Toivo

is not memory or state? I think there must be a list of the order the nodes joined somewhere?

There is state form that perspective, but not state as to who was ever on the network (as that grows forever)

[Southside]

@Toivo

In Finland we “do” it totally differently: Everyone tries to position him/herself at the bus stop so, that the door of the bus stops right in front of you. Then we go in in whichever order follows from that.

Its in Finlamd so its important to get on the bus quickly. Its all right for these Ports hanging about in the , they can take a more leisurely approach