We propose a novel generalized cellular automaton (GCA) model for discrete-time pulse-coupled oscillators and study the emergence of synchrony. Given a finite simple graph and an integer n >= 3, each vertex is an i...
详细信息
We propose a novel generalized cellular automaton (GCA) model for discrete-time pulse-coupled oscillators and study the emergence of synchrony. Given a finite simple graph and an integer n >= 3, each vertex is an identical oscillator of period n with the following weak coupling along the edges: each oscillator inhibits its phase update if it has at least one neighboring oscillator at a particular "blinking" state and if its state is ahead of this blinking state. We obtain conditions on initial configurations and on network topologies for which states of all vertices eventually synchronize. We show that our GCA model synchronizes arbitrary initial configurations on paths, trees, and with random perturbation, any connected graph. In particular, our main result is the following local-global principle for tree networks: for n is an element of {3, 4, 5, 6}, any n-periodic network on a tree synchronizes arbitrary initial configuration if and only if the maximum degree of the tree is less than the period n. (C) 2015 Elsevier B.V. All rights reserved.
Consider a distributed network in which up to a third of the nodes may be Byzantine, and in which the non-faulty nodes may be subject to transient, faults that alter their memory in air arbitrary fashion. Within the c...
详细信息
ISBN:
(纸本)9781595939890
Consider a distributed network in which up to a third of the nodes may be Byzantine, and in which the non-faulty nodes may be subject to transient, faults that alter their memory in air arbitrary fashion. Within the context of this model. we are interested in the digital clock synchronization problem;which consists of agreeing oil bounded integer counters, and increasing these counters regularly. It has been postulated in the past that, synchronization cannot be solved in a Byzantine tolerant and self-stabilizing first. solution to this problem tu had an expected manner. exponential convergence time. Later, a deterministic solution was, published with linear convergence time, which is optimal for deterministic solutions. In the current paper we achieve an expected constant convergence time. We thus obtain the optimal probabilistic solution, both in terms of convergence time and in terms of resilience to Byzantine adversaries.
暂无评论