Synchronization of a line of finite automata with nonuniform delays

Abstract : We study the Firing Squad Synchronization Problem with non uniform delays in the case of a line of cells. The problem was solved in the general case by T.~Jiang in time Delta^3. In the case of the line, we improve his result, obtaining the Delta^2. We observe that there does not exist an optimal solution. We also note that the strategy, used here, is the general strategy (Waksman's one) and thus, even in this case, we can break the line in its middle.
Document type :
Reports
Complete list of metadatas

Cited literature [10 references]  Display  Hide  Download

https://hal-lara.archives-ouvertes.fr/hal-02101770
Contributor : Colette Orange <>
Submitted on : Wednesday, April 17, 2019 - 9:05:49 AM
Last modification on : Thursday, November 21, 2019 - 2:38:39 AM

File

RR1994-49.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02101770, version 1

Collections

Citation

Jacques Mazoyer. Synchronization of a line of finite automata with nonuniform delays. [Research Report] LIP RR-1994-49, Laboratoire de l'informatique du parallélisme. 1995, 2+24p. ⟨hal-02101770⟩

Share

Metrics

Record views

10

Files downloads

7