68-XX COMPUTER SCIENCE (For papers involving machine computations and programs in a specific mathematical area, see Section -04 in that area)
Refine
Year of publication
- 2013 (3)
Document Type
- Bachelor's Thesis (1)
- Master's Thesis (1)
- ZIB-Report (1)
Language
- German (3) (remove)
Has Fulltext
- yes (3)
Is part of the Bibliography
- no (3) (remove)
Keywords
- Forschungsdatenmanagement (1)
- Langzeitverfügbarkeit (1)
- algorithm (1)
- dht (1)
- scalaris (1)
„Ich mache ihm ein Angebot, das er nicht ablehnen kann.” Diese Aussage aus einem gänzlich anderen Kontext lässt sich recht treffend übertragen als Wunsch von Dienstleistern und Zweck von Dienstleistungen für Datenproduzenten im Forschungsdatenmanagement. Zwar wirkt Druck zur Datenübergabe nicht förderlich, die Eröffnung einer Option aber sehr wohl. Im vorliegenden Artikel geht es um das Verständnis der Nachhaltigkeit von Forschung und ihren Daten anhand der Erkenntnisse und Erfahrungen aus der ersten Phase des DFG-Projekts EWIG. [Fn 01] Eine Auswahl von Fallstricken beim Forschungsdatenmanagement wird anhand der Erkenntnisse aus Expertengesprächen und eigenen Erfahrungen beim Aufbau von LZA-Workflows vorgestellt. Erste Konzepte in EWIG zur Datenübertragung aus unterschiedlich strukturierten Datenquellen in die „Langfristige Domäne” werden beschrieben.
Snapshots in Scalaris
(2013)
Eines der größten Hindernisse beim praktischen Einsatz von Scalaris, einer skalierbaren Implementierung einer verteilten Hashtabelle mit Unterstützung für Transaktionen, ist das Fehlen eines Verfahrens zur Aufnahme eines konsistenten Zustandes des gesamten Systems. Wir stellen in dieser Arbeit ein einfaches Protokoll vor, dass diese Aufgabe erfüllt und sich, auf Grund der von uns gewählten Herangehensweise, leicht implementieren lässt.
Als Ausgangspunkt dafür wählen wir aus einer Reihe von „klassischen“ Snapshot-Algorithmen ein 1993 von Mattern entworfenes Verfahren, welches auf dem Algorithmus von Lai und Yang basiert, aus. Diese Entscheidung basiert auf einer gründlichen Analyse der Protokolle unter Berücksichtigung der Architektur der existierenden Software.
Im nächsten Arbeitsschritt benutzen wir unser vollständiges Wissen über die Interna des Transaktionssystems von Scalaris und vereinfachen damit das Verfahren hinsichtlich Benutzbarkeit und Implementierungskomplexität, ohne die Anforderungen an den aufgenommenen Zustand aufzuweichen. Statt einer losen Anhäufung lokaler Zustände der einzelnen Teilnehmerknoten können wir am Ende eine große Schlüssel-Wert-Tabelle als Ergebnis erzeugen, die konsistent ist, sich leicht weiterverarbeiten lässt und die einem Zustand entspricht, in dem sich das System einmal befunden haben könnte.
Nachdem wir das Verfahren dann in Software umgesetzt haben, werten wir die Ergebnisse hinsichtlich des Einflusses auf die Performanz des Gesamtsystems aus und diskutieren mögliche Weiterentwicklungen.
Heutzutage ist eine Vielzahl der mehrstöckigen Gebäude mit Personenaufzugsgruppen
ausgestattet. Uns wohl bekannt sind die sogenannten konventionellen Systeme. Bei
diesen Systemen betätigt jeder ankommende Passagier eine der beiden Richtungstasten
und teilt dem dahinterstehenden Steuerungsalgorithmus seine gewünschte Startetage
und Fahrtrichtung mit. Betreten wird der zuerst auf der Startetage ankommende Aufzug
mit gleicher Fahrtrichtung und ausreichend Kapazität. Die entsprechende Zieletage
wird dem System erst nach dem Betreten der Fahrgastkabine mitgeteilt. Neben diesen
konventionellen Systemen gibt es Aufzugsgruppen mit Zielrufsteuerung. Die Besonderheit
eines zielrufgesteuerten Systems ist, dass ein ankommender Passagier bereits auf
der Startetage seine gewünschte Zieletage angibt und eine Rückmeldung vom System
erhält, welchen Aufzug er nutzen soll. Diese Zuweisung durch das System hat das Ziel,
die Warte- und Reisezeiten der Passagiere zu minimieren. Ein wesentlicher Faktor bei
der Berechnung warte- und reisezeitminimaler Fahrpläne ist das momentane Verkehrsmuster.
Eine Einteilung der Verkehrsszenarien lässt sich am besten bei Bürogebäuden
vornehmen. So ist es typisch für die Morgenstunden, dass jeder Passagier auf einer
Zugangsebene seine Fahrt beginnt und alle Passagiere die gleiche Fahrtrichtung haben.
Unter einer Zugangsebene ist z. B. der Haupteingang oder ein Parkdeck zu verstehen.
Ein weiterer wesentlicher Punkt bei Zielrufsystemen ist die Art der Zuweisung der Passagiere
durch das System. Zum einen gibt es unmittelbar zuweisende (UZ-) Systeme.
In einem UZ-System wird nach jeder Ankunft eines Passagiers eine Momentaufnahme
des momentanen Verkehrs erstellt und es findet eine Neuplanung und Zuweisung statt.
Eine solche Momentaufnahme werden wir im späteren Verkauf als Schnappschussproblem
bezeichnen. Jeder Passagier bekommt im Anschluss an die Lösung des Schnappschussproblems
eine Mitteilung vom System, z. B. über ein Display, welchen Aufzug
er benutzen soll. Zum anderen gibt es verzögert zuweisende (VZ-) Systeme. In diesen
Systemen wird die Erstellung und Lösung eines Schnappschussproblems bis kurz vor
Ankunft eines Aufzuges auf einer Etage verzögert. In einem VZ-System teilt das System
allen wartenden Passagieren die geplanten Zieletagen des ankommenden Aufzugs mit.
Jeder Passagier, der einen Ruf getätigt hat und zu einer dieser Zieletagen fahren will,
kann jetzt diesen Aufzug betreten. Durch die Verzögerung muss im Vergleich zu einem
UZ-System eine weitaus größere Menge von Passagieren zugewiesen werden. Dadurch
kann der Lösungsprozess bedeutend aufwändiger werden. Vorteil eines VZ-Systems ist
hingegen der größere Freiheitsgrad bei der Optimierung, da aufgrund der späten Zuweisung
die weitere Verkehrsentwicklung mit einbezogen werden kann.
VZ-Systeme sind aufgrund des größeren Freiheitsgrades interessant für die
Praxis ist, wir uns demzufolge in dieser Arbeit mit einer effizienteren Lösung dieser
Art von Schnappschussproblemen befassen. Es genügt dabei den Lösungsprozess eines
Schnappschussproblems zu betrachten. Das Ziel ist eine Reduzierung der benötigten
Rechenzeit. Unter Reoptimierung verstehen wir die Konstruktion
zulässiger Spalten in den jeweiligen Iterationsrunden der Spaltengenerierung
innerhalb eines Schnappschussproblems. Als eine Iterationsrunde bezeichnet wir einer
Menge zulässiger Touren mit negativen reduzierten Kosten. Eine effiziente Reoptimierung
zeichnet sich durch die Wiederverwendung und Aufbereitung von Informationen
aus vorangegangenen Iterationsrunden desselben Schnappschussproblems aus. Zu den
wichtigen Informationen gehört der konstruierte Suchbaum der vorherigen Iterationsrunde
mit seinen ausgeloteten (abgeschnittenen) Blättern sowie konstruierten Touren
bzw. Spalten, welche in der Iterationsrunde ihrer Konstruktion nicht zur Lösung des
Teilproblems der Spaltengenerierung beitrugen. Eine solche Wiederverwendung und
Aufbereitung von Informationen nennen wir Warmstart.