0 as ? ? 0 by the no generation condition (F2) of SPF, there exists a ? 1 < ? 0 such that µ T (s ? 1 ) = ? by the intermediate value property of continuity. By the bounded stabilization time condition (F5), there are no transitions ,
Discrete max-plus spectral theory, Idempotent Mathematics and Mathematical Physics, pp.53-78, 2005. ,
DOI : 10.1090/conm/377/06984
URL : https://hal.archives-ouvertes.fr/inria-00000968
Random walks on finite groups and rapidly mixing markov chains, Séminaire de probabilités de Strasbourg, pp.243-297, 1983. ,
DOI : 10.1214/aop/1176994578
Shuffling Cards and Stopping Times, The American Mathematical Monthly, vol.93, issue.5, pp.333-348, 1986. ,
DOI : 10.2307/2323590
Strong uniform times and finite random walks, Advances in Applied Mathematics, vol.8, issue.1, pp.69-97, 1987. ,
DOI : 10.1016/0196-8858(87)90006-6
The Designers Guide to VHDL, 2008. ,
Complexity of network synchronization, Journal of the ACM, vol.32, issue.4, pp.804-823, 1985. ,
DOI : 10.1145/4221.4227
Interaction ruling animal collective behavior depends on topological rather than metric distance: Evidence from a field study, Proceedings of the National Academy of Sciences, pp.1232-1237, 2008. ,
DOI : 10.1073/pnas.0711437105
Concurrency in heavily loaded neighborhoodconstrained systems, ACM Transactions on Programming Languages and Systems, vol.11, issue.4, pp.562-584, 1989. ,
Short Random Walks on Graphs, SIAM Journal on Discrete Mathematics, vol.9, issue.1, pp.19-28, 1996. ,
DOI : 10.1137/S0895480194264988
Equivalence of the arbiter, the synchronizer, the latch, and the inertial delay, IEEE Transactions on Computers, vol.32, issue.7, pp.603-614, 1983. ,
Logical modelling of delay degradation effect in static CMOS gates, IEE Proceedings ? Circuits, Devices, and Systems, pp.107-117, 2000. ,
DOI : 10.1049/ip-cds:20000197
Logic-Timing Simulation and the Degradation Delay Model, 2006. ,
Convergence in multiagent coordination, consensus, and flocking, Proceedings of the 44th IEEE Conference on Decision and Control, and the European Control Conference (CDC-ECC), pp.2996-3000, 2005. ,
Coupling time of a (max,plus) matrix, Proceedings of the Workshop on Max-Plus Algebra at the 1st IFAC Symposium on System Structure and Control, 2001. ,
URL : https://hal.archives-ouvertes.fr/inria-00100573
An algorithmic toolbox for network calculus. Discrete Event Dynamic Systems, pp.3-49, 2008. ,
URL : https://hal.archives-ouvertes.fr/inria-00123643
Universal computation and other capabilities of hybrid and continuous dynamical systems, Theoretical Computer Science, vol.138, issue.1, pp.67-100, 1995. ,
On a Problem of Partitions, American Journal of Mathematics, vol.64, issue.1/4, pp.299-312, 1942. ,
DOI : 10.2307/2371684
Combinatorial Matrix Theory, 1991. ,
On the delay-sensitivity of gate networks, IEEE Transactions on Computers, vol.41, issue.11, pp.1349-1360, 1992. ,
Analysis of Link Reversal Routing Algorithms, SIAM Journal on Computing, vol.35, issue.2, pp.305-326, 2005. ,
DOI : 10.1137/S0097539704443598
Reaching a Consensus in a Dynamically Changing Environment: A Graphical Approach, SIAM Journal on Control and Optimization, vol.47, issue.2, pp.575-600, 2008. ,
DOI : 10.1137/060657005
Reaching a Consensus in a Dynamically Changing Environment: Convergence Rates, Measurement Delays, and Asynchronous Events, SIAM Journal on Control and Optimization, vol.47, issue.2, pp.601-623, 2008. ,
DOI : 10.1137/060657029
The drinking philosophers problem, ACM Transactions on Programming Languages and Systems, vol.6, issue.4, pp.632-646, 1984. ,
DOI : 10.1145/1780.1804
Orientation and connectivity based criteria for asymptotic consensus, 2013. ,
Full Reversal Routing as a Linear Dynamical System, Proceedings of the 18th International Colloquium on Structural Information and Communication Complexity (SIROCCO), pp.101-112, 2011. ,
DOI : 10.1007/BFb0022451
Partial is Full, Proceedings of the 18th International Colloquium on Structural Information and Communication Complexity (SIROCCO), pp.113-124, 2011. ,
DOI : 10.1007/978-3-642-05434-1_10
The Heard-Of model: computing in distributed systems with benign faults, Distributed Computing, vol.384, issue.3, pp.49-71, 2009. ,
DOI : 10.1007/s00446-009-0084-6
-Energy of a Multiagent System, SIAM Journal on Control and Optimization, vol.49, issue.4, pp.1680-1706, 2011. ,
DOI : 10.1137/100791671
URL : https://hal.archives-ouvertes.fr/hal-01179401
Laplacians and the Cheeger Inequality for Directed Graphs, Annals of Combinatorics, vol.9, issue.1, pp.1-19, 2005. ,
DOI : 10.1007/s00026-005-0237-z
Algebraic tools for the performance evaluation of discrete event systems, Proceedings of the IEEE, vol.77, issue.1, pp.39-85, 1989. ,
DOI : 10.1109/5.21069
Analyse du comportement périodique de systèmes de production par la théorie des dio¨?desdio¨?des, INRIA Research Report, vol.191, 1983. ,
A linear-system-theoretic view of discrete-event processes and its use for performance evaluation in manufacturing, IEEE Transactions on Automatic Control, vol.30, issue.3, pp.210-220, 1985. ,
DOI : 10.1109/TAC.1985.1103925
Trends and challenges in VLSI circuit reliability, IEEE Micro, vol.23, issue.4, pp.14-19, 2003. ,
DOI : 10.1109/MM.2003.1225959
Periods of Connected Networks and Powers of Nonnegative Matrices, Mathematics of Operations Research, vol.2, issue.1, pp.20-24, 1977. ,
DOI : 10.1287/moor.2.1.20
Geometric Bounds for Eigenvalues of Markov Chains, The Annals of Applied Probability, vol.1, issue.1, pp.36-61, 1991. ,
DOI : 10.1214/aoap/1177005980
Fault-tolerant algorithms for tickgeneration in asynchronous logic: Robust pulse generation, Proceeding of the 13th International Symposium on Stabilization , Safety, and Security of Distributed Systems (SSS), pp.163-177, 2011. ,
Self Stabilization, Journal of Aerospace Computing, Information, and Communication, vol.1, issue.6, 2000. ,
DOI : 10.2514/1.10141
URL : https://hal.archives-ouvertes.fr/inria-00627780
Dynamic analysis of repetitive decision-free discreteevent processes: The algebra of timed marked graphs and algorithmic issues, Annals of Operations Research, vol.15, issue.5, pp.150-193, 1990. ,
DOI : 10.1007/BF02248590
Gaps in the exponent set of primitive matrices, Illinois Journal of Mathematics, vol.8, issue.4, pp.642-656, 1964. ,
The use of a synchronizer yields the maximum computation rate in distributed networks, Theory of Computing Systems, vol.5, issue.9, pp.447-474, 1997. ,
DOI : 10.1007/BF02679457
On the threat of metastability in an asynchronous fault-tolerant clock generation scheme Reconciling fault-tolerant distributed computing and systems-on-chip, Proceedings of the 15th IEEE International Symposium on Asynchronous Circuits and Systems (ASYNC) Distributed Computing, pp.127-136, 2009. ,
Digital Device Error Rate Trends in Advanced CMOS Technologies, IEEE Transactions on Nuclear Science, vol.53, issue.6, pp.3466-3471, 2006. ,
DOI : 10.1109/TNS.2006.886212
Asymptotic optimality of shortest path routing algorithms, IEEE Transactions on Information Theory, vol.33, issue.1, pp.83-90, 1987. ,
DOI : 10.1109/TIT.1987.1057274
Computers and Intractability: A Guide to the Theory of NP-Completeness, 1979. ,
The max-plus algebra approach to transportation problems, Proceedings of the 8th World Conference on Transport Research (WCTR), pp.377-390, 1999. ,
A bound on the exponent of a primitive matrix using Boolean rank, Linear Algebra and its Applications, vol.217, pp.101-116, 1995. ,
DOI : 10.1016/0024-3795(92)00003-5
Cyclic scheduling on parallel processors: an overview, Scheduling Theory and Its Applications, pp.193-225, 1995. ,
Transience Bounds for Long Walks, Mathematics of Operations Research, vol.24, issue.2, pp.414-439, 1999. ,
DOI : 10.1287/moor.24.2.414
Opinion dynamics and bounded confidence models, analysis, and simulation, Journal of Artificial Societies and Social Simulation, vol.5, issue.3, 2002. ,
Truth and cognitive division of labour: First steps towards a computer aided social epistemology, Journal of Artificial Societies and Social Simulation, vol.9, issue.3, 2006. ,
Max Plus at Work, 2006. ,
DOI : 10.1515/9781400865239
Convergence of linear and non-linear versions of Vicsek's model, CESAME Research Report, vol.57, 2005. ,
Coordination of groups of mobile autonomous agents using nearest neighbor rules, IEEE Transactions on Automatic Control, vol.48, issue.6, pp.988-1001, 2003. ,
DOI : 10.1109/TAC.2003.812781
An extension of the Dulmage-Mendelsohn theorem, Linear Algebra and its Applications, vol.27, pp.187-197, 1979. ,
DOI : 10.1016/0024-3795(79)90041-7
Synchronization and Arbitration in Digital Systems, 2007. ,
Bounds for eigenvalues of certain stochastic matrices, Linear Algebra and its Applications, vol.38, pp.5-15, 1981. ,
DOI : 10.1016/0024-3795(81)90003-3
Markov Chains and Mixing Times, 2009. ,
DOI : 10.1090/mbk/058
Distributed Algorithms, 1996. ,
A lower bound on the period length of a distributed scheduler, Algorithmica, vol.29, issue.1, pp.383-398, 1993. ,
DOI : 10.1007/BF01769705
Analysis of distributed algorithms based on recurrence relations, Proceedings of the 5th International Workshop on Distributed Algorithms (WDAG), pp.242-253, 1992. ,
DOI : 10.1007/BFb0022451
The effect of asynchronous inputs on sequential network reliability, IEEE Transactions on Computers, vol.26, issue.11, pp.1082-1090, 1977. ,
General theory of metastable operation, IEEE Transactions on Computers, vol.30, issue.2, pp.107-115, 1981. ,
Analysis of clock distribution networks in the presence of crosstalk and groundbounce, Proceedings of the 8th IEEE International Conference on Electronics, Circuits, and Systems (ICECS), pp.773-776, 2001. ,
Newtonian arbiters cannot be proven correct. Formal Methods in System Design, pp.233-257, 1993. ,
DOI : 10.1007/bf01384075
Conductance and convergence of Markov chains-a combinatorial treatment of expanders, 30th Annual Symposium on Foundations of Computer Science, pp.526-531, 1989. ,
DOI : 10.1109/SFCS.1989.63529
Stability of multiagent systems with time-dependent communication links, IEEE Transactions on Automatic Control, vol.50, issue.2, pp.169-18287, 1997. ,
DOI : 10.1109/TAC.2004.841888
Convergence Speed in Distributed Consensus and Averaging, SIAM Review, vol.53, issue.4, pp.747-772, 2011. ,
DOI : 10.1137/110837462
On context-free languages, Journal of the ACM, vol.13, issue.4, pp.570-581, 1966. ,
Uniform rates of convergence for Markov chain transition probabilities, Zeitschrift f???r Wahrscheinlichkeitstheorie und Verwandte Gebiete, vol.13, issue.3, pp.193-227, 1974. ,
DOI : 10.1007/BF00536280
Flocks, herds and schools: A distributed behavioral model, ACM SIGGRAPH Computer Graphics, vol.21, issue.4, pp.25-34, 1987. ,
DOI : 10.1145/37402.37406
Q-modules: internally clocked delay-insensitive modules, IEEE Transactions on Computers, vol.37, issue.9, pp.1005-1018, 1988. ,
DOI : 10.1109/12.2252
Max-Balancing Weighted Directed Graphs and Matrix Scaling, Mathematics of Operations Research, vol.16, issue.1, pp.208-222, 1991. ,
DOI : 10.1287/moor.16.1.208
The discrepancy of (n?) n ?1, Mathematische Annalen, vol.77, issue.1?2, pp.529-545703, 1970. ,
DOI : 10.1007/BF01445118
On the semigroup of binary relations on a finite set, Czechoslovak Mathematical Journal, vol.20, issue.4, pp.632-679, 1970. ,
Non-negative Matrices and Markov Chains, 1993. ,
DOI : 10.1007/0-387-32792-4
Approximate counting, uniform generation and rapidly mixing Markov chains, Information and Computation, vol.82, issue.1, pp.93-133, 1989. ,
DOI : 10.1016/0890-5401(89)90067-9
On the Behaviour of Classes of Min-Max-Plus Systems, 2003. ,
Flocking in Fixed and Switching Networks, IEEE Transactions on Automatic Control, vol.52, issue.5, pp.863-868, 2007. ,
DOI : 10.1109/TAC.2007.895948
Product of Random Stochastic Matrices, IEEE Transactions on Automatic Control, vol.59, issue.2, 2011. ,
DOI : 10.1109/TAC.2013.2283750
Problems in Decentralized Decision Making and Computation, 1984. ,
Asynchronous sequential switching circuits with unrestricted input changes, IEEE Transaction on Computers, vol.20, issue.12, pp.1437-1444, 1971. ,
Unzerlegbare, nicht negative Matrizen, Mathematische Zeitschrift, vol.192, issue.1, pp.642-645, 1950. ,
DOI : 10.1007/BF02230720
New transience bounds for long walks. Preprint, submitted, arXiv:1209 ,
URL : https://hal.archives-ouvertes.fr/hal-00993814
New transience bounds for long walks in weighted digraphs, Proceedings of the 7th European Conference on Combinatorics, Graph Theory, and Applications (EuroComb), pp.623-624, 2013. ,
DOI : 10.1007/978-88-7642-475-5_103
URL : https://hal.archives-ouvertes.fr/hal-00993814
Transience Bounds for Distributed Algorithms, Proceeding of the 11th International Conference on Formal Modeling and Analysis of Timed Systems (FORMATS), pp.77-90, 2013. ,
DOI : 10.1007/978-3-642-40229-6_6
URL : https://hal.archives-ouvertes.fr/hal-00993785
General transience bounds in tropical linear algebra via Nachtigall decomposition, Proceedings of the Workshop on Tropical and Idempotent Mathematics Institute for Information Transmission Problems of the Russian Academy of Sciences, pp.46-52, 2012. ,
URL : https://hal.archives-ouvertes.fr/hal-00993902
Lecture Notes in Computer Science Brief announcement: The degrading effect of forgetting on a synchronizer, Proceedings of the 9th International Symposium on Algorithms and Experiments for Sensor Systems, Wireless Networks and Distributed Robotics (Algosensors) Proceeding of the 14th International Symposium on Stabilization , Safety, and Security of Distributed Systems (SSS), pp.185-200, 2012. ,
Unfaithful glitch propagation in existing binary circuit models, Proceedings of the 19th IEEE International Symposium on Asynchronous Circuits and Systems (ASYNC), pp.191-199 ,
Generalizations of bounds on the index of convergence to weighted digraphs, Discrete Applied Mathematics, p.2014 ,
URL : https://hal.archives-ouvertes.fr/hal-01107293
Weak CSR expansions and transience bounds in max-plus algebra, Linear Algebra and its Applications, vol.461, pp.163-199, 2014. ,
DOI : 10.1016/j.laa.2014.07.027
URL : https://hal.archives-ouvertes.fr/hal-01058031
An overview of transience bounds in max-plus algebra, Tropical and Idempotent Mathematics and Applications, pp.277-289 ,
DOI : 10.1090/conm/616/12306
URL : https://hal.archives-ouvertes.fr/hal-00993630
On the performance of a retransmission-based synchronizer On the performance of a retransmission-based synchronizer, Proceedings of the 18th International Colloquium on Structural Information and Communication Complexity (SIROCCO), pp.234-24525, 2011. ,
URL : https://hal.archives-ouvertes.fr/hal-00993805