michaelsproul / ewok Goto Github PK
View Code? Open in Web Editor NEWSimulator for a distributed fuzzy ordering algorithm
Simulator for a distributed fuzzy ordering algorithm
Something like: there are 5 sections, they have these prefixes, they contain these nodes.
Then: add node X at step 0, add node Y at step 5, remove node Z at step 11, etc.
Probably a pre-requisite for connects/disconnects
There are some sharp edges to the current model that it would be nice to remove...
Specifically, we need solutions for:
NodeJoined
event to the whole network (#29).Network
to re-queue them (to simulate continual resending) (#21).In general, as @Fraser999 noticed, there seems to be a weird mismatch between the simulator having a definitive idea about who is connected to who, and nodes themselves having a local view of their connectivity... I think we either need to define exactly how this relationship should work, or think about structuring it differently...
At the moment we run for a fixed number of steps, but if a churn event occurs on say last_step - 1
, then the network could still be in a forked state when the simulation ends. Instead, we should stop churning at some point and keep running until the message buffer is completely empty.
At the moment, we recompute the sets of valid and current blocks for every vote we receive, because it's simple to do by branching out from a single vote. As an optimisation, we could instead recalculate both sets only once per step. When I profiled the code a while ago (we should do this again), most time was spent recomputing the valid and current blocks.
These functions need to consider only the current blocks relevant to our node (i.e. its chain segments). At the moment they consider the whole network, and expecting any node to be in all current blocks across multiple sections is obviously silly.
With the new paradigm of 1 current block per section, we could simplify the peer states by deleting the code for handling nodes that appear in some but not all current blocks.
Rough plan:
merge.rs
, call function from construct_new_votes
in Node
.Similar to #29
If more than half the nodes in a section flake out, that's a scenario we're not really trying to handle, so we should at least note if something like this happens, or perhaps better, make sure that the simulator doesn't concentrate too many faults in one section.
At the moment we broadcast to the whole network, there's a TODO
in the code to this effect as well.
Title captures it pretty well I think... seems like there might be some gnarly details here though...
We may also need a separate issue for maintaining the blocks between merging and splitting โ even if we use "God mode" to achieve this.
Implement random partial disconnects.
Rough design I had in mind:
Simulation
, similar to drop_node
and join_node
, that does random partial disconnects.Simulation::connections
(in both directions).ConnectionLost
events (messages) to both sides.There's also a possibility we could disconnect A<->B in only one direction, but I think we should try symmetric disconnects for now (an asymmetric one could represent a lost tunnel).
Even if we are disconnected from some nodes which we consider current, we should send messages to them and expect the network to eventually deliver them. In a real network, this could be achieved by keeping a message queue for each disconnected node, but for now we can let the Network
struct act as the message queue.
Should check that at the end of every simulation, all nodes have a compatible view of the network (no forking).
This is currently unimplemented, but seeing as everyone can see the whole network anyway and we're not yet concerned with secure hop messaging, there's no hurry to implement this.
We decided to change the add/remove rules yesterday but the code has not yet been updated. The new rules are similar to the old ones, so should hopefully be straight-forward to implement based on the peer states (we could maybe even copy over the old definition from the history of peer_state.rs
).
We should differentiate between these two so that the code makes more sense. However, lets keep using the Network
to send both events and messages for now, as that saves us from duplicating the delayed delivery behaviour.
This allows us to achieve the "eventual delivery of all votes" as required by the proposal.
I started running the simulation in a loop and it failed on the ~30th iteration because a node that failed to join the network was alive at the end of the simulation but had a different view of the network to everyone else (because everyone else had given up on sending stuff to it).
As a fix, I'm thinking we should have a new method Node::should_shutdown()
that checks if self.our_current_blocks.is_empty() && step >= self.created_step + self_shutdown_timeout
. Here, self.created_step
is a new field that just stores the step that the node was created on, and self_shutdown_timeout
is a timeout parameter (possible equal to join_timeout
?). At the end of each step, the simulation just needs to call node.should_shutdown()
for each node and remove any nodes for which it returns true.
Check connections with the nodes instead... this may result in double-disconnects/double-reconnects if we go to disconnect/reconnect before the node has received the message, but the in-order delivery should mean that this doesn't cause any trouble (we'd just need to remove the warnings about double-disconnects).
If a connection drops, allow it to come back with some probability.
A declarative, efficient, and flexible JavaScript library for building user interfaces.
๐ Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. ๐๐๐
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google โค๏ธ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.