Revised project aims

Quick project goal:The main goal of this project is to study the information dissemination task of $k$-gossip under smoothing. $k$-gossip is a fundamental primitive in distributed networks and can be used to enforce data replication which has applications in the very popular blockchain networks. I want to see how $k$-gossip's lower and upper bounds are affected in dynamically changing networks if we introduce smoothing to the network graph for each round of synchronous communication. This will give us a better understanding of how efficient our current algorithms are on "realistic" inputs for $k$-gossip.

The revised project aims are as follows:

1. Present known unsmoothed and smoothed lower and upper bounds for flooding and the maximum hitting time of a random walk against oblivious adversaries, as an introduction to the techniques used for the later analysis of $k$-gossip.
2. Present/Develop unsmoothed lower and upper bounds for $k$-gossip against an oblivious adversary.
3. Present the known unsmoothed lower and upper bounds for $k$-gossip against an adaptive adversary.
4. Use 2 to develop smoothed lower and upper bounds for $k$-gossip against an oblivious adversary.
5. Use 3 to develop smoothed lower and upper bounds for $k$-gossip against an adaptive adversary.

Aims 4 and 5 will take the bulk of my time since these would be new results if completed successfully. If I fail to complete 3 and 4, I may replace them with the implementation of the best known algorithm for $k$-gossip on dynamic graphs against an oblivious/adaptive adversary. The program could then compare the runtime of its unsmoothed input to its smoothed input.

Progress made:

• Presented $\Omega(n^{2/3}/k^{1/3})$ smoothed lower bound for flooding against an oblivious adversary. (part of aim 1)
• Presented $\Omega(n\log{k})$ unsmoothed lower bound for $k$-gossip against an adaptive adversary. (part of aim 3)

Plan for Christmas holiday:

1. Complete aim 1.
2. Complete aim 2.
3. Complete aim 3.

Progress reflection: I am currently behind schedule because I have not managed my workload for this term well. I also did not allocate enough time in term 1 for just gaining the relevant background to tackle aims 4 and 5. My goal is to make up for my lateness over Christmas where I will be able to focus purely on my project.

This will mean term 2 will be entirely focused on the hardest aims: 4 and 5. The Christmas holidays will be used as a way to complete all preliminaries needed to give me the background to tackle 4 and 5.