|
%I #19 Nov 26 2019 20:00:59
%S 1,2,4,15,97,1551,49046
%N Number of non-isomorphic directed graphs reachable by n agents using the LNS protocol.
%C Suppose that each of n agents initially knows a single secret. Agent a is allowed to call agent b on the condition that a does not know the secret initially held by b. Each time two agents call each other they share all the secrets they know at the time. The agents can only learn new secrets; they can never forget one.
%C Imagine the following discrete random process: We randomly select two agents a and b, satisfying the condition that a does not know the initial secret of b, and let them call each other (i.e., we let a learn all the secrets known by b at the time and vice versa). The random process stops when all the agents know all the available secrets. Clearly there are several ways to achieve the situation where every agent knows all the available secrets. During each of these ways several secret distributions are produced. Initially everybody knows only their own secret, after the first call there are two agents who know each other's secret (and of course everybody still knows their own secret), etc.
%C We can nicely represent the above procedure using secrets graphs. A secrets graph is a directed graph where the nodes are the agents and there is an edge between a and b iff a knows the secret of b. Initially the graph contains only self loops; during the procedure edges are added and finally the secrets graph is complete (i.e., when all the agents know all the available secrets). The random process described above is known as the LNS protocol in the literature (see e.g. the paper "Dynamic Gossip" in the links section) and the secrets graphs reachable by LNS are also called ordered tuples (see the paper "Reachability and Expectation in Gossiping" in the links section).
%C For up to 4 agents it is relatively easy to verify by hand that our sequence is correct. For 5, 6 and 7 agents we developed a program for generating the reachable graphs modulo isomorphism. Details and definitions for our program can be found in the paper "Reachability and Expectation in Gossiping" in the links section.
%C If we drop the condition that agent a can call agent b only if a does not know b's initial secret then we get the ANY protocol, i.e., a protocol where every call is possible at any moment (see "Dynamic Gossip"). The sequence of non-isomorphic tuples reachable by ANY is A318154. It is interesting that already with 4 agents a tuple appears that can be reached by ANY but not by LNS (see "Reachability and Expectation in Gossiping"). So the calling condition of LNS strictly shrinks the set of reachable tuples.
%H Hans van Ditmarsch, Jan van Eijck, Pere Pardo, Rahim Ramezanian, François Schwarzentruber, <a href="https://arxiv.org/abs/1511.00867">Dynamic Gossip</a>, arXiv:1511.00867 [cs.DM], 2015-2018.
%H Hans van Ditmarsch, Ioannis Kokkinis, Anders Stockmarr, <a href="https://www.researchgate.net/publication/319331098_Reachability_and_Expectation_in_Gossiping">Reachability and Expectation in Gossiping</a>, PRIMA 2017: 93-109.
%H Hans van Ditmarsch, Malvin Gattinger, Ioannis Kokkinis, Louwe B. Kuijer, <a href="https://doi.org/10.1007/978-3-030-30806-3_17">Reachability of Five Gossip Protocols</a>, Reachability Problems, 13th Int'l Conf. (Brussels, Belgium, RP 2019), Lecture Notes in Computer Science (LNCS Vol. 11674), Springer, Cham, 218-232.
%H Ioannis Kokkinis, <a href="https://github.com/Jannis17/gossip_protocol_expectation">Implementation for Reachability and Expectation in Gossiping</a>
%H Ioannis Kokkinis <a href="https://drive.google.com/file/d/1-YCz0MieU4f2kjrRbd02SWPtiE0dH-wg/view?usp=sharing">The LNS-Reachable Tuples for up to 4 Agents</a>
%e For n=1 only the 1-node graph with a self loop is reachable.
%e For n=2 it is clear that we can reach only 2 graphs: the initial with only self loops and the final complete directed graph with 2 vertices.
%e An example for the graphs generated for up to 4 agents by the LNS protocol can be found in the links section.
%o In order to generate the above sequence install the program given by the github repository in the links section.
%Y Cf. A318154.
%K nonn,more
%O 1,2
%A _Ioannis Kokkinis_, Mar 23 2019
| 