In this article, we establish orientation and connectivity based criteria for the agreement algorithm to achieve asymptotic consensus in the context of time-varying topology and communication delays. These criteria unify and extend many earlier convergence results on the agreement algorithm for deterministic and discrete-time multiagent systems.
After writing the proof of Theorem , we became aware of two recent papers both containing Theorem in the synchronous case. @cite_14 , Hendrickx and Tsitsiklis showed that the agreement algorithm achieves asymptotic consensus under assumptions A, B with @math , D1 and the so-called cut-balance condition. In light of Proposition below, the latter condition turns out to correspond to the decentralized model. Independently, Touri and Nedi 'c @cite_7 established a general convergence result for the infinite product of random stochastic matrices, and to do that, they first proved that this result holds in the deterministic case; see Lemma 5 in @cite_7 . It is easy to see that this lemma actually coincides with our Theorem in the particular case of a synchronous multiagent system. In fact, our technique for proving the lemmas in Sections and infra specialized to @math , is similar to the one used for the proof of the deterministic result in @cite_7 .
@cite_14 @cite_7
1842280653 2949839621
A recent theorem of [arXiv:0910.1824v2, 2010], proved using results about the cluster expansion in statistical mechanics, extends the Lovasz local lemma by weakening the conditions under which its conclusion holds. In this note, we prove an algorithmic analogue of this result, extending Moser and Tardos's recent algorithmic local lemma [J. ACM, 57 (2010), 11], and providing an alternative proof of the theorem of applicable in the Moser--Tardos algorithmic framework. The celebrated Time Hierarchy Theorem for Turing machines states, informally, that more problems can be solved given more time. The extent to which a time hierarchy-type theorem holds in the distributed LOCAL model has been open for many years. It is consistent with previous results that all natural problems in the LOCAL model can be classified according to a small constant number of complexities, such as @math , etc. In this paper we establish the first time hierarchy theorem for the LOCAL model and prove that several gaps exist in the LOCAL time hierarchy. 1. We define an infinite set of simple coloring problems called Hierarchical @math -Coloring . A correctly colored graph can be confirmed by simply checking the neighborhood of each vertex, so this problem fits into the class of locally checkable labeling (LCL) problems. However, the complexity of the @math -level Hierarchical @math -Coloring problem is @math , for @math . The upper and lower bounds hold for both general graphs and trees, and for both randomized and deterministic algorithms. 2. Consider any LCL problem on bounded degree trees. We prove an automatic-speedup theorem that states that any randomized @math -time algorithm solving the LCL can be transformed into a deterministic @math -time algorithm. Together with a previous result, this establishes that on trees, there are no natural deterministic complexities in the ranges @math --- @math or @math --- @math . 3. We expose a gap in the randomized time hierarchy on general graphs. Any randomized algorithm that solves an LCL problem in sublogarithmic time can be sped up to run in @math time, which is the complexity of the distributed Lovasz local lemma problem, currently