<jupyter_start><jupyter_text>Dynamic Topology over Exponential Two GraphWhen running average consensus based decentralized algorithm, the communication cost is not neglectable usually. In one round, the vector length of communication is proportional to the number of edges -- $O(E)$. Even for exponential graph each node will contain only $O(log(|V|))$ edge, the total communication cost will be $O(|V|log(|V|))$, i.e. $O(Nlog(N))$. This is actually worse than the [ring-allreduce](https://arxiv.org/pdf/1802.05799.pdf) based decentralized algorithm, which only requires $O(2N)$ communication cost. Although ring-structed neighbor allreduce will have similar communication cost, the convergence speed of ring-structure is so slow that it can hinder the gradient descent. Actually, it is shown under some assumptions that ring-allreduce algorithm actually achieve the optimal bandwidth usage for static topology.Fortunately, AWC algorithms or other variantions also work under dynamic topology. It means in each round, the underlying topology is dynamic, i.e., the communication graph $\mathcal{G}^k$ changes with time/iteration $k$. There are many choices for generating dynamic topologies. Among them, this notebook focuses on the *dynamic one peer strategy*, which means all agents only selection one neighbor agents (peer) at each communication around. You can immediate find that the communication cost decreased to $O(N)$ now.When it combined with Exponential graph, you will see that it not only reduces the communications cost but surprisingly accelerates the average consensus speed under mild conditions.<jupyter_code># Consider a static exponential-2 graph with size 16
nx.draw_circular(topology_util.ExponentialTwoGraph(16))<jupyter_output><empty_output><jupyter_text>Under exponential-2 graph, we know the agent $i$ will send the informaiton to $[i+1, i+2, i+4, \ldots, i+2^n]$ module $N$. Then, the dynamic one peer strategy can be easily generated through at iteration $k$, agent $i$ selects the neighbro $i+2^{k\%n}$. It is easy to see that dynamic topology is periodical and the period is $n$. Let's plot the case for exponential-2 graph with size 16, which should have 4 distinct one peer graphs.<jupyter_code>n = 4
size = 2 ** n
G_full = topology_util.ExponentialTwoGraph(size=size)
for k in range(4):
    plt.figure(figsize=(8, 6))
    x = np.array([1.0 if i == 2 ** (k % n) else 0 for i in range(size)])
    x /= x.sum()
    topo = np.empty((size, size))
    for i in range(size):
        topo[i] = np.roll(x, i)
    G = nx.from_numpy_array(topo, create_using=nx.DiGraph)

    nx.draw_circular(G_full, node_size=800, width=2, edge_color="#C2C2C2")
    nx.draw_circular(G, node_size=800, width=2)
    plt.text(
        1,
        -1.2,
        "Iteration K" + ("+" + str(k) if k != 0 else "  "),
        horizontalalignment="right",
        verticalalignment="center",
        fontsize=25,
    )
    plt.show()<jupyter_output><empty_output><jupyter_text>It is not surprising that the communication cost is reduced. But you may wonder when we decrease the communication, will it hinder our convergence speed and eventually undermine the speedup brought by the communication? There is one simple lemma:**Lemma** Suppose $W^{(k)}$ is the combination matrix at iteration $k$ over the dynamic one-peer exponential-2 graph with $N=2^n$ nodes. It holds that each $W^{(k)}$ is doubly-stochastic, i.e., $W^{(k)} \mathbb{1} = \mathbb{1}$ and $\mathbb{1}^T W^{(k)} = \mathbb{1}^T$. Furthermore, it holds that\begin{align}\label{finite-time-average}W^{(k+\ell)} W^{(k+\ell-1)} \cdots W^{(k+1)} W^{(k)}= \frac{1}{n}\mathbb{1}\mathbb{1}^T\end{align}for any integer $k \ge0$ and $\ell \ge n$. Let's verify this in code.<jupyter_code>all_combined_matrix = np.eye(size)
for k in range(4):
    x = np.array([1.0 if i == 2 ** (k % n) else 0 for i in range(size)])
    x /= x.sum()
    topo = np.empty((size, size))
    for i in range(size):
        topo[i] = np.roll(x, i)  # topo does not include self
    W = (np.eye(size) + topo) / 2
    all_combined_matrix = all_combined_matrix @ W
uniform_matrix = np.ones([size, size]) / size
np.all(np.isclose(all_combined_matrix - uniform_matrix, 0))<jupyter_output><empty_output><jupyter_text>Dynamic One Peer Strategy over General TopologySimilarly, we can design one peer strategy over general topology, i.e. every node pick one peer to send at each iterations. BlueFog provided several topology utility functions for several common dynamic topology cases. This dynamic one peer strategy is definitely covered -- `topology_util.GetDynamicOnePeerSendRecvRanks`.It is not a function but [generator](https://docs.python.org/3/tutorial/classes.htmlgenerators) actually. If you are not familar with the concept of generator, don't be afraid. It is easy. Check the following example<jupyter_code>def simple_generator():
    yield 1
    yield 2


g = simple_generator()
print(next(g))
print(next(g))<jupyter_output>1
2<jupyter_text>You should use the `topology_util.GetDynamicOnePeerSendRecvRanks` in a similar style. It takes the `topology` and `self_rank` as input and at each iteration, it returns two lists -- one for the ranks of sending to and another for the ranks of receiving from with respect to that `self_rank`.<jupyter_code>generator = topology_util.GetDynamicOnePeerSendRecvRanks(
    topology_util.ExponentialTwoGraph(size=16), self_rank=0
)
print(next(generator))
print(next(generator))
print(next(generator))
print(next(generator))
print(next(generator))<jupyter_output>([1], [15])
([2], [14])
([4], [12])
([8], [8])
([1], [15])<jupyter_text>Another example of using it over mesh grid topology.<jupyter_code>generator = topology_util.GetDynamicOnePeerSendRecvRanks(
    topology_util.MeshGrid2DGraph(size=16), self_rank=0
)
print(next(generator))
print(next(generator))
print(next(generator))
print(next(generator))
print(next(generator))<jupyter_output>([1], [])
([4], [])
([1], [1, 4])
([4], [])
([1], [])
{'fraction_non_alphanumeric': 0.11774572291177457, 'fraction_numerical': 0.017276081851727607, 'mean_word_length': 4.974949899799599, 'pattern_counts': {'":': 0, '<': 22, '<?xml version=': 0, '>': 22, 'https://': 2, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '6', 'dir': 'jupyter-structured-clean-dedup', 'id': '36849', 'license': 'Apache-2.0', 'n_tokens_mistral': 1882, 'n_tokens_neox': 1787, 'n_words': 665, 'path': 'Section 5/Sec-5.2-Dynamic-topology.ipynb', 'repo_name': 'Bluefog-Lib/bluefog-tutorial', 'size': '5962'}