关键词：通信网络；分布式；算法
摘 要：We summarize three problems. In the first problem, we study the impact of communication constraints on delay-critical problems of distributed computation. We consider networks of agents, each having access to some partial information, which aim at computing some application-specific function of the global information. Computation has to be ompletely distributed, i.e., agents can rely on the local observations only, while iteratively processing the available information, and communicating through digital noisy channels. As large delays can be detrimental for the overall system performance, it is critical to design distributed algorithms which perform such computation in the quickest possible way. We present tight lower bounds on the computation delay that capture the connectivity of the network as well as the channel characteristics.