The way we detect forks in Parsec is currently incorrect

Description

The way we currently detect forks is subtly incorrect. It impacts malice detection, but also in general correctness of the algorithm in presence of folks.

Roughly, the problem is that topological ordering is used as a proxy for ancestorship. That approximation doesn't always hold and can use to incorrect conclusions.

It is easier to explain the bug with an example.

Here is an example gossip graph with an index for each gossip event that represents one valid topological ordering.
Say Alice receives a gossip communication at the point where she is already aware of a_2 (topo index 4). She will process the events 5-15 in topological order.
When processing d_1a (topo index 8), Alice will realise that there is a fork and locally mark Dave as a forking peer. When processing event b_2 (topo index 12), Alice will think that b_2 is "aware" of the fork as it has a higher topological index. This is incorrect as only d_1a is an ancestor of b_2; not d_1b.

This mistake will lead to a number of nasty errors; for instance, when asking whether b_2 sees d_1a, the current algorithm will say "no because of the fork" which is obviously incorrect.

Note: the incorrect code is around the use of forking_peers in parsec.rs.

Environment

None

Status

Assignee

Adam Cigánek

Reporter

Pierre Chevalier

External issue URL

None

External issue ID

None

Start date

2019/01/31

End date

2019/03/26

Task progress

None

Baseline start date

None

Baseline end date

None

Story Points

6

Components

Priority

Major
Configure