Name
Abstract | ||
|---|---|---|
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. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1007/978-3-642-40229-6_6 | FORMATS |
Keywords | Field | DocType |
initial transient phase,min-plus algebra,classical synchronizers,new proof,easy convolution lemma,graph-theoretic argument,previous proof,large variety,periodic behavior,transience bound,involved path reduction | Discrete mathematics,Upper and lower bounds,Convolution,Recurrence relation,Mathematical proof,Distributed algorithm,Periodic graph (geometry),Mathematics,Lemma (mathematics),Critical graph | Conference |
Citations | PageRank | References |
5 | 0.44 | 15 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Bernadette Charron-bost | 1 | 785 | 67.22 |
| Matthias Függer | 2 | 167 | 21.14 |
| Thomas Nowak | 3 | 5 | 0.44 |