# Gossip protocols

A gossip protocol is a process of computer peer-to-peer communication.It's used by network nodes to share and disseminate information quickly and reliably with each other.

## Dissemination - LNS

Let's take a set of agents, such that each has a secret x. The purpose of gossip protocols is that agents share their secrets to get to a state where they know all the secrets. An agent who knows all the secrets is called an expert. LNS is one of the distributed gossip protocols in which one agent calls another one only if he doesn't know his secret. During a call, the two agents share all the secrets they know.

Let us take an example of 3 agents a, b, c holding secrets A, B, C respectively. Since at the beginning each agent knows only his own secret, everyone can call the two remaining agents.

If a chooses to call b, we obtain this distribution of secrets:

• a : [A, B] , b: [A, B] , c : [C]

Now a and b know each other's secrets, so they can't call each other. if then, c calls a the new distribution is :

• a : [A, B, C] , b: [A, B] , c : [A, B, C]

Here a and c know all the secrets, so they can't make any call, but b doesn't know the secret of c. So the only possible call is that b calls c, we obtain the final distribution.

• a : [A, B, C] , b: [A, B, C] , c : [A, B, C]

More details :

## Aggregation - PushSum

• Problem: Each Agent "i" holds a value v$_i$
• Goal: Compute the average of agents values in the system

More detail :

Algorithm:

• At all times t, each agent "i" maintains two quantities, a sum "s$_{t,i}$" and a weight "w$_{t,i}$" .
• Initially, s$_{0,i}$=v$_i$ and w$_{0,i}$=1

• At each Round t :

• Let {($\hat{s_r}$,$\hat{w_r}$)} be all pairs sent to i in round t − 1
• Let s$_{t,i}$:= $\sum_{r} \hat{s_r}$ and w$_{t,i}$:= $\sum_{r} \hat{w_r}$
• Each agent i selects a uniform random neighbor
• Each agent sends to the selected neighbor half of s$_{t,i}$ and w$_{t,i}$ , and half is kept by this agent
• At time t, the sum estimate is $\frac{s_{t,i}}{w_{t,i}}$

Implementation:

• To implement the synchronous version of push sum we have a "Ticker" agent and a set of n "push" agents:
• Let T be the number of rounds and each push agent has a value v$_i$
• at t=0, s$_{0,i}=v_i$ and w$_{0,i}$=1
• Agent Ticker sends a "Start round" message to push sum agents at the start of each round "t"
• When the push sum agent receives the "Start Round" message , he must do the push, so he selects a random receiver from his list of neighbors to send them half of s$_{t,i}$ and w$_{t,i}$, and he keeps the half
• When a push agent receives the message push, he should add the pair (s$_{t,i}$,w$_{t,i}$) to its own values and inform the Ticker agent.
• When the Ticker agent receives n inform type messages,he starts the next round
• After T rounds, the protocol is ended by Ticker agent

In the example below, we took 3 agents represented in an undirected graph and a ticker agent. In this example, we assume that agent 1 receives the start message first, but in reality it can be agent 2 or 3 .

sequenceDiagram note right of Ticker :First Round Ticker ->> AgentPush1 : startRound(idRound) Ticker ->> AgentPush2 : startRound(idRound) Ticker ->> AgentPush3 : startRound(idRound) note over AgentPush1 : (S1,1 =v1,w1,1=1,neighbors=[Agent2,Agent3]) AgentPush1->>AgentPush2: Push ((1/2*S1,1),(1/2*w1,1)) AgentPush2 ->>Ticker : Inform() note over AgentPush2 : (S1,2=v2,w1,2=1,neighbors=[Agent3,Agent1]) AgentPush2->>AgentPush3: Push((1/2*S1,2),(1/2*w1,2)) AgentPush3 ->>Ticker : Inform() note over AgentPush3 :(S1,3=v3,w1,3=1 ,neighbors=[Agent1,Agent2]) AgentPush3->>AgentPush1: Push((1/2*S1,3),(1/2*w1,3)) AgentPush1 ->>Ticker : Inform() note right of Ticker :Second Round Ticker ->> AgentPush1 : startRound(idRound) Ticker ->> AgentPush2 : startRound(idRound) Ticker ->> AgentPush3 : startRound(idRound) note over AgentPush1 : (S2,1=1/2*S1,1+1/2*S1,3, w2,1=1/2*w1,1+1/2*w1,3) AgentPush1->>AgentPush3: Push((1/2*S2,1),(1/2*w2,1)) AgentPush3 ->>Ticker : Inform() note over AgentPush2 :(S2,2=1/2*S1,2+1/2*S1,1, w2,1=1/2*w1,2+1/2*w1,1) AgentPush2->>AgentPush3: Push((1/2*S2,2),(1/2*w2,2)) AgentPush3 ->>Ticker : Inform() note over AgentPush3 : (S2,3=1/2*S1,3+1/2*S1,2, w2,1=1/2*w1,3+1/2*w1,2) AgentPush3->>AgentPush2: Push((1/2*S2,3),(1/2*w2,3)) AgentPush2->>Ticker : Inform() note right of Ticker :After T Round Ticker ->> AgentPush1 : End Ticker ->> AgentPush2 : End Ticker ->> AgentPush3 : End

In directed graph

sequenceDiagram note right of Ticker :First Round Ticker ->> AgentPush1 : startRound(idRound) Ticker ->> AgentPush2 : startRound(idRound) Ticker ->> AgentPush3 : startRound(idRound) note over AgentPush1 : (S1,1 =v1,w1,1=1,neighbors=[Agent2]) AgentPush1->>AgentPush2: Push((1/2*S1,1),(1/2*w1,1)) AgentPush2 ->>Ticker : Inform() note over AgentPush2 : (S1,2=v2,w1,2=1,neighbors=[Agent3]) AgentPush2->>AgentPush3: Push((1/2*S1,2),(1/2*w1,2)) AgentPush3 ->>Ticker : Inform() note over AgentPush3 :(S1,3=v3,w1,3=1 ,neighbors=[Agent1,Agent2]) AgentPush3->>AgentPush1: Push((1/2*S1,3),(1/2*w1,3)) AgentPush1 ->>Ticker : Inform() note right of Ticker :Second Round Ticker ->> AgentPush1 : startRound() Ticker ->> AgentPush2 : startRound() Ticker ->> AgentPush3 : startRound() note over AgentPush1 : (S2,1=1/2*S1,1+1/2*S1,3, w2,1=1/2*w1,1+1/2*w1,3) AgentPush1->>AgentPush2: Push((1/2*S2,1),(1/2*w2,1)) AgentPush2 ->>Ticker : Inform(idRound) note over AgentPush2 :(S2,2=1/2*S1,2+1/2*S1,1, w2,1=1/2*w1,2+1/2*w1,1) AgentPush2->>AgentPush3: Push((1/2*S2,2),(1/2*w2,2)) AgentPush3 ->>Ticker : Inform() note over AgentPush3 : (S2,3=1/2*S1,3+1/2*S1,2, w2,1=1/2*w1,3+1/2*w1,2) AgentPush3->>AgentPush2: Push((1/2*S2,3),(1/2*w2,3)) AgentPush2 ->>Ticker : Inform() note right of Ticker :After T Round Ticker ->> AgentPush1 : End Ticker ->> AgentPush2 : End Ticker ->> AgentPush3 : End