We are interested in analyzing the efficiency of this approach, using techniques from the analysis of randomized algorithms, in particular the analysis of random processes.
For this project, we are interested in the following questions.
- How efficient are different topologies at spreading information?
- What use is a slow spread of information?
The first question is always dependent on the setting of what needs to be optimized; typically, a complete graph as underlying topology gives the fastest spread in information. The second question asks for a setting in which a fast spread of information is not desirable, in other words, a setting in which the underlying topology should not be the complete graph but rather, for example, a ring or torus topology.
The first question has gotten a preliminary answer in ; however, the offered bounds are not tight and can be improved. The second question has not yet been addressed in the literature. Also, the cost of communication has not been sufficiently considered (the complete graph as topology has a high communication overhead, the ring topology only has a very small overhead).