OFFSET
1,2
COMMENTS
Suppose that each of n agents initially knows a single secret. Each agent is allowed to call each of the others and each time they call they share all the secrets they know at the time. The agents can only learn new secrets; they can never forget one. Imagine the following discrete random process: We randomly select two agents a and b and let them call each other (i.e., we let a learn b's secrets 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.
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 ANY protocol in the literature (see e.g. the paper Dynamic Gossip in the links section) and the secrets graphs reachable by ANY are also called ordered tuples (see the paper Reachability and Expectation in Gossiping in the links section).
For up to 4 agents it is relatively easy to verify 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.
A similar problem was studied by Douglas West (see links). The problem studied by West is similar to ours with the exception that calls are selected under very strict criteria. This allowed West to obtain a closed formula for the number of reachable non-isomorphic graphs with the fewest calls possible. In our case, since such a restriction is absent, we are unable to find a closed formula. So, we believe that developing a program which generates the reachable non-isomorphic graphs is the best we can do.
LINKS
Hans van Ditmarsch, Jan van Eijck, Pere Pardo, Rahim Ramezanian, François Schwarzentruber, Dynamic Gossip, arXiv:1511.00867 [cs.DM], 2015-2018.
Hans van Ditmarsch, Jan van Eijck, Pere Pardo, Rahim Ramezanian, François Schwarzentruber, Dynamic gossip Bulletin of the Iranian Mathematical Society (2018): 1-28.
Hans van Ditmarsch, Ioannis Kokkinis, Anders Stockmarr, Reachability and Expectation in Gossiping, PRIMA 2017: 93-109.
Hans van Ditmarsch, Malvin Gattinger, Ioannis Kokkinis, Louwe B. Kuijer, Reachability of Five Gossip Protocols, Reachability Problems, 13th Int'l Conf. (Brussels, Belgium, RP 2019), Lecture Notes in Computer Science (LNCS Vol. 11674), Springer, Cham, 218-232.
Ioannis Kokkinis, Implementation for Reachability and Expectation in Gossiping
Ioannis Kokkinis The ANY-Reachable Tuples for up to 4 Agents
D. B. West, A class of solutions to the gossip problem, part I, Discrete Math. 39(3), 307-326.
EXAMPLE
For n=1 only the 1-node graph with a self loop is reachable.
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.
An example for the graphs generated for up to 4 agents can be found in the links section.
PROG
(C) /* In order to generate the above sequence install the program given by the github repository in the links section. */
CROSSREFS
KEYWORD
nonn,more
AUTHOR
Ioannis Kokkinis, Aug 19 2018
STATUS
approved