This talk deals with balls and bins processes related to randomized load balancing, dynamic resource allocation, and hashing. Suppose n balls have to be assigned to n bins, where each ball has to be placed without knowledge about the distribution of previously placed balls. The goal is to achieve an allocation that is as even as possible so that no bin gets much more balls than the average. A well known and good solution for this problem is to choose d possible locations for each ball at random, to look into each of these bins, and to place the ball into the least full among these bins. This class of algorithms has been investigated intensively in the past, but almost all previous analyses assume that the dlocations for each ball are chosen uniformly and independently at random from the set of all bins.
We investigate whether a non-uniform and possibly dependent choice of the d locations for a ball can improve the load balancing. Three types of selections are distinguished: 1) uniform and independent 2) non-uniform and independent 3) non-uniform and dependent. Our first result shows that choosing the locations in a non-uniform way (type 2) results in a better load balancing than choosing the locations uniformly (type 1). Surprisingly, this smooth load balancing is obtained by an algorithm called ``Always-Go-Left'' which creates an asymmetric assignment of the balls to the bins. Our second result is a lower bound on the smallest possible maximum load that can be achieved by any allocation algorithm of type 1, 2, or 3. Our upper and lower bounds are tight up to a small additive constant, showing that the Always-Go-Left scheme achieves almost the optimal load balancing.
Furthermore, we show that our upper bound can be generalized to infinite processes in which balls are inserted and deleted by an adversary.
What can be computed in a distributed system in which faults can occur? This talk will address what CANNOT be computed in certain environments or when insufficient resources are available. A number of techniques for obtaining lower bounds and impossibility results in distributed computing will be surveyed. These include valency arguments, covering arguments, characterizations, and topological arguments.
In meinem Vortrag werde ich die Architektur der ersten von Konrad Zuse gebauten Rechenmaschinen erläutern. Allen lag ein gemeinsamer Gedanke zugrunde: die Effiziente Ausführung von Gleitkomma-Operationen für wissenschaftliches Rechnen.
Speziell gilt für diese Maschinen:
Ich werde auch zeigen, dass diese Maschinen universell waren, d.h. eine Turing Maschine liesse sich damit simulieren, obwohl der bedingte Sprung nicht im Befehlssatz vorhanden war.
Am Ende werde ich die Verbindung zwischen dem Plankalkül und den Rechenmaschinen erläutern. Ich werde Simulationen der Rechenmaschinen, den ersten Plankalkül-Compiler, sowie das erste Schachprogramm der Welt laufen lassen.
Mehr Information unter: www.zib.de/zuse
Zum Vortragenden: Prof. Rojas ist Leiter der Arbeitsgruppe
Künstliche Intelligenz an der FU
Berlin .
Neben zahlreichen Zeitschriften-Veröffentlichungen hat er als
Autor oder Herausgeber mehrere Bü verfasst, u.a. "The First
Computers - History and Architectures", "Die Rechenmaschinen von Konrad
Zuse", "Neural Networks - A Systematic Introduction" und "Die Armut der
Nationen".
Die Arbeitsgruppe ist Europameister 2000 in Robotic Soccer (small size category)
We introduce an object-oriented model of computation called OOPSILON. We prove that it is Church-Rosser, Turing-complete, and an acceptable programming system. The first two properties make this a valid model of computation worth studying, while the third supplies a unique notion of self given for free by the Recursion Theorem.
OOPSILON differs from previous object calculi through its direct support for partially-constructed objects, and for data-driven rather than function-driven programming. It also serves as a nice formalism to discuss context.
(Joint work with Ken Regan and Brian Postow)
Zur Lösung grundlegender Synchronisations- und Koordinationsprobleme in verteilten Systemen (z.B. Mutex-Problem, Konsens-Problem) verwendet man Konzepte wie Fairness, Randomisierung und Synchronie, Manchmal kann man nachweisen, dass ohne solche Konzepte keine Lösung für bestimmte Probleme existiert. Solche Unmöglichkeitsresultate verbessern unser Verständnis der Wirkungsweise verteilter Algorithmen.
In dieser Arbeit werden zwei neue Unmöglichkeitsresultate gezeigt und die Ursachen untersucht. Dabei spielt ein grundlegendes Phänomen in verteilten Systemen eine entscheidende Rolle, für das in der Literatur der Begriff Konspiration geprägt wurde. Konspiration verhindert, dass ein Algorithmus seine Ziele erreicht und ist daher unerwünscht. In dieser Arbeit gelang es Konspiration zu charakterisieren und einen Zusammenhang von Konspiration und Fehlertoleranz darzustellen.
