michaelsproul / ewok

Simulator for a distributed fuzzy ordering algorithm

Ewok

Ewok is a proof-of-concept algorithm for establishing an eventually consistent view of the members of a decentralised network like the SAFE network.

Why's it called Ewok?

Because Ewoks are fuzzy, and the algorithm obtains a fuzzy ordering of events on the network...

ewok's Issues

Optimise current and valid block calculation

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.

Update the add and remove rules again

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).

Eventual consistency checking

Should check that at the end of every simulation, all nodes have a compatible view of the network (no forking).

Allow nodes to self-shutdown

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.

Remove Simulation::connections

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).

Fix in_all_current, in_some_current

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.

Merges

Rough plan:

• Implement in a similar way to splits, new file merge.rs, call function from construct_new_votes in Node.
• Keep a map from prefixes to the timestamp (step) at which a block with that prefix last became current (this is required for AddConv).

Rethink/restructure connections and peer state management

There are some sharp edges to the current model that it would be nice to remove...

Specifically, we need solutions for:

• A joining node shouldn't send its NodeJoined event to the whole network (#29).
• Nodes shouldn't keep peer states for peers that are no longer neighbours because of splits (#31).
• Nodes shouldn't broadcast their Votes to peers that are no longer neighbours (#22).
• Messages shouldn't be dropped completely because of temporary disconnects – perhaps we can use the 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...

Connections should be dynamically adjusted while merging and splitting

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.

Limit or monitor the fraction of each section that exhibits faults

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.

Allow setting the simulation up with a fixed set of nodes and events

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.

Reconnects

If a connection drops, allow it to come back with some probability.

Consider deleting PeerState::PartiallyConfirmed and in_some_current

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.

Make deterministic based on a seed

Requeue messages instead of dropping them

This allows us to achieve the "eventual delivery of all votes" as required by the proposal.

Seperate events and messages into distinct types

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.

Joining node should send its NodeJoined only to its potential sections

At the moment we broadcast to the whole network, there's a TODO in the code to this effect as well.

Vote for blocks witnessing neighbouring sections

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.

Add TravisCI?

ConnectionLost events should only be sent to the removed node's sections

Similar to #29

Broadcast votes to our current sections and their neighbours

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.

Partial disconnects

Implement random partial disconnects.

Rough design I had in mind:

• Add a method to Simulation, similar to drop_node and join_node, that does random partial disconnects.
• When a partial disconnect happens it should be sufficient to:
  1. Remove the connection from Simulation::connections (in both directions).
  2. Send 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).

In-order message delivery

Probably a pre-requisite for connects/disconnects

Run until message sending stops

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.

Drop multiple nodes at once