I was reading about the batch dynamic CONGEST model for distributed computing. This model assumes a fixed communication network, but where local inputs to nodes may change over time. It aims to study how efficiently we can update a solution given $\alpha$ local input changes.

Recently, I read about smoothed analysis of dynamic networks. The idea being that we want to see if strong lower bounds will weaken if we make small random perturbations to the problem input. Here the authors apply smoothed analysis to dynamic networks, but I was wondering if it makes sense to apply this analysis to the batch dynamic model where random perturbations are applied to the chosen edge relabeling. This paper applies smoothed analysis to the distributed CONGEST model for the problem of MST. This tells me that applying this to the batch dynamic model could be of interest.

From what I gather, smoothed analysis would be interesting in the batch dynamic model if a problem exists where only a few configurations of local input changes are responsible for the strong lower bound on a problem. Since then we could apply small random changes to these configurations and expect to end up with input changes that allow our algorithms to finish faster.

Which problems in distributed computing could smoothed analysis be applied to under the batch dynamic model and does this even make sense to study?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.