This section describes the flow a node will follow during its entire lifetime.
When they join the network, they won't yet be a member of any section.
First,they will have to bootstrap with their proxy node, receive a RelocateInfo and attempt to join the
section that this RelocateInfo is pointing to.
Once they have a full section, they will be able to operate as a full section member.
OWN_SECTION refers to this node's own section.
It is an Option<Prefix>.
While a node is being relocated, the value will be none. Once they get accepted into a section, it
becomes Some(that_section_s_prefix)
This function gets called when a node just joined the Network.
At this stage, we are connected to a proxy node and they indicate to us which section we should join.
Once a node has joined a section (indicated by OWN_SECTION.is_some()), they will be able to perform as a
member of that section until they are relocated away from it.
See StartSectionMemberNode graph for details.
First Create new identity with public key-pair
The node connects to a proxy with the new identity to use for joining the new section as a full node.
Once a node knows where to be relocated, they will follow this flow to become a full member of the
section.
This covers resource proof from the point of view of the node being resource-proofed.
The output of this function is an Option. If we fail resource proof, it is none, which means we will
have to bootstrap again. If it is Some, it contains the RelocateInfo we need to join this section.
See JoiningRelocateCandidate graph for details.
This is from the point of view of a node trying to join a section as a full member.
This node is going to connect, send Rpc::CandidateInfo, and then perform the resource proof until it receives a Rpc::NodeApproval to complete this stage
successfully.
If the node is not accepted, after time out, it will try another section as a new node.
Timeout triggered to resend messages that have not been replied to:
Either Rpc::ConnectionInfoRequest or Rpc::CandidateInfo
Timeout to stop trying to resource proof if so much time has elapsed that we will not be able to succeed.
Return the next part of the resource proof for the given elder.
inputs:
- elder name
Return connected nodes and unconnected nodes in the given collection.
inputs:
- elder names
Return true if we already received Rpc::ResourceProof for that node.
inputs:
- elder name
The RelocatedInfo given to the routine and used to send CandidateInfo
Once a node has joined a section, they need to be ready to take on multiple roles simultaneously:
Deal with relocation:
The section as a whole will sometimes act as the source and sometimes as the destination of
relocations. This means nodes will sometimes relocate away from this section and sometimes relocate
to this section. Nodes in this section will need to perform the right flow to deal with both of
these situations.
Decide who's an elder or a plain old adult as well as when to merge or split.
Decide who is online and offline.
All of these flows are happening simultaneously, but they share a common event loop. At any time, either all
flows or all but one flows must be in a "wait" state. (If an event is handled by multiple active event
loops, the one with the highest number handles it.)
If our section decides to relocates us, we will have to stop functioning as a member of our section and go
back to the previous flow where we will "Rebootstrap" so we can become a member of a different section.
As a member of a section, our section will sometimes receive a node that is being relocated. These diagrams
are from the point of view of one of the nodes in the section, doing its part to handle the node that is
trying to relocate to this section.
Deciding when to accept an incoming relocation
This flow represents what we do when a section contacts us to relocate one of their nodes to our
section.
The process starts as we receive an Rpc::ExpectCandidate from this node.
We vote for it in PARSEC to be sure all members of the section process it in the same order.
Once it reaches consensus, we are ready to process that candidate by letting them connect (see
StartRelocatedNodeConnection) and then perform the resource_proof (see StartResourceProof).
There are some subtleties, such as the fact that we only want to process one candidate at a time, but this
is the general idea.
We receive this RPC from a section that wants to relocate a node to our section.
The node is not communicating with us yet, only once we sent Rpc::ExpectCandidateAcceptResponse to the
originating section.
On receiving it, we vote for Parsec::ExpectCandidate to process it in the same order as other members of
our section.
It kickstarts the entire chain of events in this diagram.
Note that we could also see consensus on Parsec::ExpectCandidate before we ourselves voted for it in
PARSEC, as long as enough members of our section did.
We want to accept at most one incoming relocation at a time into our section.
The count_waiting_proofing_or_hop function returns the count of nodes that we have yet to resource proof
or relocate through a new hop, (States from State::WaitingCandidateInfo until it reaches State::Online
or State::Relocated).
When the output of this function is not 0 and we reach consensus on Parsec::ExpectCandidate, we send a
Rpc::ExpectCandidateRefuseResponse to the would-be-incoming-node so they can try another section or try
again later.
If we already accepted a candidate, reply with the same info we provided intially and returned by
get_waiting_candidate_info.
If we know of a section that has a shorter prefix than ours, we prefer for them to receive this incoming
node rather than ourselves as it will help keep the Network's sections tree balanced.
This shorter_prefix_section is a function that will return None if we are the shortest of any section we
know, Some if there is a better candidate.
If it is Some, we will relocate the new node to them instead of completing the relocation to our own
section.
send_rpc( Rpc::ExpectCandidateAcceptResponse) to
source section"]
SendExpectCandidateAcceptResponse --> LoopEnd
SendRefuse["send_rpc( Rpc::ExpectCandidateRefuseResponse) to source section"]
SendRefuse --> LoopEnd
Resource proof from a destination's point of view
Manage node with NodeState=State::WaitingCandidateInfo.
When we periodically decide to resource proof a node, we check if any node is ready for it:
State::WaitingCandidateInfo state.
Once the candidate is connected, it sends its CandidateInfo to each Elders it was given in RelocatedInfo.
As an elder, I will send the candidate a Rpc::ResourceProof. This gives them the "problem to solve". As they
solve it, they will send me ResourceProofResponses. These will be parts of the proof. On receiving valid
parts, I must send a ResourceProofReceipt. Once they finally send me the last valid part, they passed their
resource proof and I vote for Parsec::Online (essentially accepting them as a member of my section).
At any time during this process, they may timeout (The whole process it taking longer than expected), in
which case I will decided to reject them and vote for Parsec::PurgeCandidate.
This process ends once I reach consensus on either accepting the candidate (Parsec::Online) or refusing them
(Parsec::PurgeCandidate).
It is possible that both reach the quorum consensus, in which case the second one will be discarded. It
won't cause issues as consistency is the only property that matters here: if we accept someone who then went
Offline, we will be able to detect they are Offline later with the standard Offline detection mechanism. But
it is more likely that they took close to the time limit to complete their proof.
Return true if
The given CandidateInfo is valid,
It matches one of our nodes that is in the State::WaitingCandidateInfo state,
The message_src (from the current RPC) is consistent with the CandidateInfo's new_public_id
Return a candidate ready to be resource proofed (First node in State::WaitingCandidateInfo state)
Convert the candidate node at the target interval address to a node using the new_public_id.
Update the state of the node with the given state.
Option<(Candidate)>.
The candidate we are currently resource proofing old_public_id, if any.
Once we've voted a node online, we don't care to handle further ResourceProofResponses from them.
This local variable helps us with this.
The candidate sends this RPC that contains part of a proof. It may continue to be sent by a node we have
not accepted, even if consensus was reached to add it.
It may also still be sent by a candidate we have rejected. It's OK to discard the RPC in these cases as
it is no longer relevant.
The same node could be accepted by some nodes who would vote Parsec::Online, but also time out for some
other nodes who would vote for Parsec::PurgeCandidate.
If it's the case, we only want to process the first of these two events and discard the other one.
Provides an external entry point to cancel the currently processed nodes: Restart the resource proofing
with all involved voters.
This will be called for example after merge/split as the new nodes would become voters.
send_rpc( Rpc::ResourceProof) to CANDIDATE_INFO.new_public_id"]
RequestRP --> LoopEnd
RPC -- Rpc::ResourceProofResponse from CANDIDATE_INFO --> ProofResponse((Proof))
ProofResponse((Check))
SendProofReceipt["send_rpc( Rpc::ResourceProofReceipt) for proof"]
ProofResponse -- "Valid Part or End otherwise" --> SendProofReceipt
VoteParsecOnline["vote_for( Parsec::Online)
As members of a section, each node must keep track of how many "work units" other nodes have performed.
Once a node has accumulated enough work units to gain age, the section must work together to relocate that
node to a new section where they can become 1 age unit older.
These diagrams detail how this happens.
Deciding that a member of our section should be relocated away
In these diagrams, we are modelling the simple version of node ageing that we decided to implement for
Fleming: Work units are incremented for all nodes in the section every time a timeout reaches
consensus.
Because a quorum of elders must have voted for this timeout, the malicious nodes can't arbitrarily speed up
the ageing of their nodes.
Once a node has accumulated enough work units to be relocated, if no other node is currently in
State::RelocatingAgeIncrease we set its state to State::RelocatingAgeIncrease. This node will then be
actually relocated in StartRelocateSrc (see StartRelocateSrc).
Because of this, we will generally only relocate one adult at a time (except in case of merge).
In the context of Fleming, nodes (especially adults) aren't doing meaningful work such as handling
data.
As a proxy, we use a time based metric to estimate how much work nodes have done (i.e: how long they
remained in State::Online and responsive).
A local timeout wouldn't do here as it would allow malicious nodes to artificially age nodes in their
sections faster. However, by reaching quorum on the fact a timeout happened, we ensure that at least one
honest node has voted for the timeout.
All nodes start the WorkUnitTimeout. On expiry, they vote for a WorkUnitIncrement in PARSEC and restart
the timer.
This function increments the number of work units for all members of my peer_list (remember that
n_work_units is a member of the PeerState struct).
Returns true if we have any node currently relocating: With node state State::RelocatingAgeIncrease
only.
There will most often be zero or one such nodes, unless a merge occurs in which case there may be
multiple.
Nodes coming back online, or needing an extra hop are not considered here.
This function will return the best candidate for relocation, if any.
First, it will only consider members of our peer_list that have the state: State::Online
We use the condition with has_relocating_node() to limit the number of State::Online nodes to relocate
to one (except possibly in case of a merge).
It can return for instance the node with the largest number of work units for which the number of work
units is greater than 2^age.
This function mutates our peer_list to set the state (for example set State::RelocatingAgeIncrease for
the node).
inputs:
- node
- state
side-effect:
- mutates peer_list
At this stage, we handle nodes that were marked for relocation.
We send an Rpc::ExpectCandidate to the destination section:
Either that section will send us a Rpc::ExpectCandidateAcceptResponse, then we will complete the node
relocation.
Or that section will send us a Rpc::ExpectCandidateRefuseResponse, then we will retry later.
Or that RPC or the response is lost, then we will retry later.
When we receive Rpc::ExpectCandidateAcceptResponse or Rpc::ExpectCandidateRefuseResponse, we vote for it in
PARSEC, regardless of the order of operations, so it will be consensused.
The first Parsec::ExpectCandidateAcceptResponse consensused for a node will be the single valid relocation.
We will sign the relocation info through parsec and send to the node that is being relocated the
RelocatedInfo they will need.
At this point, we will purge their information since this node isn't a member of our section any more.
Elders are not considered for relocation: Elder nodes in State::RelocatingAgeIncrease will eventually get
demoted to adults (see StartMergeSplitAndChangeElders) at which point they may be relocated.
We prioritise relocating our Adults, then just relocated nodes that need another hop, then nodes coming back
online.
Also of note: We may be relocating multiple nodes (i.e because of merge, or node relocating to us or node
coming back online), but we will only handle one at a time per CheckRelocateTimeOut event.
Throttling is otherwise handled in flows setting the relocating states.
Takes ALREADY_RELOCATING for the nodes it will ignore.
Returns the best node to relocate and the target address to send it to
There may be multiple nodes relocating, for example because of a merge. Take the best one (oldest), and
choose a target address.
The target address is one managed by one of our neighbours. This could be random, or the current
old_public_id with a single bit of the prefix flipped.
This would help ensure that source and destination remain neighbours, even if the source splits.
Using a target address instead of a section ensures we deliver the message even if the destination
splits or merges.
There are 3 states the node may be: State::RelocatingAgeIncrease, State::RelocatingHop, and
State::RelocatingBackOnline.
Nodes will be selected in this order: State::RelocatingAgeIncrease, State::RelocatingHop and then
State::RelocatingBackOnline and tie break by age then name.
This ensures that we prioritise good node relocation.
Note: It may be possible for a node to relocate to its sibling, and complete relocation after a merge
occurred.
The nodes we ignore when selecting a new node to send Rpc::ExpectCandidate for.
Local states are not carried over on merge or split, so we will resend Rpc::ExpectCandidate earlier than
we would otherwise.
Is it a valid node that is not yet relocated (i.e State is State::RelocatingAgeIncrease,
State::RelocatingHop or State::RelocatingBackOnline).
Exactly one of these RPCs will be sent to us from the destination section as a response to our section's
Rpc::ExpectCandidate.
When this happens, we will immediately vote for it in PARSEC as we need to act in the same order as
anyone else in our section.
In case we re-sent the Rpc::ExpectCandidate, we may receive more than one
Rpc::ExpectCandidateRefuseResponse and Rpc::ExpectCandidateAcceptResponse. In this case we will pass on
the first Rpc::ExpectCandidateAcceptResponse to our Candidate.
Trigger relocation: Candidate will disconnect on receiving that RPC
This RPC contains the Rpc::ExpectCandidateAcceptResponse info, and the signatures proving the source
section received it and decided that particular response is the one to relocate to.
In case we re-sent the Rpc::ExpectCandidate, we may receive more than one
Rpc::ExpectCandidateAcceptResponse.
In this case we must ensure that no single node could act on that other
Rpc::ExpectCandidateAcceptResponse and be accepted by the destination. this means the signatures must be
provided only once the Rpc::ExpectCandidateAcceptResponse is agreed.
RelocatedInfo will contain the Rpc::ExpectCandidateAcceptResponse info and the quorum of signatures
gathered from PARSEC vote on Parsec::RelocatedInfo.
(allow resend)"]
RefusedCandidate --> LoopEnd
CheckIsAccept -- Parsec::ExpectCandidateAcceptResponse --> VoteProvableRelocateInfo
VoteProvableRelocateInfo["set_node_state( node, State::Relocated{accept_info} (Vote for same
relocation if merge/split so only one valid proof
exists)
Process for Adult/Elder promotion and demotion including merge
This flow updates the elder status of our section nodes if needed.
Because it is interlinked, it also handles merging and splitting section: When merging or splitting, no
elder change can happen.
However other flows continue, so relocating to and from the section is uninterrupted:
As for incrementing work units, we want to update the eldership status of all nodes in a section on a
synchronised, regular basis.
For this reason, it makes sense to have a timer going through Parsec.
Note that this timer has to be only as fast as needed so that it remains highly unlikely that 1/3 of the
elders in any section would go offline within one timer's duration.
A section sends a Rpc::Merge to their neighbour section when they are ready to merge at the given
SectionInfo digest. The RPC contains the SectionInfo of the originating section.
In this flow, we handle both situations:
Our neighbour triggers the merge and we receive their Rpc::Merge.
We then vote for Parsec::NeighbourMerge.
We trigger the merge ourselves (see ProcessMerge flow)
We vote for this Parsec event on receiving a Rpc::Merge from our neighbour section.
It contains the information about them that we need for merging. When this PARSEC event reaches
consensus in PARSEC, we store that information by calling store_merge_infos.
This function is used to store the merge information from a neighbour section locally.
Once it has been stored, has_merge_infos will return true and we will be ready to enter the ProcessMerge
flow.
This function indicates that we received sufficient information from our neighbour section needing a
merge, and reached consensus on it.
We are ready to start the merging process with them.
This function indicates that we need merging (as opposed to a merge triggered by our neighbour's
needs).
The details for the trigger are still in slight flux, but here are some possibilities:
The number of State::Online adults plus elders is below our min section size of 10 elder plus
90 Adults
A certain proportion of the adults in this section are marked Offline
If any of our elders is not State::Online, they must be demoted to a plain old adult.
If this happens, the oldest adult must be promoted to the elder state as a replacement.
Alternatively, if any of our State::Online adult nodes is older than any of our elders, the youngest
elder must be demoted and this adult must be promoted.
Note that elder changes are only processed when the section is not in the middle of handling a merge.
This function indicates that we need splitting.
The details for the trigger are still in slight flux, but here are some possibilities:
The number of State::Online adults plus elders is above our min section size of 10 elder plus 90
Adults + buffer
Process Adult/Elder promotion and demotion needed from last check
Vote for Parsec::Add for new elders,Parsec:: Remove for no longer elders and Parsec::NewSectionInfo
This handles any change, it does not care whether one or all elders are changed, this is decided by the
calling function.
At any time, there must be exactly NUM_ELDERS (say 10) elders per section.
To maintain this invariant, we must handle multiple eldership changes atomically
We accomplish this by voting for all the membership changes needed at once and waiting for all these
votes to reach consensus before reflecting the status change in our chain.
A list of PublicId.
The content of the NewSectionInfo parsec event that reached consensus.
This function updates the eldership status of each node in the chain based on the new section info: the
nodes with their public id in new_section_info are the exact set of current elders.
Input:
new_section_info: Set<PublicId>
The new section info that just reached consensus.
Side-effect:
Mutates the chain.
graph TB
ProcessElderChange["ProcessElderChange (Take elder changes) (shared state)"]
style ProcessElderChange fill:#f9f,stroke:#333,stroke-width:4px
EndRoutine["End of ProcessElderChange (shared state)"]
style EndRoutine fill:#f9f,stroke:#333,stroke-width:4px
ProcessElderChange --> MarkAndVoteSwapNewElder
MarkAndVoteSwapNewElder["vote_for(Parsec::Add) for new elders vote_for(Parsec::Remove) for now adults
nodes vote_for(Parsec::NewSectionInfo)
Send Rpc::Merge, and take over handling any Parsec::NeighbourMerge.
Complete when one merge has completed, and a NewSectionInfo is consensused.
If multi-stage merges are required, they will require calling this function again
While in this sanctuary, our SectionInfo shall not be disturbed by elder changes.
This stops us from changing our SectionInfo after indicating to our neighbour the last SectionInfo before
merge.
We send it to our sibling section (or sections with longer prefix) on entering ProcessMerge, containing our own SectionInfo.
We send Merge irrespective of whether we are the section that triggered the merge. This allows all
sections involved in the merge to receive a Rpc::Merge, which is how Parsec::NeighbourMerge gets voted
for.
This PARSEC event indicates that our neighbour section is ready to merge with us.
It is voted for in the StartMergeSplitAndChangeElders flow, on receipt of a Rpc::Merge.
It contains their SectionInfo (or digest for it).
Store the neighbour's merge info, may not be sibling in case of multi merge
Did we store the neighbour's merge info for our sibling
Remove the stored sibling's merge info and return the NewSectionInfo.
Once we are ready to merge, have received our neighbour's SectionInfo through their Rpc::Merge, and
subsequently reached consensus on the Parsec::NeighbourInfo we voted for, we have all the information
needed to decide on the membership of our post-merge section.
This is the Parsec::NewSectionInfo.
With the Parsec::NewSectionInfo in hands, completing the merge process consists on joining the newly
formed section and leaving the old one behind.
Vote for the two Parsec::NewSectionInfo to gather required signatures
Wait for all these votes to reach consensus before reflecting the status change in our chain.
Both sections need to be consensused before we move on so we do not leave one behind with not enough
voters.
With the NewSectionInfo in hands, completing the split process consists on joining the correct newly
formed section and leaving the old one behind.
A list of PublicId.
The content of the NewSectionInfo parsec event that reached consensus that we are now a member of.
graph TB
ProcessSplit["ProcessSplit (Take elder changes) (shared state)"]
style ProcessSplit fill:#f9f,stroke:#333,stroke-width:4px
EndRoutine["End of ProcessSplit (shared state)"]
style EndRoutine fill:#f9f,stroke:#333,stroke-width:4px
ProcessSplit --> VoteNewSections
VoteNewSections["vote_for(Parsec::NewSectionInfo) for the two new sections
Successfully relocate a node from source to destination section
Sent by the source section when a candidate needs to relocate
Contains:
old_public_id: PublicId - The joining node's current public ID.
new_age: u8 - The joining node's new public id age.
Decided by source section, could be +1 or /2 depending on why we relocate.
(If we want to allow early relocate, we could also add carried over work units.)
Sent by destination section when a candidate is accepted
Contains:
target_interval: (XorName, XorName) - The interval into which the joining node should join.
section_info: SectionInfo - The destination section that the joining node will trust.
Sent by destination section when a candidate is refused
Contains: Empty
Sent by source section when a candidate is relocated to the relocated node
Contains:
target_interval: (XorName, XorName) - The interval into which the joining node should join.
section_info: SectionInfo - The destination section that the joining node will trust and connect to.
proof: Signatures - Quorum of signature for the candidate to prove the source section relocated
it with these infos.
Sent by the joining node to each elders of the section it is joining to initiate the joining process
Contains:
old_public_id: PublicId - PublicId from before relocation.
new_public_id: PublicId - PublicId from after relocation.
signature_using_old: Signature - Signature of concatenated PublicIds using the pre-relocation
key.
signature_using_new: Signature - Signature of concatenated PublicIds and signature_using_old
using the post-relocation key.
new_client_auth: Authority - Client authority from after relocation.
source_proof: Signatures - Quorum of signature from the source section proving the source
approved that relocation.
This will be checked against the stored information in the candidate node state.
Sent to collect information needed to establish a direct connection: Unchanged
Sent to process resource proof: Unchanged
Sent by destination section when a candidate becomes an adult / resource proof is completed.
Contains: Empty (Any information needed by an adult/elder should be sent to all connected members, and
updated as it changes)
sequenceDiagram
participant Src as Source Section
participant Node as Relocating Node
participant Dst as Destination Section
loop FindDestination
Src->>+Dst: Routing RPC: Rpc::ExpectCandidate
opt Refuse
Dst-->>Src: Routing RPC: Rpc::ExpectCandidateRefuseResponse
end
end
Dst-->>-Src: Routing RPC: Rpc::ExpectCandidateAcceptResponse
Src->>Node: Direct node-to-node RPC: Rpc::RelocatedInfo
loop NodeConnection
Node->>+Dst: Proxied Routing RPC: Rpc::ConnectionInfoRequest
Dst-->>-Node: Proxied Routing RPC: Rpc::ConnectionInfoResponse
Node->>Dst: Direct node-to-node RPC to group: Rpc::CandidateInfo
end
Dst->>Node: Direct node-to-node RPC: Rpc::ResourceProof
loop ResProof
Node->>+Dst: Direct node-to-node RPC: Rpc::ResourceProofResponse
Dst-->>-Node: Direct node-to-node RPC: Rpc::ResourceProofReceipt
end
Dst->>Node: Unproxied Group RPC: Rpc::NodeApproval