Search

Es gibt tausende von Blockchain und Distributed Ledger Technologie Projekten heutzutage, dennoch hat eine Vielzahl an Menschen nur davon gehört, dass das Bitcoin Netzwerk sehr viel Energie benötigt aufgrund des darin genutzten Konsensalgorithmus. Diese Arbeit untersucht eine Auswahl von alternativen Konsensmechanismen, die in Distributed Ledger Technologie (DLT) genutzt werden und evaluiert, ob diese passend für den Einsatz in bestimmten Netzwerken (öffentlich versus privat, große Anzahl an Teilnehmern, etc.) sind und im Speziellen ob sie geeignet sind für die Verwendung in Internet of Things (IoT) Netzwerken. Zum besseren Verständnis von Konsensalgorithmen im Allgemeinen enthält diese Arbeit einen Abschnitt über historische Konsensprotokolle auf welchen viele der Entwicklungen aus jüngerer Vergangenheit aufbauen. Weiters wird ein kurzer Blick auf die spieltheoretischen Konzepte hinter Konsens geworfen um noch mehr Einsicht zu erlangen wenn gewünscht. Die dieser Arbeit zugrundeliegende Information wurde den Whitepapers der Protokolle, Protokoll-Entwürfen sowie wissenschaftlichen Artikeln, die ebenfalls Vergleiche zwischen Konsensprotokollen anstellen, entnommen. Sicherheitsrelevante Themen wie Fehlertoleranz und Risken werden ebenfalls nicht vergessen in der Evaluation, spielen sie doch eine bedeutende Entscheidung bei der Auswahl. Die Motivation dahinter ist es eine passende Konsenslösung für jedes Projekt zu bieten, das Dezentralisation, Sicherheit und Skalierbarkeit benötigt, besonders im Bereich IoT, und auch um als ein umfangreicher allgemeiner Überblick der unterschiedlichen verfügbaren Konsensarten zu dienen, der sich im Gegensatz zu anderen Publikationen nicht nur auf eine kleine Auswahl von Protokollen beschränkt. There are thousands of blockchain and distributed ledger projects and networks in existence today, yet a majority of people has only heard about the amount of energy that the Bit- coin network uses because of its consensus algorithm. This thesis investigates a variety of alternative consensus mechanisms that are used in distributed ledger technology (DLT) and evaluates if they are a good fit for certain types of networks (public versus private, large scale, etc.) and especially if they are appropriate for use in Internet of Things (IoT) networks. For a better understanding of consensus algorithms in general this thesis includes a section on historic consensus protocols that a lot of the more recent developments are based on. Additionally a quick look at the game theoretical concepts behind consensus is taken to get even more insight if so desired. Protocol whitepapers, protocol proposals and articles that compare consensus protocols serve as the basis for this theoretical work. The topic of security, particularly fault tolerance and risks, is an important factor when deciding on a consensus solution, this is of course considered as well. The motivation is to provide a fitting consensus solution to any project that requires decentralisation, security and large scale, particularly in the IoT sector, and also to serve as an extensive general overview of consensus types currently available, unlike other publications that concentrate on just a small selection of protocols.

Recently, due to the technical progress and development more and more data with thousands and thousands of features is collected in increasingly less time [Stańczyk/Jain, 2017], [H. Liu/Motoda, 2012]. In order to make use of this unmanageable flood of data, computer-aided evaluation methods are needed to support scientists in extracting useful information or knowledge [Fayyad et al., 1996]. One approach to this are methods of "feature selection". In the present work, such an algorithm is developed exemplarily for sets of genes found on the basis of current knowledge about the genetic architecture of features or diseases. It is not required to have numerical measurements from experiments for the individual genes, since an integrative approach is pursued, which uses the Gene Ontology Knowledge Base [Ashburner et al., 2000] as a basis for the criterion for the selection of the most important genes. The function-preserving, integrative gene selection presented here reduces a set of genes to their most important elements by calculating a score for each gene that describes the importance of the genes. This score is determined using the annotations of the genes to the significant biological processes in the polyhierarchically organized Gene Ontology knowledge base. The resulting directed acyclic graph (DAG) of significant biological processes describes the gene functions of the set of genes. With the gene score, genes can be ranked according to their importance. The first k∗ genes form an optimal subset, whereby the subset of genes is selected that has the best function-preserving property. The preservation of function is evaluated by precision and recall and their combination to the F1-measure, respectively, regarding the reproduction of the entire DAG with the selected subset. With the function-preserving, integrative gene selection, the original DAG could be reproduced with recall and precision of about 70% for each of the examined data sets, using only about 5% of the original genes. The most important results of this thesis were already successfully, peer-reviewed published: [Lippmann et al., 2019]., Durch den technischen Fortschritt der letzten Jahre werden in immer kürzerer Zeit immer größere Mengen von Daten mit tausenden und abertausenden Merkmalen gesammelt [Stańczyk/Jain, 2017], [H. Liu/Motoda, 2012]. Um diese unüberschaubar große Datenflut nutzbringend einzusetzen, werden computergestützte Auswertungsmethoden benötigt, die die Wissenschaftler bei der Extraktion von nützlichen Informationen bzw. Wissen unterstützen [Fayyad et al., 1996]. Ein Ansatz dazu sind Methoden der „Feature Selection“. In der vorliegenden Arbeit wird ein solcher Algorithmus beispielhaft für Gensätze entwickelt, die anhand von aktuellem Wissen über die genetische Architektur von Merkmalen oder Krankheiten gefunden wurden. Es ist dabei nicht notwendig, numerische Messwerte aus Experimenten für die einzelnen Gene zu kennen, da ein integrativer Ansatz verfolgt wird, der die Gene Ontology Wissensbasis [Ashburner et al., 2000] als Grundlage für das Kriterium zur Auswahl der wichtigsten Gene verwendet. Die hier vorgestellte funktionserhaltende, integrative Genselektion reduziert eine Menge von Genen auf ihre wichtigsten Elemente, indem für jedes Gen ein Score berechnet wird, der die Wichtigkeit der Gene beschreibt. Dieser Score wird mithilfe der Annotationen der Gene zu den signifikanten, biologischen Prozessen in der polyhierarchisch organisierten Gene Ontology Wissensbasis ermittelt. Der sich ergebende gerichtete, azyklische Graph (DAG) von signifikanten, biologischen Prozessen beschreibt die Genfunktionen des Datensatzes von Genen. Mit dem Gen-Score können die Gene in eine Rangfolge entsprechend ihrer Wichtigkeit gebracht werden. Die ersten k∗ Gene bilden eine optimale Teilmenge, wobei diejenige Teilmenge der Gene ausgewählt wird, die die beste funktionserhaltende Eigenschaft hat. Die Funktionserhaltung wird dabei über Precision und Recall bzw. deren Verrechnung zum F1-Maß bezüglich der Reproduktion des gesamten DAGs mit der gewählten Teilmenge bewertet. Mit der funktionserhaltenden, integrativen Genselektion konnte für die untersuchten Gensätze der ursprüngliche DAG jeweils mit Recall und Precision von etwa 70% reproduziert werden, wobei nur etwa 5% der ursprünglichen Gene verwendet wurden. Die wichtigsten Ergebnisse dieser Dissertation konnten bereits erfolgreich peer-reviewed publiziert werden: [Lippmann et al., 2019].

A number of erroneous attempts involving PQ-trees in the context of automatic graph drawing algorithms have been presented in the literature in recent years. In order to prevent future research from constructing algorithms with similar errors we point out some of the major mistakes. In particular, we examine erroneous usage of the PQ-tree data structure in algorithms for computing maximal planar subgraphs and an algorithm for testing leveled planarity of leveled directed acyclic graphs with several sources and sinks.