microsoft / microsoft/CCF

Consensus Trace Validation improvements

Open
#6,183 5 comments 0 reactions 0 assignees View on GitHub
tla
Dominant language
C++
Stars
876
Forks
260
Avg merge
1d 11h
Merged PRs (30d)
157

Description

# Resolved

1. (#6187) All client requests are identical at the moment `[request -> 42, contentType |-> TypeEntry]`. Two ways to go here:

- Fill them with something unique to distinguish them, perhaps a digest of the entry (with real traces in mind). We would need to capture them, and pre-fill the spec to produce `ClientRequest` from them.
- Accept that the content does not matter to the consensus spec, and remove `request` altogether. Done.

# To be discussed

2. In `IsSendAppendEntries`, `sent_idx` does not match `nextIndex[i][j]`. Investigated, explained, and options [proposed](https://github.com/microsoft/CCF/pull/5988#issuecomment-1929670423). @achamayou prefers options 1 or 2.

# Requires Investigation:

4. In `IsSendAppendEntries` `Len(log'[logline.msg.state.node_id])` does not match `logline.msg.state.last_idx`. Needs investigation.
5. In `IsRcvAppendEntriesRequest`, `leadershipState[logline.msg.state.node_id]` does not match `ToLeadershipState[logline.msg.state.leadership_state]`. Needs investigation.
6. In `IsRcvAppendEntriesRequest` `Len(log'[logline.msg.state.node_id])` does not match `logline.msg.state.last_idx`. Needs investigation.
7. In `IsAddConfiguration`, committable indices, commit Index, membershipState and last_idx don't match. I looked at this, and in situations where we receive an AE range that contains a configuration at first followed by committable indices, recv_append_entries will update the committable indices in the spec, but not in the impl state, which then goes on to handle an add_configuration event on which state->committable_indices is empty. Needs investigation.
8. In `IsAdvanceCommitIndex`, the `commit_idx` and `last_idx` don't match in the `Follower` case. Needs investigation.
9. In `IsRcvAppendEntriesResponse`, the `leadershipState` does not match. Needs investigation.
10. In `IsRcvRequestVoteRequest`, the `leadershipState` and `last_idx` do not match. Needs investigation.
11. In `IsExecuteAppendEntries`, the `commit_idx` and `last_idx` do not match. Needs investigation.
12. In `IsRcvRequestVoteResponse`, the `leadershipState` does not match. Needs investigation.

Contributor guide

Open the contributing guide

Research direction

Start by examining the consensus trace validation predicates named in the issue, beginning with IsSendAppendEntries, and read the linked discussion in PR #5988. Compare the listed implementation and specification state mismatches across the affected handlers. Done means the discrepancies are investigated, resolved or explained, and the consensus trace validation behaves consistently.

Written by the indexing model from the issue text.

Assessment

Tech stack
cpp
Domain
distributed-systems
Issue type
Bug
Difficulty
5/5
Estimated time
Over a week
Activity status
Stale
Clarity
Needs clarification
Newbie friendliness
25/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.