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.

$\endgroup$
  • 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 '18 at 16:41
  • $\begingroup$ @quintumnia That really isn't helpful. Please indicate what you think needs revising. $\endgroup$ – David Richerby Aug 22 '18 at 16:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.