Finding the K largest metrics in a noisy broadcast network
Chengzhi Li, Huaiyu Dai, Husheng Li · 2008
Distributed computing in an N-node noisy broadcast network is considered. Each node holds an n-bit integer as an input instead of a binary input assumed by most work in literature. The goal is for all the nodes to find out the K largest values with fault tolerance Q. We focus on protocol designs for the K = o(Nbeta) scenario, and investigate the communication complexity, i.e., the total number of broadcasts, with respect to various parameters: N, n,K. In particular, we show that the goal can be achieved by an oblivious protocol of complexity O(nN log K/Q ), admitting linear growth with n and N and sublinear growth with K.