1
$\begingroup$

Suppose we have a peer to peer network of, say, $n$ peers. Peers communicate by an asynchronous randomized gossip protocol (Push, Pull, Push/Pull doesn't really matter here). The task is for any local peer to get an (approximate) picture of the global communication in all of the network over time.

I mean after some time $t_1$, each local peer $k$ should have a data structure that is the record of every gossip event that took place in all of the network up to a time $t_2$, with $t_2\leq t_1$. This data structure should provide knowledge about the appearance of events globally over space and time.

To make it "simple", we can assume, that communication channels never fail. Every peer can reach every peer. However since peers might crash or disappear, we can not just choose some central peer that records everything and then redistributes its knowledge.

A solution exist in the so called hashgraph algorithm, which goes roughly as follows:

Every peer stores locally a directed acyclic graph, to record the gossip events. Vertices are the gossip event together with an identifier of sender and receiver. Each vertex has two incoming edges, which might be called $sender\_parent$ and $receiver\_parent$. $sender\_parent$ is an edge from the previous gossip event of the sender and $receiver\_parent$ is an edge from the previous gossip event of the receiver. Outgoing edges are of arbitrary number.

Each time a peer connects to another peer it askes for the previous gossip event of the receiver, then creates a new vertex locally to record *this event. Then it transfers all of the graph along to the other peer. (This is a simplification for the push protocol and can be tweaked appropriately for pull or push/pull as well)

The question now is, whether or not this is essentially (up to isomorphism) the only way to do it. The hashgraph algorithm is patented. Therefore it would be good to know if other solutions exist. With such local to global views, network analysis can be quite efficient.

Edit: The system is free to implement any kind of communication contend, which makes the task possible.

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ Can you be a bit more precise? Hard to say from my perspective, what exactly is not completely clear. $\endgroup$
    – Mark Neuhaus
    Aug 22, 2018 at 16:41
  • $\begingroup$ @quintumnia That really isn't helpful. Please indicate what you think needs revising. $\endgroup$
    – David Richerby
    Aug 22, 2018 at 16:46

1 Answer 1

Reset to default
1
$\begingroup$

Another solution would be to use SWIM gossip (Scalable Weakly-consistent Infection-style Process Group Membership Protocol), or it derivatives like Serf (which includes the vivaldi network and SWIM) or even Consul (which implements raft consensus, key value store, and Serf).

Improve this answer
$\endgroup$
4
  • $\begingroup$ Can you briefly explain what these tools guarantee, and how they accomplish it? $\endgroup$
    – Yuval Filmus
    Jan 20, 2021 at 8:40
  • $\begingroup$ i'm not an expert on the topic. But the papers are fascinating to read! I personally like vivaldi more than SWIM $\endgroup$
    – Max N
    Jan 20, 2021 at 10:45
  • $\begingroup$ I notice you've recently written four answers mentioning SWIM. Would you be willing to share whether you have any affiliation or connection with SWIM, and if so, what it is? $\endgroup$
    – D.W. ♦
    Jan 20, 2021 at 22:48
  • $\begingroup$ I'm not sure that this answers the question. The question asks whether every way to do it is essentially isomorphic to hashgraph. You suggest SWIM, but it's not clear to me whether SWIM is essentially isomorphic to hashgraph or not. Any community opinions? $\endgroup$
    – D.W. ♦
    Jan 20, 2021 at 22:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.