fast multi-log sync about peer-crdt HOT 23 OPEN

@pgte I've been trying to encourage ipfs peeps to use this protocol for a while! I'm glad you've seen this! Lets collaborate on a spec we can use in both ssb and ipfs! I am beginning to roll out support for this into ssb, but my aim is to make an implementation that is sufficiently flexible for other protocols to use. https://github.com/dominictarr/epidemic-broadcast-trees

I'd expect that ipfs will want to use different encoding, but I figure if we can separate the wire protocol, we can use a shared implementation of the behaviour. (our reference implementation is javascript, but we also have a go implementation underway or coming soon)

from peer-crdt.

Just watched @dominictarr 's talk about scalable secure scuttlebutt (video here) — thanks @olizilla! — and there are some ideas that have some parallel here:

from peer-crdt.

@pgte am happy to answer any questions - just post issues on the epidemic-broadcast-trees module, I guess.

from peer-crdt.

@diasdavid @vmx This solution is more specific than IPLD graph-swap, since it's tailored for the multi-log data structure, but I think we need to introduce vector clocks to keep track of remote state. What do you think?

from peer-crdt.

Eager and lazy connections:

Turning the redundant connections from eager into lazy is a great idea, which I think we can apply here. I was worried of the redundancy of operation transmission for when there are more than 2 replicas. I think we could solve this this way, making an intelligent use of vector clocks. (A vector clock transmits the information that I know about, if a replica needs new information about a different replica and the specific replica is not in the network, that replica can explicitly ask another replica for that, (instead getting those operations pushed)).

from peer-crdt.

Optimizing vector clock transmission

Instead of broadcasting the entire vector clock to every peer, send only the vector clock differences to each peer individually.

from peer-crdt.

Hi @dominictarr o/ , good to see you around! :)

Pinging @vyzo who has been working on an epidemic-broadcast-trees as well

from peer-crdt.

I should point out that epidemic broadcast trees behave very poorly with multiple/random sources.

from peer-crdt.

oh, I should probably make clear: in ssb we use ebt in the "protocol instance per source" mode. since you are also talking about replicating logs, I think we are in the same situation.

from peer-crdt.

@dominictarr thanks so much for reaching out!
This looks like it's just what is needed here, thank you for abstracting this into its own package!
I'll take a look at the code and see how this can be plugged.

I wouldn't worry too much about the encoding as we're going to use multiplexed p2p switch connections which expose a raw stream, so we can use whatever.

I'll be taking a look at the code and getting more familiar with EBT and trying to integrate them here. Sounds good?

from peer-crdt.

You should also check out our progress with gossipsub:
libp2p/go-libp2p-pubsub#67

We want to have a mode for single/fixed source epidemic optimizations in the next iteration.

from peer-crdt.

@vyzo is the a discription of the design that is higher level than the protocol? like what performance properties is it expected to have GRAFT and PRUNE seem a bit like EBT but it's hard to tell whats intended

from peer-crdt.

The intention is to build a mesh of a bounded degree; basically mold floodsub to something that doesn't blow up from amplification as you build larger overlays.
Wrt performance, there are some sample simulations in https://github.com/vyzo/gerbil-simsub; I have run a lot more, and the samples are representative.

The protocol could be turned into EBT by sending GRAFT/PRUNE in response to gossip/late messages, although some care must be exercised for stability. It might be more appropriate to use a CHOKE message for suppressing flow from late messages without severing the link.

from peer-crdt.

@vyzo by degree you mean the number of connections? as in https://en.wikipedia.org/wiki/Degree_(graph_theory)

I still don't understand what GRAFT and PRUNE do. are they messages a peer send to another peer?
do they have an argument (such as what source they are about?)

from peer-crdt.

The number of active connections used by the overlay to propagate messages; it's totally the node degree in graph theoretic sense.

GRAFT and PRUNE are sent between peers to forge the overlay. They have the topic as "argument", there is no notion of single source in the protocol level.

from peer-crdt.

@vyzo is it possible to put gossip sub into a "lazy mode" where it sends a message that you have received an item, but without sending the whole thing - and is that is associated with the subscription channel somehow?

from peer-crdt.

hmm, but I'm guessing that "IHAVE" messages are just hashes (as in the style of the ipfs replication protocol)

from peer-crdt.

You want to just send IHAVE messages in place of forwarding the actual messages? It is possible, but it's not implemented that way.
What do you have in mind?

from peer-crdt.

The IHAVE messages contain seen message ids in the last 3 seconds, they are not hashes.

from peer-crdt.

@vyzo what is a message id? if it's not a hash is it channel_id+sequence or channel_id+timestamp? (in my ebt, channel id + sequence are used for replication, but in all other situations ssb uses hash as id)

from peer-crdt.

The message id is constructed using the sender ID together with an atomic counter.

from peer-crdt.

@vyzo this is a bit obscure to me.. is there a place where this gossip-sub protocol is described in a more abstract / reusable way?

from peer-crdt.

@pgte there is https://github.com/vyzo/gerbil-simsub; it looks like it's time to make a spec pr in libp2p-specs though.

from peer-crdt.