Threshold protocols in survivor set systems. - In: Distributed computing, ISSN 1432-0452, Bd. 23 (2010), 2, S. 135-149
Many replication protocols employ a threshold model when expressing failures they are able to tolerate. In this model, one assumes that no more than t out of n components can fail, which is a good representation when failures are independent and identically distributed (IID). In many real systems, however, failures are not IID, and a straightforward application of threshold protocols yields suboptimal results. Here, we examine the problem of transforming threshold protocols into survivor-set protocols tolerating dependent failures. Our main goal is to show the equivalence between the threshold model and the core/survivor set model. Toward this goal, we develop techniques to transform threshold protocols into survivor set ones. Our techniques do not require authentication, self-verification or encryption. Our results show in one case that we can transform a threshold protocol to a subset by spreading a number of processes across processors. This technique treats a given threshold algorithm as a black box, and consequently can transform any threshold algorithm. However, it has the disadvantage that the transformation is not possible for all sets of survivor sets. The second technique instead focuses on transforming voters: functions that evaluate to a value out of a set of tallied values in a replication protocol. Voters are an essential part of many fault-tolerant protocols, and we show a universal way of transforming them. With such a transformation we expect that a large number of protocols in the literature can be directly transformed with our technique. It is still an open problem, however, if the two models are equivalent, and our results constitute an important first step in this direction.
http://dx.doi.org/10.1007/s00446-010-0107-3
Long cycles and paths in distance graphs. - In: Discrete mathematics, Bd. 310 (2010), 23, S. 3417-3420
For n a natural number and D a set of natural numbers, the distance graph P^D_n has vertex set {0,...,n-1}and edge set { ij | 0 <= i,j <= n-1, |j-i| is in D}. Note that the important and very well-studied circulant graphs coincide with the regular distance graphs. A fundamental result concerning circulant graphs is that for these graphs, a simple greatest common divisor condition, their connectivity, and the existence of a Hamiltonian cycle are all equivalent. Our main result suitably extends this equivalence to distance graphs. We prove that for a finite set D of order at least 2, there is a constant c_D such that the greatest common divisor of the integers in D is 1 if and only if for every n, P^D_n has a component of order at least n-c_D if and only if for every n >= c_D+3, P^D_n has a cycle of order at least n-c_D. Furthermore, we discuss some consequences and variants of this result.
http://dx.doi.org/10.1016/j.disc.2010.07.020
Tight thresholds for cuckoo hashing via XORSAT. - In: Automata, languages and programming, (2010), S. 213-225
http://dx.doi.org/10.1007/978-3-642-14165-2_19
Tight bounds for blind search on the integers and the reals. - In: Combinatorics, probability & computing, ISSN 1469-2163, Bd. 19 (2010), 5/6, S. 711-728
https://doi.org/10.1017/S0963548309990599
Shellsort: Analyse und Bewertung eines einfachen dateninvarianten randomisierten Sortierverfahrens. - 75 S. : Ilmenau, Techn. Univ., Bachelor-Arbeit, 2010
Die Arbeit beschäftigt sich mit dem 2010 in Michael T. Goodrichs Paper "Randomized Shellsort: A Simple Data-Oblivious Sorting Algorithm" vorgestellten randomisierten Shellsort-Algorithmus. Die in dem Paper gelieferten Inhalte und Beweise werden nachvollzogen und überprüft, für eventuell auftretende Unklarheiten werden außerdem alternative Lösungswege aufgezeigt. Als Ziel der Arbeit wird formal nachgewiesen, dass Goodrichs Algorithmus einfach und dateninvariant ist, über eine garantierte Laufzeit von O(n log n) verfügt und jede Eingabe mit sehr hoher Wahrscheinlichkeit sortiert. Die sehr hohe Sortierwahrscheinlichkeit wird außerdem experimentell nachgewiesen.
An alternative analysis of cuckoo hashing with a stash and realistic hash functions. - 98 S. : Ilmenau, Techn. Univ., Diplomarbeit, 2010
Enth. außerdem: Thesen
Diese Arbeit beschäftigt sich mit Cuckoo-Hashing, einem speziellen Hash-Verfahren. Ein Nachteil dieses Verfahrens ist, dass das Einfügen eines Elements mit einer kleinen Wahrscheinlichkeit fehlschlägt. Diese ist für einige Anwendungen groß genug, um Cuckoo-Hashing trotz seiner guten Laufzeiteigenschaften dort nicht praktikabel einsetzen zu können. Eine aktuelle Arbeit von Kirsch et al. schlägt eine Lösung für dieses Problem vor, indem ein kleiner zusätzlicher Speicher, der sogenannte Stash, eingeführt wird. In dieser Diplomarbeit geben wir einen neuen Beweis dafür, dass der Stash in Cuckoo-Hashing zu einer enorm reduzierten Fehlerwahrscheinlichkeit führt. Weiterhin werden wir zeigen, dass dieser keinen wesentlichen Einfluss auf die Laufzeiten der insert-, delete- und lookup-Operationen hat. Wir werden beweisen, dass unsere Analyse für eine Klasse von effizient auswertbaren Hashfunktionen gilt und somit eine offene Frage von Kirsch et al. beantworten. Für diese Klasse wird ein abstraktes Ergebnis vorgestellt, das es ermöglicht die Idee dieser Hashklasse auch in anderen Zusammenhängen zu nutzen. In Experimenten zeigen wir auf, dass schon ein kleiner zusätzlicher Speicher mit nur neun Speicherplätzen für Schlüssel eine enorme Verbesserung für die praktische Einsatzfähigkeit von Cuckoo-Hashing bringt. Wir können damit problemlos in der Nähe der theoretisch maximalen Tabellenauslastung von Cuckoo-Hashing arbeiten, ohne Gefahr zu laufen, dass die Datenstruktur durch eine fehlschlagende Einfügeoperation neu aufgebaut werden muss. Insbesondere im Falle kleiner Tabellen wird sich der Stash als wertvolle Erweiterung erweisen. Weiterhin werden wir auch die zwei populären Varianten d-äres Cuckoo-Hashing und geblocktes Cuckoo-Hashing näher betrachten. Dabei wird sich herausstellen, dass in diesen Varianten ein zusätzlicher Speicher die Fehlerwahrscheinlichkeit bei kleinen Tabellengrößen deutlich senkt. Im Gegensatz zu normalem Cuckoo-Hashing ist ein Stash jedoch im Falle großer Tabellen nutzlos.
Cycles, paths, connectivity and diameter in distance graphs. - In: Graph theoretic concepts in computer science, (2010), S. 320-328
http://dx.doi.org/10.1007/978-3-642-11409-0
Moderne Konstruktionen von Expandergraphen. - 84 S. Ilmenau : Techn. Univ., Bachelor-Arbeit, 2010
Expandergraphen sind in Bezug auf die Kanten dünn besetzte Graphen, die gleichzeitig eine hohe Konnektivität besitzen. Die Feststellung ob man in einem Expander mit einem gewünschten Expansionsgrad expandieren kann ist co-NP-vollständig. Folglich ist das Generieren eines gewünschten Graphen durch Erraten der Adjazenzmatrix sehr ineffizient. Diese Arbeit nutzt Erkenntnisse eines Papers (2008) von Noga Alon, Asaf Shapira und Oded Schwartz. Hierauf basierend werden Konstruktionen von expliziten und voll expliziten Expandern die in der Knotenanzahl polynomiell berechenbar sind vorgestellt. Zur Generierung großer Expander wird das Ersetzungsprodukt (Replacement Product) genutzt. Dieses lässt durch die mehrmalige Einbettung eines Expanders in einen anderen einen großen Expander entstehen, für den dann der Expansionsparameter abgeschätzt wird. Weiterhin sind Beweise zu finden die die Abhängigkeit des Expansionsparameters von dem zweitgrößten Eigenwert darstellen.
Implicit characterizations of FPTIME and NC revisited. - In: The journal of logic and algebraic programming, Bd. 79 (2010), 1, S. 47-60
Various simplified or improved, and partly corrected well-known implicit characterizations of the complexity classes FPTIME and NC are presented. Primarily, the interest is in simplifying the required simulations of various recursion schemes in the corresponding (implicit) framework, and in developing those simulations in a more uniform way, based on a step-by-step comparison technique, thus consolidating groundwork in implicit computational complexity.
http://dx.doi.org/10.1016/j.jlap.2009.02.005
Algorithmen für Datenströme: ein extrem platzeffizienter Algorithmus für das Finden von Duplikaten. - 55 S. Ilmenau : Techn. Univ., Bachelor-Arbeit, 2009
Für einen Datenstrom der Länge n über dem Alphabet [m] mit n>m, betrachtet die Arbeit das Problem des Duplikatfindens mit einem einzigen Durchlauf. Es wird ein randomisiertes Lösungsverfahren für dieses Problem vorgestellt, welches lediglich Platz O((log m)џ) Bits benötigt. Dieser Algorithmus wurde Anfang 2009 von P. Gopalan und J. Radhakrishnan in ihrer Arbeit "Finding Duplicates in a Data Stream" vorgestellt und beantwortet die Frage nach der Existenz eines randomisierten Algorithmus für das Problem FindeDuplikat mit sublinearem Platzverbrauch. Die Arbeit verfeinert und erweitert dabei das zu Grunde liegende Werk.