A multi-agent consensus protocol is investigated over noisy undirected connected graphs. It is supposed that each agent can know her neighbors' states with bounded noise. A theoretical stopping rule having a probabilistic guarantee is established for the consensus protocol, which explicitly relates the number of iterations with the closeness of the agreement. The stopping rule is derived by utilizing Bernstein inequality that deals with a given noise bound explicitly. The sample complexity with respect to the number of agents is also investigated, where it is shown that the number of iterations required by the proposed stopping rule based on the bound of noise itself is generally smaller than that of the conventional stopping rules that utilize bound of noise variance. The results are demonstrated through numerical examples.
展开▼