edoc-Server der Humboldt-Universität zu Berlin

Dissertation

Autor(en): Tobias Vesper
Titel: Petrinetze zum Entwurf selbststabilisierender Algorithmen
Gutachter: Hans Jürgen Prömel; Jörg Desel; Wolfgang Reisig
Erscheinungsdatum: 08.12.2000
Volltext: pdf (urn:nbn:de:kobv:11-10014574)
ps (urn:nbn:de:kobv:11-10014582)
Fachgebiet(e): Informatik
Schlagwörter (ger): Selbststabilisierung, verteiltes System, verteilter Algorithmus, Petrinetz
Schlagwörter (eng): self-stabiilization, distributed system, distributed algorithm, Petri net
Einrichtung: Humboldt-Universität zu Berlin, Mathematisch-Naturwissenschaftliche Fakultät II
Zitationshinweis: Vesper, Tobias: Petrinetze zum Entwurf selbststabilisierender Algorithmen; Dissertation, Humboldt-Universität zu Berlin, Mathematisch-Naturwissenschaftliche Fakultät II , publiziert am 08.12.2000, urn:nbn:de:kobv:11-10014582
Metadatenexport: Um den gesamten Metadatensatz im Endnote- oder Bibtex-Format zu speichern, klicken Sie bitte auf den entsprechenden Link. Endnote   Bibtex  
print on demand: Wenn Sie auf dieses Icon klicken, können Sie ein Druckexemplar dieser Publikation bestellen.
Diese Seite taggen: Diese Icons führen auf so genannte Social-Bookmark-Systeme, auf denen Sie Lesezeichen anlegen, persönliche Tags vergeben und Lesezeichen anderer Nutzer ansehen können.
  • connotea
  • del.icio.us
  • Furl
  • RawSugar

Abstract (ger):
Edsger W. Dijkstra prägte im Jahr 1974 den Begriff Selbststabilisierung (self-stabilization) in der Informatik. Ein System ist selbststabilisierend, wenn es von jedem denkbaren Zustand aus nach einer endlichen Anzahl von Aktionen ein stabiles Verhalten erreicht. Im Mittelpunkt dieser Arbeit steht der Entwurf selbststabilisierender Algorithmen. Wir stellen eine Petrinetz-basierte Methode zum Entwurf selbststabilisierender Algorithmen vor. Wir validieren unsere Methode an mehreren Fallstudien: Ausgehend von algorithmischen Ideen existierender Algorithmen beschreiben wir jeweils die die schrittweise Entwicklung eines neuen Algorithmus. Dazu gehört ein neuer randomisierter selbststabilisierender Algorithmus zur Leader Election in einem Ring von Prozessoren. Dieser Algorithmus ist abgeleitet aus einem publizierten Algorithmus, von dem wir hier erstmals zeigen, daß er fehlerhaft arbeitet. Wir weisen die Speicherminimalität unseres Algorithmus nach. Ein weiteres Ergebnis ist der erste Algorithmus, der ohne Time-Out-Aktionen selbststabilisierenden Tokenaustausch in asynchronen Systemen realisiert. Petrinetze bilden einen einheitlichen formalen Rahmen für die Modellierung und Verifikation dieser Algorithmen.
Abstract (eng):
In 1974, Edsger W. Dijkstra suggested the notion of self-stabilization. A system is self-stabilizing if regardless of the initial state it eventually reaches a stable behaviour. This thesis focuses on the design of self-stabilizing algorithms. We introduce a new Petri net based method for the design of self-stabilizing algorithms. We validate our method on several case studies. In each of the case studies, our stepwise design starts from an algorithmic idea and leads to a new self-stabilizing algorithm. One of these algorithms is a new randomized self-stabilizing algorithm for leader election in a ring of processors. This algorithm is derived from a published algorithm which we show to be incorrect. We prove that our algorithm is space-minimal. A further result is the first algorithm for token-passing in a asynchronous environment which works without time-out actions. Petri nets form a unique framework for modelling and verification of these algorithms.
Zugriffsstatistik: Die Daten für die Zugriffsstatistik der einzelnen Dokumente wurden aus den durch AWStats aggregierten Webserver-Logs erstellt. Sie beziehen sich auf den monatlichen Zugriff auf den Volltext sowie auf die Startseite. Die Zugriffsstatistik wird nicht standardisiert erfasst und kann maschinelle Zugriffe enthalten.
 
Bei Formatversionen eines Dokuments, die aus mehreren Dateien bestehen (insbesondere HTML), wird jeweils der monatlich höchste Zugriffswert auf eine der Dateien (Kapitel) des Dokuments angezeigt.
 
Um die detaillierten Zugriffszahlen zu sehen, fahren Sie bitte mit dem Mauszeiger über die einzelnen Balken des Diagramms.
Startseite: 2 Zugriffe PDF: 2 Zugriffe Startseite: 1 Zugriffe PDF: 4 Zugriffe Startseite: 4 Zugriffe PDF: 3 Zugriffe Startseite: 2 Zugriffe PDF: 3 Zugriffe Startseite: 2 Zugriffe PDF: 14 Zugriffe Startseite: 3 Zugriffe PDF: 16 Zugriffe PDF: 11 Zugriffe PDF: 10 Zugriffe PDF: 5 Zugriffe Startseite: 4 Zugriffe PDF: 10 Zugriffe Startseite: 5 Zugriffe PDF: 12 Zugriffe Startseite: 4 Zugriffe PDF: 18 Zugriffe PDF: 9 Zugriffe PDF: 7 Zugriffe PDF: 19 Zugriffe PDF: 9 Zugriffe Startseite: 4 Zugriffe PDF: 20 Zugriffe Startseite: 5 Zugriffe PDF: 43 Zugriffe Startseite: 1 Zugriffe PDF: 19 Zugriffe PDF: 26 Zugriffe Startseite: 1 Zugriffe PDF: 21 Zugriffe Startseite: 1 Zugriffe PDF: 8 Zugriffe PDF: 12 Zugriffe Startseite: 7 Zugriffe PDF: 15 Zugriffe PDF: 11 Zugriffe Startseite: 3 Zugriffe PDF: 10 Zugriffe Startseite: 3 Zugriffe PDF: 29 Zugriffe Startseite: 1 Zugriffe PDF: 24 Zugriffe Startseite: 6 Zugriffe PDF: 19 Zugriffe Startseite: 2 Zugriffe PDF: 12 Zugriffe PDF: 19 Zugriffe Startseite: 2 Zugriffe PDF: 22 Zugriffe Startseite: 5 Zugriffe PDF: 20 Zugriffe PDF: 18 Zugriffe Startseite: 3 Zugriffe PDF: 26 Zugriffe Startseite: 1 Zugriffe PDF: 13 Zugriffe Startseite: 2 Zugriffe PDF: 19 Zugriffe
Jul
11
Aug
11
Sep
11
Oct
11
Nov
11
Dec
11
Feb
12
Apr
12
May
12
Jun
12
Jul
12
Aug
12
Sep
12
Oct
12
Nov
12
Dec
12
Jan
13
Feb
13
Mar
13
Apr
13
May
13
Jun
13
Jul
13
Aug
13
Sep
13
Oct
13
Nov
13
Dec
13
Jan
14
Feb
14
Mar
14
Apr
14
May
14
Jun
14
Jul
14
Aug
14
Sep
14
Monat Jul
11
Aug
11
Sep
11
Oct
11
Nov
11
Dec
11
Feb
12
Apr
12
May
12
Jun
12
Jul
12
Aug
12
Sep
12
Oct
12
Nov
12
Dec
12
Jan
13
Feb
13
Mar
13
Apr
13
May
13
Jun
13
Jul
13
Aug
13
Sep
13
Oct
13
Nov
13
Dec
13
Jan
14
Feb
14
Mar
14
Apr
14
May
14
Jun
14
Jul
14
Aug
14
Sep
14
Startseite 2 1 4 2 2 3       4 5 4         4 5 1   1 1   7   3 3 1 6 2   2 5   3 1 2
PDF 2 4 3 3 14 16 11 10 5 10 12 18 9 7 19 9 20 43 19 26 21 8 12 15 11 10 29 24 19 12 19 22 20 18 26 13 19

Gesamtzahl der Zugriffe seit Jul 2011:

  • Startseite – 74 (2 pro Monat)
  • PDF – 558 (15.08 pro Monat)
 
 
Generiert am 25.10.2014, 04:23:59