Pierre explains PARSEC

Sorry to revive this old topic, but this indeterminism still bothers me. The following initial state is used in many PARSEC presentations:

The problem is that this situation is not in the domain of validity of PARSEC because there are two nodes with an estimate of true and two with false. This means there are necessarily two malicious nodes here, which is above the 1/3 PARSEC threshold.

The common coin will allow reaching an agreement, but there is a 50% chance that the decided value will be the one proposed by the malicious nodes. I think this is an obstacle for users to understand the protocol, and this certainly confused me.

Now, I will rephrase my original question: Is the common coin protocol only needed to unblock the algorithm outside PARSEC domain of validity or are there cases where it is also needed within this domain (with less than one 3rd of malicious nodes)?

3 Likes

This estimates are not final votes about an event but meta votes. Meta votes are the answer about the question “Do I strongly see an interesting gossip event for this node?”. In this case Alice and Dave strongly see an interesting event and Bob and Carol not.

4 Likes

Ok. But now I have an even more basic question for @maidsafe: how do we get this situation highlighted in my post and mentioned in many PARSEC presentations?

Suppose there is a real network event (for example Frank wants to join the network) but some malicious nodes don’t want it to be recorded. I see the following cases but none of them lead to this situation.

  • If all nodes are honest then the 4 nodes will strongly see this event.
  • If one node is malicious then the 3 honest nodes will strongly see the event
  • If two nodes are malicious then no nodes will strongly see the event because the 2 honest nodes don’t make a super majority
  • Same for 3 and 4 malicious nodes
1 Like

2 of 4 is less than a superiority if your group size is 4 (which is what I think you are seeing). Use of 1, 2 or 3 in some maths is a it misleading. If you start at a group size of 8 or similar it becomes more clear.

1 Like

There is no group size in PARSEC, because the whole network is a section.

But this eludes the question, I just want to know how we can get the following example used in many PARSEC presentations:

and described with words by @digipl:

In this case Alice and Dave strongly see an interesting event and Bob and Carol not.

1 Like

Maybe it’s easier to explain than with 8 or 1008

1 Like

In Dave’s case is evident. Bob->Carol->Dave (Dave sees, at least, 3 of 4 nodes that form a supermajority).

In Alice’s case a previous gossip makes a path that forms a supermajority.

For example Carol->Bob->Alice or Dave->Bob->Alice.

We also know that neither Bob or Carol can see a path that pass through more than two nodes.

2 Likes

That’s a good question. It comes from a misunderstanding of the problem space:
Honest nodes can vote for true or false. It is not malicious to vote for something another honest node didn’t vote for.

Let me give you an example (with a bit of a metaphore):
You could use binary consensus to have people all over the planet agree on the question: “Did it rain on this specific day?” Each honest node would report on the weather conditions they observed where they live. Honest nodes would definitely say the truth, but all honest nodes may not have experienced the same reality, because it may have rained in some parts of the world but not in others. Malicious nodes may vote contrary to what they experienced (if it’s advantageous to impede consensus).

The outcome of binary consensus will be either “yes” or “no”. All honest nodes will have the same outcome. If the outcome is “yes”, you can be sure that it rained in at least one place where a honest node was observing the weather. If the outcome is “no”, you can be sure that it didn’t rain in at least one place where a honest node was observing the weather.

What’s malicious is not to disagree but to report fake information (probably with the purpose of causing nodes to agree on a fake value or with the purpose to delay consensus forever).

I hope this clarifies it :smile:

17 Likes

Hi @pierrechevalier83, a contextual question regarding the use of the word “byzantine” in the name and definition of a consensus algorithm:

An algorithm being “byzantine” meaning that it’s liar proof, right.

So, 2/3 must be sincere. Say these are split 50-50 of the 66.6%, meaning 33.3% vote YES and 33.3% vote NO.

Parsec can’t read the minds of the remaining 33.3% liars.

If the liars are allowed to vote as they want, they can tip over 50% both for the YES and the NO side. (33.3% genuine participants’ YES + 33.3% YES votes from the liars = 66.6% YES vote, which is above the >50% majority threshold, same for the NO side - 33.3% genuine participants’ NO + 33.3% NO votes from the liars = 66.6% NO vote.)

Absent of being able to read people’s minds, what does Parsec do to to separate the wheat from the chaff & get to some kind of honest participants’ vote?

1 Like

If I understand correctly there is no chaff. If a value has been voted for by an honest node, then this value is good.

In your case both values are good because they both have been reported by honest nodes. Votes of malicious nodes doesn’t matter here.

1 Like

More exactly, >= 2/3 must be honest (<1/3 may be malicious).

From ABA’s BV broadcast, no estimate coming from <1/3 of the nodes will propagate. From this behaviour follows that they won’t be able to dictate an incorrect value.

9 Likes

I think that the weird things about the diagram I mentioned above are simply due to the block being invalid. A valid block is a block voted for by a supermajority of nodes. Here N=4 and the vote is true for only 2 nodes, which is not enough to make it valid (because 2/3N = 2.66 > 2).

The requirements are not met to trigger a meta election. It is a pity is that this diagram is used in the parsec paper to illustrate meta-election (on page 6):

This is a very bad example because the block is not valid.

When the requirements are met (an event strongly sees a valid block), then current node knows that the block will be agreed on eventually. The meta election only determines the order of the block, so counter intuitive actions can be done like:

  • adding an estimate different from what a node voted for in the past
  • using randomness by flipping a coin

The aim is only to get a consensus on the order of the block. If it were to determine the block validity, then these actions would be effectively absurd.

I hope this explains my past misunderstandings.

6 Likes

@pierrechevalier83 when are you releasing the updated version of the paper which is under peer review currently did you say?

Also: This thread and the thread Understand if-how Parsec solves this problem, please explain/describe Parsec have very similar topics.

1 Like

I wouldn’t hold my breath waiting on a reply from Pierre on that.

6 Likes


:wink::kissing:

12 Likes

The second best looking guy in MaidSafe’s history still on the forums? Outrageous!!!

15 Likes

so says the third :smiley: :smiley:

13 Likes

We’re opening this out to the top 50?

10 Likes

I have to say, while it’s flattering, it’s tiring to be constantly reduced to one’s looks… Of course, as the third ever best looking employee, you wouldn’t be able to put yourself in my shoes; but you know… It feels a bit objectifying… Sometimes I just want to tell the world: I’m more than just a pretty face :joy::joy::joy:

20 Likes

We all feel the same, solidarity brother :smiley:

16 Likes