50 years Univerity of Lübeck

Institute for Theoretical Computer Science

Events 2000


Talks

  • 12. Dezember 2000, 18 Uhr ct H1/SFS
    Dr. Berthold Vöcking, MPI für Informatik, Saarbrücken
    How Asymmetry Helps Load Balancing

    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.

  • 6. September 2000, 11 Uhr ct, H1/SFS
    Prof. Faith E. Fich, University of Toronto/Canada
    Lower Bounds for Distributed Computing

    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.

  • 21. Juni 2000, 17 Uhr ct, H3, Haus 21
    Prof. Dr. Raul Rojas, Freie Universität Berlin
    Die Computer des Konrad Zuse: Ein moderner Rückblick auf den Anfang der Computerentwicklungen vor 60 Jahren.<

    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:

    • Sie waren Floating-Point Rechner
    • Der Prozessor war vom Speicher getrennt
    • Die Addition wurde in konstanter Zeit berechnet (d.h. unabhängig von der Anzahl der Bits)
    • Shifts wurden ebenfalls in konstanter Zeit berechnet
    • Die Maschinen waren Mikroprogrammiert

    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)

  • 8. Juni 2000, 18 Uhr ct, Hörsaal 1/SFS
    Prof. Carl Smith, Department of Computer Science, University of Maryland
    Towards a Model of Object Oriented Programming

    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)

  • 30. Mai 2000, 16 Uhr ct, Raum H1/SFS
    Hagen Völzer, Institut für Informatik, Humboldt-Universität zu Berlin
    Fairness, Randomisierung und Konspiration in verteilten Algorithmen

    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.