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 :
-
van Ditmarsch, Hans, Ioannis Kokkinis, and Anders Stockmarr. Reachability and expectation in gossiping. International Conference on Principles and Practice of Multi-Agent Systems. Springer, Cham, 2017
-
Apt, K. R., Grossi, D., van der Hoek, W. (2016). Epistemic protocols for distributed gossiping.
Aggregation - PushSum
- Problem: Each Agent "i" holds a value v_i
- Goal: Compute the average of agents values in the system
More detail :
- Kempe, D., Dobra, A., & Gehrke, J. (2003, October). Gossip-based computation of aggregate information. In 44th Annual IEEE Symposium on Foundations of Computer Science, 2003. Proceedings. (pp. 482-491). IEEE
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 .
In directed graph