Univ., Diss., 2009--Marburg.

Köln, Universiẗat, Diss., 2003.

Ulm, Univ., Diss., 2008.

Diese multizentrische, randomisierte, doppel-blinde Studie hatte zum Ziel, die additive Wirksamkeit von Pentaglobin® bei der Behandlung der Peritonitis zu untersuchen. Pentaglobin® wurde hierbei zusammen mit einer im klinischen Alltag üblichen Antibiotikatherapie intravenös verabreicht. Die Kontrollgruppe erhielt ein Placebo bestehend aus Humanalbumin. Primäre Endpunkte waren der postoperative kumulierte Summenwert der SIRS-Kriterien nach Bone bis zum 23. postoperativen Tag sowie der postoperative kumulierte Summenwert des SOFA-Score bis zum 28. postoperativen Tag. Ergebnisse wurden durch Anwendung verschiedener Scores überprüft. Insgesamt konnten 260 Patienten mit Peritonitis an 16 Studienzentren eingeschlossen werden. 258 Patienten kamen in die Safety-Analyse sowie 255 in die Intentio-To-Treat Analyse. Bei den primären Endpunkten konnte eine Tendenz für die Wirksamkeit von Pentaglobin® bei septischen Patienten gezeigt werden. Insbesondere die Patienten mit einem höheren MPI-Wert scheinen mehr von einer Therapie mit Pentaglobin® profitiert zu haben. Eine statistische Signifikanz konnte jedoch nicht nachgewiesen werden. Bei den sekundären Endpunkten zeigte sich eine statistisch signifikant kürzere Therapie mit Katecholaminen in der Pentaglobin®-Gruppe. Weiterhin fanden sich statistisch signifikante Unterschiede des IL-2-Rezeptors sowie des TNF-1-Rezeptors im Studienverlauf zwischen der Pentaglobin®- und der Placebo-Gruppe. Bei der Überprüfung der Verträglichkeit der Studienmedikation fanden sich keine signifikanten Unterschiede. / The aim of the present clinical trial was to show a therapeutic effect of Pentaglobin® under concomitant administration of antibiotics in patients with beginning peritoneal infections. The study was conducted as a placebo-controlled, double-blind, multicentre and prospective trial of clinical phase IV. The patients were allocated to the two treatment groups (Pentaglobin®/placebo) by randomisation. The primary efficacy parameters were the post-operative cumulative sum score of the SIRS criteria according to Bone until Day 23 and the post-operative cumulative Sequential Organ Failure Assessment (SOFA) sum score until Day 28. In total 260 patients with beginning intraabdominell infection in 16 study centres were included in the study. 258 patients were included in the safety analyses and 255 in the Intention-to-treat analyses. In conclusion, the efficacy results in this study showed a tendency in favour of Pentaglobin® compared to placebo regarding the primary efficacy parameters cumulative SIRS score and cumulative SOFA score that were lower in the Pentaglobin® group than in the placebo group, especially in patients with a more severe peritonitis. The differences between Pentaglobin® and placebo in SIRS and SOFA score were not statistically significant, but patients in the Pentaglobin® group had a lower mean TISS-28 score, a shorter duration of fever, a shorter duration of ICU treatment and artificial ventilation and the duration of treatment with catecholamines was significantly shorter in the Pentaglobin® group. Regarding laboratory parameters, the inflammatory parameters decreased more in the Pentaglobin® group than in the placebo group (with significant differences in favour of Pentaglobin® for IL-2R and TNF-R1) while the significant differences in favour of Pentaglobin® for IgM, IgA, IgG were mainly caused by the administration of the intravenous immunoglobulin preparation (with significant differences in favour of Pentaglobin® for IgM, IgA, IgG). The safety data showed that Pentaglobin® and placebo were equally safe and well tolerated.

Complex networks have been successfully employed to represent different levels of biological systems, ranging from gene regulation to protein-protein interactions and metabolism. Network-based research has mainly focused on identifying unifying structural properties, including small average path length, large clustering coefficient, heavy-tail degree distribution, and hierarchical organization, viewed as requirements for efficient and robust system architectures. Existing studies estimate the significance of network properties using a generic randomization scheme - a Markov-chain switching algorithm - which generates unrealistic reactions in metabolic networks, as it does not account for the physical principles underlying metabolism. Therefore, it is unclear whether the properties identified with this generic approach are related to the functions of metabolic networks. Within this doctoral thesis, I have developed an algorithm for mass-balanced randomization of metabolic networks, which runs in polynomial time and samples networks almost uniformly at random. The properties of biological systems result from two fundamental origins: ubiquitous physical principles and a complex history of evolutionary pressure. The latter determines the cellular functions and abilities required for an organism’s survival. Consequently, the functionally important properties of biological systems result from evolutionary pressure. By employing randomization under physical constraints, the salient structural properties, i.e., the smallworld property, degree distributions, and biosynthetic capabilities of six metabolic networks from all kingdoms of life are shown to be independent of physical constraints, and thus likely to be related to evolution and functional organization of metabolism. This stands in stark contrast to the results obtained from the commonly applied switching algorithm. In addition, a novel network property is devised to quantify the importance of reactions by simulating the impact of their knockout. The relevance of the identified reactions is verified by the findings of existing experimental studies demonstrating the severity of the respective knockouts. The results suggest that the novel property may be used to determine the reactions important for viability of organisms. Next, the algorithm is employed to analyze the dependence between mass balance and thermodynamic properties of Escherichia coli metabolism. The thermodynamic landscape in the vicinity of the metabolic network reveals two regimes of randomized networks: those with thermodynamically favorable reactions, similar to the original network, and those with less favorable reactions. The results suggest that there is an intrinsic dependency between thermodynamic favorability and evolutionary optimization. The method is further extended to optimizing metabolic pathways by introducing novel chemically feasibly reactions. The results suggest that, in three organisms of biotechnological importance, introduction of the identified reactions may allow for optimizing their growth. The approach is general and allows identifying chemical reactions which modulate the performance with respect to any given objective function, such as the production of valuable compounds or the targeted suppression of pathway activity. These theoretical developments can find applications in metabolic engineering or disease treatment. The developed randomization method proposes a novel approach to measuring the significance of biological network properties, and establishes a connection between large-scale approaches and biological function. The results may provide important insights into the functional principles of metabolic networks, and open up new possibilities for their engineering. / In der Systembiologie und Bioinformatik wurden in den letzten Jahren immer komplexere Netzwerke zur Beschreibung verschiedener biologischer Prozesse, wie Genregulation, Protein-Interaktionen und Stoffwechsel (Metabolismus) rekonstruiert. Ein Hauptziel der Forschung besteht darin, die strukturellen Eigenschaften von Netzwerken für Vorhersagen über deren Funktion nutzbar zu machen, also eine Verbindung zwischen Netzwerkeigenschaften und Funktion herzustellen. Die netzwerkbasierte Forschung zielte bisher vor allem darauf ab, gemeinsame Eigenschaften von Netzwerken unterschiedlichen Ursprungs zu entdecken. Dazu zählen die durchschnittliche Länge von Verbindungen im Netzwerk, die Häufigkeit redundanter Verbindungen, oder die hierarchische Organisation der Netzwerke, welche als Voraussetzungen für effiziente Kommunikationswege und Robustheit angesehen werden. Dabei muss zunächst bestimmt werden, welche Eigenschaften für die Funktion eines Netzwerks von besonderer Bedeutung (Signifikanz) sind. Die bisherigen Studien verwenden dafür eine Methode zur Erzeugung von Zufallsnetzwerken, welche bei der Anwendung auf Stoffwechselnetzwerke unrealistische chemische Reaktionen erzeugt, da sie physikalische Prinzipien missachtet. Es ist daher fraglich, ob die Eigenschaften von Stoffwechselnetzwerken, welche mit dieser generischen Methode identifiziert werden, von Bedeutung für dessen biologische Funktion sind, und somit für aussagekräftige Vorhersagen in der Biologie verwendet werden können. In meiner Dissertation habe ich eine Methode zur Erzeugung von Zufallsnetzwerken entwickelt, welche physikalische Grundprinzipien berücksichtigt, und somit eine realistische Bewertung der Signifikanz von Netzwerkeigenschaften ermöglicht. Die Ergebnisse zeigen anhand der Stoffwechselnetzwerke von sechs Organismen, dass viele der meistuntersuchten Netzwerkeigenschaften, wie das Kleine-Welt-Phänomen und die Vorhersage der Biosynthese von Stoffwechselprodukten, von herausragender Bedeutung für deren biologische Funktion sind, und somit für Vorhersagen und Modellierung verwendet werden können. Die Methode ermöglicht die Identifikation von chemischen Reaktionen, welche wahrscheinlich von lebenswichtiger Bedeutung für den Organismus sind. Weiterhin erlaubt die Methode die Vorhersage von bisher unbekannten, aber physikalisch möglichen Reaktionen, welche spezifische Zellfunktionen, wie erhöhtes Wachstum in Mikroorganismen, ermöglichen könnten. Die Methode bietet einen neuartigen Ansatz zur Bestimmung der funktional relevanten Eigenschaften biologischer Netzwerke, und eröffnet neue Möglichkeiten für deren Manipulation.

Fairneß (d.h. faire Konfliktlösung), Randomisierung (d.h. Münzwürfe) und partielle Synchronie sind verschiedene Konzepte, die häufig zur Lösung zentraler Synchronisations- und Koordinationsprobleme in verteilten Systemen verwendet werden. Beispiele für solche Probleme sind das Problem des wechselseitigen Ausschlusses (kurz: Mutex-Problem) sowie das Konsens-Problem. Für einige solcher Probleme wurde bewiesen, daß ohne die oben genannten Konzepte keine Lösung für das betrachtete Problem existiert. Unmöglichkeitsresultate dieser Art verbessern unser Verständnis der Wirkungsweise verteilter Algorithmen sowie das Verständnis des Trade-offs zwischen einem leicht analysierbaren und einem ausdrucksstarken Modell für verteiltes Rechnen. In dieser Arbeit stellen wir zwei neue Unmöglichkeitsresultate vor. Darüberhinaus beleuchten wir ihre Hintergründe. Wir betrachten dabei Modelle, die Randomisierung einbeziehen, da bisher wenig über die Grenzen der Ausdrucksstärke von Randomisierung bekannt ist. Mit einer Lösung eines Problems durch Randomisierung meinen wir, daß das betrachtete Problem mit Wahrscheinlichkeit 1 gelöst wird. Im ersten Teil der Arbeit untersuchen wir die Beziehung von Fairneß und Randomisierung. Einerseits ist bekannt, daß einige Probleme (z.B. das Konsens- Problem) durch Randomisierung nicht aber durch Fairneß lösbar sind. Wir zeigen nun, daß es andererseits auch Probleme gibt (nämlich das Mutex-Problem), die durch Fairneß, nicht aber durch Randomisierung lösbar sind. Daraus folgt, daß Fairneß nicht durch Randomisierung implementiert werden kann. Im zweiten Teil der Arbeit verwenden wir ein Modell, das Fairneß und Randomisierung vereint. Ein solches Modell ist relativ ausdrucksstark: Es erlaubt Lösungen für das Mutex-Problem, das Konsens-Problem, sowie eine Lösung für das allgemeine Mutex-Problem. Beim allgemeinen Mutex-Problem (auch bekannt als Problem der speisenden Philosophen) ist eine Nachbarschaftsrelation auf den Agenten gegeben und ein Algorithmus gesucht, der das Mutex-Problem für jedes Paar von Nachbarn simultan löst. Schließlich betrachten wir das ausfalltolerante allgemeine Mutex-Problem -- eine Variante des allgemeinen Mutex-Problems, bei der Agenten ausfallen können. Wir zeigen, daß sogar die Verbindung von Fairneß und Randomisierung nicht genügt, um eine Lösung für das ausfalltolerante allgemeine Mutex-Problem zu konstruieren. Ein Hintergrund für dieses Unmöglichkeitsresultat ist ein unerwünschtes Phänomen, für das in der Literatur der Begriff Konspiration geprägt wurde. Konspiration wurde bisher nicht adäquat charakterisiert. Wir charakterisieren Konspiration auf der Grundlage nicht-sequentieller Abläufe. Desweiteren zeigen wir, daß Konspiration für eine große Klasse von Systemen durch die zusätzliche Annahme von partieller Synchronie verhindert werden kann, d.h. ein konspirationsbehaftetes System kann zu einem randomisierten System verfeinert werden, das unter Fairneß und partieller Synchronie mit Wahrscheinlichkeit 1 konspirationsfrei ist. Partielle Synchronie fordert, daß alle relativen Geschwindigkeiten im System durch eine Konstante beschränkt sind, die jedoch den Agenten nicht bekannt ist. Die Darstellung der Unmöglichkeitsresultate und die Charakterisierung von Konspiration wird erst durch die Verwendung nicht-sequentieller Abläufe möglich. Ein nicht-sequentieller Ablauf repräsentiert im Gegensatz zu einem sequentiellen Ablauf kausale Ordnung und nicht zeitliche Ordnung von Ereignissen. Wir entwickeln in dieser Arbeit eine nicht-sequentielle Semantik für randomisierte verteilte Algorithmen, da es bisher keine in der Literatur gibt. In dieser Semantik wird kausale Unabhängigkeit durch stochastische Unabhängigkeit widergespiegelt. / Concepts such as fairness (i.e., fair conflict resolution), randomization (i.e., coin flips), and partial synchrony are frequently used to solve fundamental synchronization- and coordination-problems in distributed systems such as the mutual exclusion problem (mutex problem for short) and the consensus problem. For some problems it is proven that, without such concepts, no solution to the particular problem exists. Impossibilty results of that kind improve our understanding of the way distributed algorithms work. They also improve our understanding of the trade-off between a tractable model and a powerful model of distributed computation. In this thesis, we prove two new impossibility results and we investigate their reasons. We are in particular concerned with models for randomized distributed algorithms since little is yet known about the limitations of randomization with respect to the solvability of problems in distributed systems. By a solution through randomization we mean that the problem under consideration is solved with probability 1. In the first part of the thesis, we investigate the relationship between fairness and randomization. On the one hand, it is known that to some problems (e.g. to the consensus problem), randomization admits a solution where fairness does not admit a solution. On the other hand, we show that there are problems (viz. the mutex problem) to which randomization does not admit a solution where fairness does admit a solution. These results imply that fairness cannot be implemented by coin flips. In the second part of the thesis, we consider a model which combines fairness and randomization. Such a model is quite powerful, allowing solutions to the mutex problem, the consensus problem, and a solution to the generalized mutex problem. In the generalized mutex problem (a.k.a. the dining philosophers problem), a neighborhood relation is given and mutual exclusion must be achieved for each pair of neighbors. We finally consider the crash-tolerant generalized mutex problem where every hungry agent eventually becomes critical provided that neither itself nor one of its neighbors crashes. We prove that even the combination of fairness and randomization does not admit a solution to the crash-tolerant generalized mutex problem. We argue that the reason for this impossibility is the inherent occurrence of an undesirable phenomenon known as conspiracy. Conspiracy was not yet properly characterized. We characterize conspiracy on the basis of non-sequential runs, and we show that conspiracy can be prevented by help of the additional assumption of partial synchrony, i.e., we show that every conspiracy-prone system can be refined to a randomized system which is, with probability 1, conspiracy-free under the assumptions of partial synchrony and fairness. Partial synchrony means that each event consumes a bounded amount of time where, however, the bound is not known. We use a non-sequential semantics for distributed algorithms which is essential to some parts of the thesis. In particular, we develop a non-sequential semantics for randomized distributed algorithms since there is no such semantics in the literature. In this non-sequential semantics, causal independence is reflected by stochastic independence.

No description available.

Die vorliegende Dissertation besteht aus zwei Teilen, deren gemeinsames Thema in der Frage besteht, wie mächtig Zufall als Berechnungsressource ist. Im ersten Teil beschäftigen wir uns mit zufälligen Strukturen, die -- mit hoher Wahrscheinlichkeit -- Eigenschaften haben können, die von Computeralgorithmen genutzt werden können. In zwei konkreten Fällen geben wir bis dahin unbekannte deterministische Konstruktionen solcher Strukturen: Wir derandomisieren eine randomisierte Reduktion von Alekhnovich und Razborov, indem wir bestimmte unbalancierte bipartite Expandergraphen konstruieren, und wir geben eine Reduktion von einem Problem über bipartite Graphen auf das Problem, den minmax-Wert in Dreipersonenspielen zu berechnen. Im zweiten Teil untersuchen wir die Ausdrucksstärke verschiedener Logiken, wenn sie durch zufällige Relationssymbole angereichert werden. Unser Ziel ist es, Techniken aus der deskriptiven Komplexitätstheorie für die Untersuchung randomisierter Komplexitätsklassen nutzbar zu machen, und tatsächlich können wir zeigen, dass unsere randomisierten Logiken randomisierte Komlexitätsklassen einfangen, die in der Komplexitätstheorie untersucht werden. Unter Benutzung starker Ergebnisse über die Logik erster Stufe und die Berechnungsstärke von Schaltkreisen beschränkter Tiefe geben wir sowohl positive als auch negative Derandomisierungsergebnisse für unsere Logiken. Auf der negativen Seite zeigen wir, dass randomisierte erststufige Logik gegenüber normaler erststufiger Logik an Ausdrucksstärke gewinnt, sogar auf Strukturen mit einer eingebauten Additionsrelation. Außerdem ist sie nicht auf geordneten Strukturen in monadischer zweitstufiger Logik enthalten, und auch nicht in infinitärer Zähllogik auf beliebigen Strukturen. Auf der positiven Seite zeigen wir, dass randomisierte erststufige Logik auf Strukturen mit einem unären Vokabular derandomisiert werden kann und auf additiven Strukturen in monadischer Logik zweiter Stufe enthalten ist. / This thesis is comprised of two main parts whose common theme is the question of how powerful randomness as a computational resource is. In the first part we deal with random structures which possess -- with high probability -- properties than can be exploited by computer algorithms. We then give two new deterministic constructions for such structures: We derandomise a randomised reduction due to Alekhnovich and Razborov by constructing certain unbalanced bipartite expander graphs, and we give a reduction from a problem concerning bipartite graphs to the problem of computing the minmax-value in three-player games. In the second part we study the expressive power of various logics when they are enriched by random relation symbols. Our goal is to bridge techniques from descriptive complexity with the study of randomised complexity classes, and indeed we show that our randomised logics do capture complexity classes under study in complexity theory. Using strong results on the expressive power of first-order logic and the computational power of bounded-depth circuits, we give both positive and negative derandomisation results for our logics. On the negative side, we show that randomised first-order logic gains expressive power over standard first-order logic even on structures with a built-in addition relation. Furthermore, it is not contained in monadic second-order logic on ordered structures, nor in infinitary counting logic on arbitrary structures. On the positive side, we show that randomised first-order logic can be derandomised on structures with a unary vocabulary and is contained in monadic second-order logic on additive structures.

In diese Dissertation, betrachte ich das Problem der Aufteilung der unteilbaren Objekte unter Agenten, ihren Vorlieben entsprechend, und die Transfers fehlen. In Kapitel 1 studiere ich den Kompromiss zwischen Fairness und Effizienz in der Klasse der strategy-proof Aufteilungsmechanismen. Das wichtigste Ergebnis ist, dass für die strategy-proof Mechanismen folgende Effizienz- und Fairness-Kriterien nicht miteinander vereinbar sind: (1) Ex-post-Effizienz und Neidfreiheit, (2) Ordnung-Effizienz und schwache Neidfreiheit und (3) Ordnung-Effizienz und gleiche-Teilung-untere-Grenze. In Kapitel 2 ist der Fokus auf zwei Darstellungen einer Zuteilung: als probabilistische Zuordnung und als Lotterie über deterministische Zuordnungen. Um die Gestaltung der praktischen Lotterie-Mechanismen zu erleichtern schlagen wir neue Werkzeuge für den Erhalt der stochastischen Verbesserungen bei Lotterien vor. Als Anwendungen schlagen wir Lotterie Mechanismen, die die weit verbreiteten Random serial dictatorship Mechanismus verbessern, und eine Lotterie-Darstellung seiner Konkurrent, die Probabilistic serial Mechanismus, vor. In Kapitel 3 schlage ich einen neuen Mechanismus vor, der Schüler an Grundschulen zuweist: Adaptive Acceptance (AA). AA sammelt von Neumann-Morgenstern Präferenzen von Studenten über Schulen und implementiert die Zuordnung unter Verwendung eines iterativen Verfahrens, das ähnlich der vorherrschenden Immediate Acceptance (IA) ist. AA verfügt über eine starke Kombination von Anreize und Effizienzeigenschaften im Vergleich zu IA und sein Rivale, Deferred Acceptance (DA). / I consider the problem of allocating indivisible objects among agents according to their preferences when transfers are absent. In Chapter 1, I study the tradeoff between fairness and efficiency in the class of strategy-proof allocation mechanisms. The main finding is that for strategy-proof mechanisms the following efficiency and fairness criteria are mutually incompatible: (1) Ex-post efficiency and envy-freeness, (2) ordinal efficiency and weak envy-freeness and (3) ordinal efficiency and equal division lower bound. In Chapter 2, the focus is on two representations of an allocation when randomization is used: as a probabilistic assignment and as a lottery over deterministic assignments. To help facilitate the design of practical lottery mechanisms, we provide new tools for obtaining stochastic improvements in lotteries. As applications, we propose lottery mechanisms that improve upon the widely-used random serial dictatorship mechanism, and a lottery representation of its competitor, the probabilistic serial mechanism. In Chapter 3, I propose a new mechanism to assign students to primary schools: the Adaptive Acceptance rule (AA). AA collects von Neumann-Morgenstern utilities of students over schools and implements the assignment using an iterative procedure similar to the prevalent Immediate Acceptance rule (IA). AA enjoys a strong combination of incentive and efficiency properties compared to IA and its rival, the Deferred Acceptance rule (DA). In case of strict priorities, AA implements the student-optimal stable matching in dominant strategies, which dominates each equilibrium outcome of IA. In case of no priorities, AA is ex-post efficient while some equilibrium outcomes of IA are not; also, AA causes loss of ex-ante efficiency less often than DA. If, in addition, students have common ordinal preferences, AA is approximately strategy-proof and ex-ante dominates DA.