TY - GEN
T1 - Transience bounds for distributed algorithms
AU - Charron-Bost, Bernadette
AU - Függer, Matthias
AU - Nowak, Thomas
PY - 2013/8/28
Y1 - 2013/8/28
N2 - A large variety of distributed systems, like some classical synchronizers, routers, or schedulers, have been shown to have a periodic behavior after an initial transient phase (Malka and Rajsbaum, WDAG 1991). In fact, each of these systems satisfies recurrence relations that turn out to be linear as soon as we consider max-plus or min-plus algebra. In this paper, we give a new proof that such systems are eventually periodic and a new upper bound on the length of the initial transient phase. Interestingly, this is the first asymptotically tight bound that is linear in the system size for various classes of systems. Another significant benefit of our approach lies in the straightforwardness of arguments: The proof is based on an easy convolution lemma borrowed from Nachtigall (Math. Method. Oper. Res. 46) instead of purely graph-theoretic arguments and involved path reductions found in all previous proofs.
AB - A large variety of distributed systems, like some classical synchronizers, routers, or schedulers, have been shown to have a periodic behavior after an initial transient phase (Malka and Rajsbaum, WDAG 1991). In fact, each of these systems satisfies recurrence relations that turn out to be linear as soon as we consider max-plus or min-plus algebra. In this paper, we give a new proof that such systems are eventually periodic and a new upper bound on the length of the initial transient phase. Interestingly, this is the first asymptotically tight bound that is linear in the system size for various classes of systems. Another significant benefit of our approach lies in the straightforwardness of arguments: The proof is based on an easy convolution lemma borrowed from Nachtigall (Math. Method. Oper. Res. 46) instead of purely graph-theoretic arguments and involved path reductions found in all previous proofs.
U2 - 10.1007/978-3-642-40229-6_6
DO - 10.1007/978-3-642-40229-6_6
M3 - Conference contribution
AN - SCOPUS:84882736289
SN - 9783642402289
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 77
EP - 90
BT - Formal Modeling and Analysis of Timed Systems - 11th International Conference, FORMATS 2013, Proceedings
T2 - 11th International Conference on Formal Modeling and Analysis of Timed Systems, FORMATS 2013
Y2 - 29 August 2013 through 31 August 2013
ER -