Abstract:
Im Gebiet des verteilten Rechnens werden Modelle untersucht, in denen sich mehrere Berechnungseinheiten koordinieren, um zusammen ein gemeinsames Ziel zu erreichen, wobei sie aber nur über begrenzte Ressourcen verfügen — sei diese Zeit-, Platz- oder Kommunikationskapazitäten. Das Hauptuntersuchungsobjekt dieser Dissertation ist das wohl einfachste solche Modell überhaupt: (eindimensionale) Zellularautomaten. Unser Ziel ist es, einen besseren Überblick über die Fähigkeiten und Einschränkungen des Modells und ihrer Varianten zu erlangen in dem Fall, dass die gesamte Bearbeitungszeit deutlich kleiner als die Größe der Eingabe ist (d. ... mehrh. Sublinear-Zeit). Wir führen unsere Analyse von dem Standpunkt der Komplexitätstheorie und stellen dabei auch Bezüge zwischen Zellularautomaten und anderen Gebieten wie verteiltes Rechnen und Streaming-Algorithmen her.
Sublinear-Zeit Zellularautomaten. Ein Zellularautomat (ZA) besteht aus identischen Zellen, die entlang einer Linie aneinandergereiht sind. Jede Zelle ist im Wesentlichen eine sehr primitive Berechnungseinheit (nämlich ein deterministischer endlicher Automat), die mit deren beiden Nachbarn interagieren kann. Die Berechnung entsteht durch die Aktualisierung der Zustände der Zellen gemäß derselben Zustandsüberführungsfunktion, die gleichzeitig überall im Automaten angewendet wird. Die von uns betrachteten Varianten sind unter anderem schrumpfende ZAs, die (gewissermaßen) dynamisch rekonfigurierbar sind, sowie eine probabilistische Variante, in der jede Zelle mit Zugriff auf eine faire Münze ausgestattet ist. Trotz überragendem Interesse an Linear- und Real-Zeit-ZAs scheint der Fall von Sublinear-Zeit im Großen und Ganzen von der wissenschaftlichen Gemeinschaft vernachlässigt worden zu sein. Wir arbeiten die überschaubare Anzahl an Vorarbeiten zu dem Thema auf, die vorhanden ist, und entwickeln die daraus stammenden Techniken weiter, sodass deren Spektrum an Anwendungsmöglichkeiten wesentlich breiter wird. Durch diese Bemühungen entsteht unter anderem ein Zeithierarchiesatz für das deterministische Modell. Außerdem übertragen wir Techniken zum Beweis unterer Schranken aus der Komplexitätstheorie auf das Modell der schrumpfenden ZAs und entwickeln neue Techniken, die auf probabilistische Sublinear-Zeit-ZAs zugeschnitten sind.
Ein Bezug zu Härte-Magnifizierung. Ein Bezug zu Komplexitätstheorie, die wir im Laufe unserer Untersuchungen herstellen, ist ein Satz über Härte-Magnifizierung (engl. hardness magnification) für schrumpfende ZAs. Hier bezieht sich Härte-Magnifizierung auf eine Reihe neuerer Arbeiten, die bezeugen, dass selbst geringfügig nicht-triviale untere Schranken sehr beeindruckende Konsequenzen in der Komplexitätstheorie haben können. Unser Satz ist eine Abwandlung eines neuen Ergebnisses von McKay, Murray und Williams (STOC, 2019) für Streaming-Algorithmen. Wie wir zeigen kann die Aussage dabei genauso in Bezug auf schrumpfende ZAs formuliert werden, was sie auch beweisbar verstärkt.
Eine Verbindung zu Sliding-Window Algorithmen. Wir verknüpfen das verteilte Zellularautomatenmodell mit dem sequenziellen Streaming-Algorithmen-Modell. Wie wir zeigen, können (gewisse Varianten von) ZAs von Streaming-Algorithmen simuliert werden, die bestimmten Lokalitätseinschränkungen unterliegen. Konkret ist der aktuelle Zustand des Algorithmus vollkommen bestimmt durch den Inhalt eines Fensters fester Größe, das wenige letzte Symbole enthält, die vom Algorithmus verarbeitet worden sind. Dementsprechend nennen wir diese eingeschränkte Form eines Streaming-Algorithmus einen Sliding-Window-Algorithmus. Wir zeigen, dass Sliding-Window-Algorithmen ZAs sehr effizient simulieren können und insbesondere in einer solchen Art und Weise, dass deren Platzkomplexität eng mit der Zeitkomplexität des simulierten ZA verbunden ist.
Derandomisierungsergebnisse. Wir zeigen Derandomisierungsergebnisse für das Modell von Sliding-Window-Algorithmen, die Zufall aus einer binären Zufallsquelle beziehen. Dazu stützen wir uns auf die robuste Maschinerie von Branching-Programmen, die den gängigen Ansatz zur Derandomisierung von Platz-beschränkten Maschinen in der Komplexitätstheorie darstellen. Als eine Anwendung stellen sich Derandomisierungsergebnisse für probabilistische Sublinear-Zeit-ZAs heraus, die durch die oben genannten Verknüpfung erlangt werden.
Vorhersageproblem für Pilz-Sandhaufen. Ein letztes Problem, das wir behandeln und das auch einen Bezug zu Sublinear-Zeitkomplexität im Rahmen von Zellularautomaten hat (obwohl nicht zu Sublinear-Zeit-Zellularautomaten selber), ist das Vorhersageproblem für Sandhaufen-Zellularautomaten. Diese Automaten sind basierend auf zweidimensionalen ZAs definiert und modellieren einen deterministischen Prozess, in dem sich Partikel (in der Regel denkt man an Sandkörnern) durch den Raum verbreiten. Das Vorhersageproblem fragt ob, gegeben eine Zellennummer $y$ und eine initiale Konfiguration für den Sandhaufen, die Zelle mit Nummer $y$ irgendwann vor einer gewissen Zeitschranke einen von Null verschiedenen Zustand erreichen wird. Die Komplexität dieses mindestens zwei Jahrzehnte alten Vorhersageproblems ist für zweidimensionelle Sandhaufen bemerkenswerterweise nach wie vor offen. Wir lösen diese Frage im Wesentlichen für eine neue Variante von Sandhaufen namens Pilz-Sandhaufen, die von Goles u. a. (Phys. Lett. A, 2020) vorgeschlagen worden ist. Unser Ergebnis ist besonders relevant, weil es innovative Erkenntnisse und neue Techniken liefert, die für die Lösung des offenen Problems im allgemeinen Fall von hoher Relevanz sein könnten.
Abstract (englisch):
Distributed computing studies models in which multiple computational units coordinate themselves to work towards some common goal while having only limited resources at their disposal—be it time, space, or communication. The main object of study of this dissertation is the arguably simplest such model there is: (one-dimensional) cellular automata. Our goal is to obtain a better picture of the capabilities and limitations of the model and its variants in the case where the overall processing time is significantly smaller than the size of the input (i.e., sublinear time). ... mehrWe carry out our analysis from the perspective of computational complexity theory and also establish connections between cellular automata and other fields such as distributed computing and streaming algorithms.
Sublinear-time cellular automata. A cellular automaton (CA) is composed of identical cells arranged on a line. Each cell is essentially a very primitive computational unit (namely a deterministic finite automaton) that may interact with its two neighbors. Computation occurs by the cells updating their state according to the same local transition function all across the automaton. The variants we consider include shrinking CAs, which are CAs that are dynamically reconfigurable (to some extent) by means of cell deletion, and also a probabilistic variant in which each cell is equipped with access to a fair coin. Despite remarkable interest on CAs in the linear- and real-time cases, the setting of sublinear time appears to have been neglected by the community at large. We review the little previous work on the topic there is and further develop some techniques originating from it so as to widen the scope of applications. This effort yields, among others, a time hierarchy theorem for the deterministic model. We also transfer lower bound techniques from complexity theory over to the shrinking CA model as well as develop new ones to analyze the capabilities of probabilistic sublinear-time CAs.
A connection to hardness magnification. One connection to complexity theory we establish along the way is a hardness magnification theorem for shrinking CAs. Here hardness magnification refers to a recent line of work that shows how even slightly nontrivial lower bounds might have very surprising consequences for complexity theory. Ours is a recasting of a recent result of McKay, Murray, and Williams (STOC, 2019) for streaming algorithms. As we also show, the result may be equally stated in terms of shrinking CAs, which provably strengthens it.
A connection to sliding-window algorithms. We relate the distributed model of cellular automata to the sequential model of streaming algorithms. As we show, (certain variants of) CAs can be simulated by streaming algorithms that are subject to certain locality restrictions. Concretely, the current state of the algorithm is exclusively dependent on a (fixed-size) window that contains the last few symbols that have been processed. We dub this restricted form of streaming algorithm a sliding-window algorithm, accordingly. We prove that sliding-window algorithms can simulate CAs quite efficiently and, in particular, in such a way that their space complexity is tightly connected to the time complexity of the simulated CA.
Derandomization results. We prove derandomization results for the model of sliding-window algorithms that draw randomness from a binary source. To do so, we rely on the robust machinery of branching programs that forms the standard approach for derandomization of space-bounded computation in complexity theory. As an application, using the aforementioned connection to cellular automata, we derive derandomization results for sublinear-time probabilistic CAs.
Predicting fungal sandpiles. A final problem we tackle and that relates to sublinear-time complexity in relation to cellular automata (albeit not sublinear-time cellular automata per se) is the prediction problem in sandpile automata. These automata are defined based on two-dimensional CAs and model a deterministic process in which particles (usually thought of as grains of sand) spread across space. The prediction problem asks whether, given the number $y$ of a cell and some initial configuration for the sandpile, the cell with the number $y$ will eventually assume a non-zero state in a set amount of time.The complexity of the prediction problem (for two-dimensional sandpiles) has been remarkably open for at least two decades. We effectively settle the question for a variant of sandpiles called fungal sandpiles recently proposed by Goles et al. (Phys. Lett. A, 2020). Our result is of particular relevance since it provides fresh insights and new techniques that could be highly relevant towards obtaining a solution for the open problem in the general case.
