[
https://issues.apache.org/jira/browse/CASSANDRA-17530?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel
]
Blake Eggleston updated CASSANDRA-17530:
----------------------------------------
Reviewers: Blake Eggleston
Description:
The version of Paxos introduced recently had a subtle mistake that introduced
a linearizability flaw that has been detected by the simulator, and also a flaw
with the simulator has been found that may erroneously report a linearizability
violation.
The true linearizability fault is quite simple: fast read permissions were
erroneously being escalated to promises when an incomplete proposal was
discovered. This was likely due in part to the naming of the state
{{FOUND_INCOMPLETE_ACCEPTED}} which does not communicate that the ballot will
be used to re-propose this proposal using the promises we have obtained. The
fix is to yield {{SUPERSEDED}} if {{!haveOnlyPromises}}.
The false linearizability fault was triggered when two different competing
incomplete proposals were reproposed multiple times, with the winning proposal
being the one with the lower original ballot, and the proposal with the higher
ballot having been successfully proposed to a majority of nodes but across
multiple different ballots (so that no single ballot reached a majority), while
the most recently successful ballot (at a minority) was the older original
ballot. The range movement validation logic looked only at the original ballot,
and since it saw the higher original ballot as having reached a majority
perceived that it should have become persistent, when in fact the older ballot
did so.
was:
The version of Paxos introduced recently had a subtle mistake that introduced
a linearizability flaw that has been detected by the simulator, and also a flaw
with the simulator has been found that may erroneously report a linearizability
violation.
The true linearizability fault is quite simple: fast read permissions were
erroneously being escalated to promises when an incomplete proposal was
discovered. This was likely due in part to the naming of the state
{{FOUND_INCOMPLETE_ACCEPTED}} which does not communicate that the ballot will
be used to re-propose this proposal using the promises we have obtained. The
fix is to yield {{SUPERSEDED}} if {{!haveOnlyPromises}}.
The false linearizability fault was triggered when two different competing
incomplete proposals were reproposed multiple times, with the winning proposal
being the one with the lower original ballot, and the proposal with the higher
ballot having been successfully proposed to a majority of nodes but across
multiple different ballots (so that no single ballot reached a majority), while
the most recently successful ballot (at a minority) was the older original
ballot. The range movement validation logic looked only at the original ballot,
and since it saw the higher original ballot as having reached a majority
perceived that it should have become persistent, when in fact the older ballot
did so.
> Paxos v2 Linearizability Violation
> ----------------------------------
>
> Key: CASSANDRA-17530
> URL: https://issues.apache.org/jira/browse/CASSANDRA-17530
> Project: Cassandra
> Issue Type: Bug
> Components: Consistency/Coordination
> Reporter: Benedict Elliott Smith
> Assignee: Benedict Elliott Smith
> Priority: Normal
> Fix For: 4.1
>
>
> The version of Paxos introduced recently had a subtle mistake that
> introduced a linearizability flaw that has been detected by the simulator,
> and also a flaw with the simulator has been found that may erroneously report
> a linearizability violation.
> The true linearizability fault is quite simple: fast read permissions were
> erroneously being escalated to promises when an incomplete proposal was
> discovered. This was likely due in part to the naming of the state
> {{FOUND_INCOMPLETE_ACCEPTED}} which does not communicate that the ballot will
> be used to re-propose this proposal using the promises we have obtained. The
> fix is to yield {{SUPERSEDED}} if {{!haveOnlyPromises}}.
> The false linearizability fault was triggered when two different competing
> incomplete proposals were reproposed multiple times, with the winning
> proposal being the one with the lower original ballot, and the proposal with
> the higher ballot having been successfully proposed to a majority of nodes
> but across multiple different ballots (so that no single ballot reached a
> majority), while the most recently successful ballot (at a minority) was the
> older original ballot. The range movement validation logic looked only at the
> original ballot, and since it saw the higher original ballot as having
> reached a majority perceived that it should have become persistent, when in
> fact the older ballot did so.
--
This message was sent by Atlassian Jira
(v8.20.7#820007)
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscr...@cassandra.apache.org
For additional commands, e-mail: commits-h...@cassandra.apache.org
