Safe Gossip protocol

Back to important, today we have the initial commit of the Safe gossip protocol.

This algorithm will be used for message retransmission and, comparing with the current implementation, will significantly reduce the number of messages sent between the different nodes, reducing the work required and increasing the speed of the network.

From what little is known, a push-pull algorithm has been chosen. Theoretically, the number of messages needed could be reduced from N² to Nloglog(N) . A huge jump.

43 Likes

Nice detective work @digipl PR’s welcome :wink:

19 Likes

David or @anon86652309, can you give us a one paragraph description - not so much of gossip, but of what this is heading towards.

For example, does this provide a gossip server like interface against which people can build gossip clients, or is it internal to the network?

Is it a way to implement pubsub, or what else?

7 Likes

I assume it has something to do with the following part of MaidSafe Dev Update - January 25, 2018

One important thing that comes up while tweaking the parameters is the average and peak section sizes. While the average is pretty good, the peak sizes sometimes make us wonder if we could be more efficient given those many nodes in a section. Currently, the Elders are all connected to every peer in their section and the swarm strategy is O(n^2) for votes and blocks. We will also be deeply looking into secure gossip and finding out if we can design a system which addresses both: not forcing connection among everyone (thus frugal use of socket descriptors) and also making swarm ideally logarithmic.

7 Likes

Is it correct to see it like this change will give a faster network, like in comparison the speed of different sorting alghoritms?

4 Likes

Just via vanilla gossip, you’d be reducing the amount of messages required to disperse a message between a given set of peers massively. Quite a lot of resources about the topic, one interesting presentation giving an overview.

In terms of what it is heading towards, starting off expecting it to get used in the internals of the system by nodes to exchange required info(votes/blocks/messages/…). This has been something we’ve intended to have for the routing layer and so on and just getting it done essentially. think @draw identified that part ^^.

It should certainly make comms a whole lot more efficient. This crate should showcase benchmarks itself too to draw such conclusions of the efficiency between patterns and complexities.

14 Likes

@dugcampbell Would it be possible for dev updates to have one or a few lines of, simple text, that highlights benefits or implications for the network of significant improvements. Just a thought i had that sometimes I understand that a improvement means alot but can’t quite wrap my head around what it does. :slight_smile: I think it would mean alot to many people following. Awesome work and progress with Safe-gossip protocol!

7 Likes

Good idea - I agree, anything we can do to simplify the info coming out so it’s understandable for everyone is a win for us all. Will have a think about what we can do here for next week’s Dev update :slight_smile:

13 Likes

How does this particular implementation of gossip within safe network compare to the “gossip about gossip” implementation applied by Hashgraph?

2 Likes

This is pure gossip with signatures. So secured push-pull gossip protocol. This is more general purpose, but the impl will make the message type generic allowing any type of message/event to be passed around. Hashgraph for instance could use this as a basis for event transmission, but that is just a use case of gossip, there are a great many such cases.

In hashgraph the gossip about gossip is really using parent events (linked via hashes in each event) to create a DAG. the clever part though is using an algorithm for event connectivity (a bit like k graph connectivity) that allows events to be identified as strongly seen and then a further round to ensure a super majority (over 2/3) can all attest via the same structure (DAG) that the super majority again can all see the previously well connected events (called famous). There is some additional things to consider such as what they call witnesses etc. but basically it is gossip transfer of messages and these have a graph like structure.

So hashgraph is an impl on gossip, I think IOTA is as well. Gossip is really a standard way to transfer data amongst nodes on a network with very high degrees of probability that are all seen and as @digipl noted, this can be nlog(n) rounds and nloglog(n) messages, which is very efficient. Our current swarm is much more basic in that it is at least n^2 messages, which is fine for testing and getting other parts in place, but really it should be much more efficient and faster.

21 Likes

For the odd case that a data message is not seen by all nodes: could that be a problem?

2 Likes

Thank you for the explanation, David. What you are building is very sound and combines so many different protocols (e.g., citations of Petar’s kademlia, close group consensus, data chains, etc.). The closer one looks, the more impressed they are.

11 Likes

No, not for us, as long as quorum (majority) see the message we are golden. As all the votes create a valid block (with quorum) then that block is then again sent around all nodes. So the odd miss is Ok in fact we can miss out easily 1/3 of nodes and likely up to 50%.

15 Likes

Thanks, Dug, appreciate it. Always looking to improve. :slight_smile:

1 Like

I was also wondering and interested in understanding if this could be the foundations to have a publish/subscribe mechanism in safenet, perhaps a non-persistent one, i.e. not stored on the vaults/chunk store, with some TTL included.

Perhaps I’m getting this veeeery wrong, but based on your comment David, I was thinking if we could use this gossip protocol to allow an app to send a request which is transformed to a particular type of event (in the gossip protocol) within the targeted node’s group.

I know this might not make any sense, but here I go anyway, e.g.:

1- My “live weather” app publishes a MD (let’s call it the ‘weather events MD’) with a specific type tag that triggers the “creation” of a gossip event type.
Different topics for the same gossip event type could be defined by the app in the MD as entries, let’s say my app puts two topics by having two entries (this would be specific to the app’s protocol spec. just so subscribers know which type of topics they can subscribe to, again, purely application specific):

[
   "temperature" => <MD 'A' xorname which contains up to date info about temperature>,
   "humidity" => <MD 'B' xorname which contains up to date info about humidity>
]

2- Then another app can send a “subscribe” request to the ‘weather events MD’ address (specifying the topic/s of interest), therefore nodes in the targeted group could maintain the subscriber’s connection end in a in-memory table (I’m not fully sure about the challenge/restrictions for having a connection end to send a message to a client app), which would be accomplished by just sending an “update subscriptions table” gossip event internally within the group.

3- When my “live weather” app updates the current temperature in MD ‘A’ because it sensed a change in current temperature, it then sends a “notify” request to the ‘weather events MD’ group, which causes the targeted group to check the in-memory subscriptions table and sending a notification message to each subscriber/client app (they can correlate the topics each subscribed to with the topic defined in the notification request).

It seems to me that if all this makes sense, the toughest part could probably be preventing it from spammers, but perhaps this could be handled in a analogous way as of persistent storage, having a different persona that can farm only these non-persistent events in memory, earning some safecoins by keeping the subscriptions table in memory, and having the apps to also pay for this subscriptions and notifications messages,…and we would be already enabling farming on mobiles :open_mouth: !? what??? :smiley:

10 Likes

This makes pretty good sense to me, from my no-technically adept position, but it does lead me to wonder how much traffic and burden this would place on nodes if a lot of different apps started using it to do a lot of different things. Though I guess if the app is paying for every PUT to the MD for each parameter, that would help balance things.

2 Likes

@dirvine – Has any of this (SAFE Gossip Protocol) changed with the introduction of PARSEC? Is the SAFE gossip protocol unique? Will it be GPL too or is it included under PARSEC GPL license?

cheers

Gossip is a communication protocol and PARSEC is a complete BFT consensus that use gossip as procedure of communication. So this topic is overtake by PARSEC.

2 Likes

So you are saying that this topic’s version of gossip protocol is null/void by new PARSEC gossip protocol?

If so, is the new gossip protocol in PARSEC unique or taken from other open-source code somewhere else?

I’m asking all this as someone has questioned the originality and legal status of Maidsafe’s gossip protocol on my recent video on PARSEC. So I am seeking clarification so that I can say with confidence that current gossip protocol implementation is open source.

The gossip protocol is a well established algorithm. PARSEC uses this protocol, but we don’t change it. We will probably end up implementing it ourselves so it fits with the precise way we want to use it, but that’s a detail.

PARSEC didn’t innovate by making gossip better, or anything. We use gossip because it’s very well suited for asynchronous BFT type things, as shown in recent literature. Our innovations are mostly about finding a way to look at gossip communications, and finding a way to deduce a consensused order based on them.

9 Likes