Dissertation/Thesis Abstract

Partial Solutions for the Firing Squad Synchronization Problem on Rings
by Ng, Weng Leong, Ph.D., University of California, Irvine, 2011, 380; 3477975
Abstract (Summary)

The Firing Squad Synchronization Problem (FSSP) is an old problem in theoretical Computer Science concerned with the synchronization of identical automata on lines of arbitrary length. Recent work by Umeo and Yanagihara explored partial solutions for the FSSP, where the original problem is relaxed to require synchronization only for some infinite proper subset of lengths. Umeo, Kamikawa and Yunès (UKY) investigated ring partial solutions, and found, via exhaustive testing of automata on a small number of lengths, that there are at most 17 4-state, symmetric candidate partial solutions for power-of-2 lengths greater than 1 (powers-of-2 solutions). They similarly tested and surmised the non-existence of 3-state ring partial solutions. This thesis extends UKY's work on rings as follows.

First, we devise a search procedure for partial solutions that backtracks on repeated configurations. We apply it to show that there are at most 97 candidate powers-of-2 solutions, 17 of which are UKY's symmetric ones, and 80 are new asymmetric ones. From this result we infer the non-existence of 4-state ring full solutions.

Second, we prove the powers-of-2 candidate solutions by introducing exponential rulesets, which are rulesets parameterized by exponents. We devise a procedure to generate exponential rulesets from an underlying ruleset. We apply this procedure to the candidate solutions to obtain a small, common set of exponential rulesets, which are then used to prove the candidate solutions.

Third, we devise a backtracking search procedure for firing exponential rulesets, i.e., exponential rulesets that synchronize. We use it to discover numerous firing exponential rulesets, effectively finding ring partial solutions for the FSSP generalized to nullities other than 2.

Last, we use de Bruijn subgraphs of ruleset minimal segments to prove the non-existence of 3-state ring partial solutions. We also provide an alternate computer-aided proof using firing transition graphs. These proofs suggest that graph-theoretic methods can be good starting points for resolving less tractable FSSP impossibility results.

An underlying theme of this thesis is the use of algorithmic techniques in formulating proofs of FSSP results. Our work shows that a judicious mix of analytic and computational methods is an effective way to approach the FSSP.

Indexing (document details)
Advisor: Hayes, Wayne B.
Commitee: Arvo, James R., Enciso, German A.
School: University of California, Irvine
Department: Information and Computer Science - Ph.D.
School Location: United States -- California
Source: DAI-B 73/01, Dissertation Abstracts International
Subjects: Computer science
Keywords: Automata, Firing, Firing squad synchronization, Fssp, Rings, Synchronization problem
Publication Number: 3477975
ISBN: 978-1-124-95113-3
Copyright © 2020 ProQuest LLC. All rights reserved. Terms and Conditions Privacy Policy Cookie Policy