CS Paper Radar

Two barriers for minimal time firing squads, with applications to four and five states

Kia Keng Giam

cs.FL nlin.CG ·submitted 2026-11-08 02:41 UTC · v1
publishedtheory

Abstract

A minimal-time solution of the firing squad synchronization problem synchronizes every line of n cells at time 2n minus 2. Six states suffice; whether five do has been open since 1987. Every line agrees with the half line until its right ends echo returns. For minimal time solutions with any number of states, we prove that cells at distance j behind the half lines front become time-periodic only after time (1.5 minus epsilon)j, for every epsilon greater than 0 and infinitely many j, and that the half line is never periodic in time and space on a wedge at its left border, hence not eventually regular in our sense. With certified satisfiability checks, we exclude four states using the lines of lengths 2 to 5 and parts of the next five, and show that every five state minimal time solution uses at least 15 non quiescent neighbourhoods on its half lines first 78 anti-diagonals. We give five state rules synchronizing exactly the lengths 2 to 14.

Comment
34 pages, 18 figures, accepted (awaiting print) at the Journal of Cellular Automata

Closest papers

Nearest neighbours by meaning across the whole index.

Self-stabilising approximate clock synchronisation requires linear time

cs.DC ·2026-11-03 ·Joel Rybicki
theory similarity 0.60
Abstract

Synchronising the clocks of processes is a fundamental problem in distributed computing. We consider message-passing systems in which processes start in an arbitrary initial state (self-stabilisation) and up to $f$ processes may be non-transiently faulty. It is well known that synchronising clocks \emph{exactly} is at least as hard as consensus and requires $Θ(f)$ time. In contrast, without self-stabilisation, clocks can be synchronised \emph{approximately} much faster, in time independent of the number of non-transient faults [Srikanth and Toueg, JACM 1987; Welch and Lynch, Inf. Comput. 1988]. In this work, we show that deterministic self-stabilising approximate clock synchronisation tasks require $Ω(f)$ time to stabilise. This gives the first non-trivial time lower bound for these tasks, whose time complexity has remained open for over two decades [Dolev and Welch, JACM 2004; Dolev, Függer, Schmid and Lenzen, JACM 2014]. In particular, this answers the open question whether self-stabilising approximate clock synchronisation tasks are as hard as consensus or as easy as approximate agreement [Lenzen and Rybicki, JACM 2019]. The results show that guaranteeing \emph{both} transient and non-transient fault-tolerance simultaneously is expensive even for approximate synchronisation tasks. The lower bounds hold in a very strong model: the faulty processes can only crash, the local clocks of processes have no clock drift, and the message delay is bounded and known to all processes. The proof is based on a combinatorial topological argument showing that no fast finite-state protocol can ensure that the clocks behave consistently across all executions. To our knowledge, this is the first use of topological arguments to prove time lower bounds in the self-stabilising setting.

0.14

The triple rendezvous time of a synchronizing automaton can be floor(4n/3)

cs.FL ·2026-09-14 ·Enkai Zhang
theorycode/data similarity 0.55
Abstract · 42 pages, including additional results and computational notes. Computational data are available at https://doi.org/10.5281/zenodo.22561629

For every $n\ge9$, we construct a strongly connected synchronizing automaton with two input letters and $n$ states whose shortest word merging some three distinct states has length $\lfloor4n/3\rfloor$. One letter is a permutation; the other has an image of size $n-1$. We give complete transition maps and an explicit word attaining the bound. For the lower bound, we assign an integer to each unordered pair of states and prove that applying either input letter can decrease it by at most one. For $n\not\equiv0\pmod3$, the same construction contains a specified state whose shortest merging word, with its partner chosen freely, has length $\lfloor4n/3\rfloor-1$.

0.35

Synchronizing Automata: Open Problems

cs.FL ·2026-08-25 ·Marek Szykuła
publishedsurveyhot directionhighly cited similarity 0.54
Abstract · In Proceedings AFL 2026, arXiv:2608.23071

We survey selected open problems in the theory of synchronizing automata, centered around the famous Černý conjecture. A deterministic finite automaton is called synchronizing if it admits a reset word whose action maps all states to a single state. The Černý conjecture states that every synchronizing automaton with n states possesses a reset word of length at most (n-1)^2. We discuss avoiding words, compressing a state with another, synchronization of a (given or any) subset, complexity of deciding the synchronizability, average reset threshold, and linear-algebraic methods. Some new auxiliary results are also presented.

0.72

The Two-Dimensional Majority Rule is P-Complete

cs.DM ·2026-10-03 ·Pedro Montealegre, Martín Ríos-Wilson
theory similarity 0.52
Abstract

We prove that prediction for the synchronous two-dimensional majority rule is $\mathrm{P}$-complete under logspace many-one reductions, resolving a problem open for almost three decades. In 1997, Moore established $\mathrm{P}$-completeness in dimension three and higher and conjectured that the two-dimensional case admits an efficient parallel algorithm. We consider an $n\times n$ torus on which each cell follows the majority of its four nearest neighbors and retains its current state in a tie. Given an explicitly specified initial configuration and a time $T$, prediction asks whether a designated cell is in state $+1$ at time $T$. The central challenge is to make independent information streams cross in the plane under a homogeneous, monotone, diffusive local rule. We overcome this obstacle through a temporal encoding of Boolean values: both values generate activity, but are distinguished by signal arrival times. This encoding yields a crossover that preserves both values and composes with wires, duplication, and AND and OR gates to simulate arbitrary monotone Boolean circuits. Thus a local rule that favors agreement can nevertheless transport, combine, and cross independent information in two dimensions. We also prove $\mathrm{P}$-completeness for deciding whether a designated cell ever reaches $+1$, without a prescribed time horizon. The prediction result extends to every uniform symmetric signed majority rule on the same neighborhood, including the minority rule.

0.27

Random Clocks on Computation Paths]{Random Clocks on Computation Paths: How Far Can They Reach, and When Does Stepping Back Help?

cs.CC math.PR ·2026-10-19 ·Farzad Didehvar, Saman Farhat
similarity 0.52
Abstract

We watch a computation only at moments chosen by a random clock that can leap ahead, pause, or step back, and we count looks rather than steps. How far can such a clock reliably see with polynomially many looks, and does stepping back help? Rare long leaps reach exponential and doubly exponential time, with infinitely many levels between polynomial and exponential time. A clock that tends to fall back sees only the start of the input, and below polynomial time we find infinitely many incomparable levels. Stepping back can help decisively. For clocks whose long leaps occur only at rare positions, no forward-only clock goes beyond polynomial time, while even single steps back raise the reach to exponential time. Stepping back cannot help, however, when the clock's leaps ignore its position.

0.50

The Rhythm of the Tiles: Narrow and Low Temperature Computation and Simulation in Synchronous Tile Self-Assembly

cs.CG ·2026-10-12 ·Florent Becker, Phillip Drake, Benjamin Durbin, Nicolas Ollinger, Brent Orlina +1 more
publishedtheoryunusual similarity 0.52
Abstract · 112 pages, 52 figures, Submission to the 2027 ACM-SIAM Symposium on Discrete Algorithms (SODA27)

In this paper, we prove that the synchronicity provided by the syncTAM can be leveraged to perform two additional feats impossible in the asynchronous aTAM. The aTAM has long been known to be equivalent to finite automata in the one-dimensional case. For our first set of results, we prove that this still holds when a finite, fixed amount of space is available in the second dimension. Yet, surprisingly, in the synchronous setting, a small, fixed, width is enough to simulate a Turing Machine. This holds even in the non-cooperative setting. For our second set of main results we prove that there exists a single set of syncTAM tiles that can be used to simulate any syncTAM system simply by using those tiles to create a scaled version of the seed structure of the original system and then letting the tiles from that set self-assemble from the scaled seed structure. While it has been shown (FOCS 2012) that such a tile set also exists in the aTAM for simulating all aTAM systems, that "intrinsically universal" (IU) tile set requires cooperativity (and is impossible without cooperativity as shown in SODA 2014). We prove there exists an IU tile set in the syncTAM that works without cooperativity. Furthermore, there exists a tile set that is IU for the class of directed systems (i.e. systems which each have a single terminal assembly) while remaining directed during simulation. This was shown to be impossible in the aTAM (FOCS 2016).

0.40

Execution-Time Opacity in (Controllable) Timed Automata is Hard

cs.CC cs.FL ·2026-10-11 ·Sarah Dépernet, Engel Lefaucheux
publishedtheory similarity 0.52
Abstract · In Proceedings GandALF 2026, arXiv:2610.08898

Timing information leakage occurs whenever an attacker successfully deduces confidential internal information by observing some timed information such as the total duration of a run. Timed automata (TAs) are an extension of finite-state automata with a set of clocks evolving at the same rate and that can be tested or reset. Hence, this formalism is able to represent systems involving timing constraints reacting to the passage of time. Some of the transitions in a timed automaton may be controlled, i.e., enabled or disabled, to limit the runs that are allowed. Execution-time opacity (ET-opacity) aims at studying timing information leakage through the analysis of timed automata. More precisely, the ET-opacity problem consists in deciding whether an attacker can deduce whether some secret locations were visited by a run, solely from the run's duration. When control is allowed, the goal becomes to find a strategy that blocks the runs leaking information. This problem has been shown decidable for TAs, with and without control. However, these existing results only provide upper bounds on the complexity of the ET-opacity problem, sometimes largely above the tight bound. Our main contribution is to provide tight lower bounds for those two results. Moreover, for controllable TAs, two variants of ET-opacity (depending on whether detecting if a run did not visit a secret location represents an information leakage or not, and named full and weak ET-opacity respectively) had been separately studied; we prove here that these two notions are inter-reducible.

0.25

Reachability, Not Observation: Containing Systems Whose Wiring Changes

cs.CR cs.NI ·2026-09-17 ·Yoshiaki Takashita
unusual similarity 0.50
Abstract · 29 pages, 3 figures, 17 tables. Companion to arXiv:2609.18145. Code and records for every number are included with the submission

Containment decisions -- where to put a firewall, which links to monitor, what a program may reach -- are computed from an observed structure, and observation is a snapshot. We ask what a snapshot misses when the wiring changes over time. On a hypercube whose active dimension rotates, a balanced split shows zero crossing edges at 93% of instants, yet 8,192 edges must be blocked permanently; adding one always-on ring, a defender sees 2 where 8,194 must be blocked, a factor of 4,097. A time-aware defender holds 585 blocks on average, but one step of clock lag drops its containment to 0%. On the real Internet the same gap is only x1.8-2.0 (1997-2000) and x1.5-1.6 (2024-2026) once growth is removed, so the blind spot is introduced by design, not inherited from the world -- and it has been designed: the round-robin schedules of optical datacentre fabrics have a gap equal to their period. A declared capability map, checked by static reachability over a real application's call graph, catches all 8 planted holes; the string deny-list previously in place catches 2. One calculation generates every number from one parameter, the period, and reads three boundaries not usually called schedules: frequency hopping, whose standard results are these closed forms with channels in place of edges; the air gap, whose always-on crossing set is empty and whose known breach came at the one phase a snapshot misses; and the tool surface of a coding agent, inventoried from the inside. Turning the cuts on that agent: idle, its instantaneous state cut is zero, while 6 channels carry it across a context reset, none of them the network, so severing the network removes 0. The channel that spawns copies is a branching process with a sharp threshold at approval rate 1/b, below which denial is unnecessary and above which denial is insufficient. Contain by the paths that exist, not by the behaviour that was seen.

0.33