Das Buch "Verteilte Algorithmen. Intuitiver Ansatz "

    BildDieses Buch ist für einen Kurs über verteilte Algorithmen für Studenten und Doktoranden in Fachgebieten der Informatik und Softwaretechnik konzipiert. Es kann auch von Forschern in diesen Bereichen als Referenz verwendet werden. Das Buch konzentriert sich auf grundlegende Algorithmen und Ergebnisse auf dem Gebiet des verteilten Rechnens. Die darin betrachteten Algorithmen sind hauptsächlich „klassische“ und wurden in erster Linie ausgewählt, weil sie unter dem Gesichtspunkt des Entwurfs von Algorithmen für verteilte Systeme lehrreich sind oder wichtige Probleme bei der verteilten und parallelen Programmierung beleuchten.

    Das Buch besteht aus zwei Teilen. Der erste Teil befasst sich mit der Interaktion von Prozessen durch Nachrichtenübermittlung. Es basiert auf einem Kurs an der Vrije Universität (Amsterdam), der ursprünglich auf dem Lehrbuch „Introduction to Distributed Algorithms“ von Gerard Tel. Der zweite Teil ist Shared-Memory-Architekturen gewidmet.

    Einleitung


    Ein Algorithmus ist ein schrittweises Verfahren zur Lösung eines bestimmten Problems durch einen Computer. Um ein qualifizierter Programmierer zu werden, müssen Sie die Algorithmen gut verstehen. Jedes Bildungsprogramm im Bereich der Informatik bietet einen oder mehrere Kurse zu den Grundlagen der Algorithmisierung an. In der Regel betrachten sie Algorithmen zum Suchen und Sortieren, zur Mustererkennung und zum Auffinden der kürzesten Wege in Diagrammen. Sie lehren die Schüler, solche Teilaufgaben in ihren Computerprogrammen zu identifizieren und effektiv zu lösen. Darüber hinaus lernen die Studierenden, algorithmisch zu denken, die Richtigkeit von Algorithmen zu beweisen und eine einfache Komplexitätsanalyse zu erstellen.

    Distributed Computing ist viel komplizierter als Einprozessor-Computing und unterscheidet sich stark von diesen, da die Ausführung von Teilen einer Aufgabe auf den Knoten eines verteilten Systems zeitlich verschachtelt ist. Wenn zwei Knoten gleichzeitig bestimmte Aktionen ausführen, ist es unmöglich vorherzusagen, welche davon früher ausgeführt werden. Dies führt beispielsweise zu dem sogenannten Racing-Effekt: Wenn zwei Nachrichten im Netzwerk an demselben Knoten ankommen, kann das Verhalten des Knotens davon abhängen, welche Nachricht früher ankommt. Verteilte Systeme sind daher nicht deterministisch - ein zweimaliges Starten des Systems in derselben Konfiguration aus demselben Ausgangszustand kann zu unterschiedlichen Ergebnissen führen. Darüber hinaus nimmt die Anzahl erreichbarer Zustände mit zunehmender Anzahl von Knoten exponentiell zu.

    Ein weiterer wichtiger Unterschied zwischen verteiltem und Einprozessor-Computing besteht darin, dass die Knoten in einem verteilten System im Allgemeinen keine relevanten Informationen über den globalen Status des Systems haben. Sie kennen ihre eigenen lokalen Zustände, aber sie wissen nicht immer über die lokalen Zustände anderer Knoten oder Nachrichten Bescheid, die gerade übertragen werden. Beispielsweise wird es problematisch, festzustellen, wann die Ausführung abgeschlossen ist. Es sollte festgestellt werden, dass alle Knoten im System die Arbeit abgeschlossen haben, aber auch in diesem Fall kann sich herausstellen, dass noch eine Nachricht gesendet wird, die eine Aktivierung des empfangenden Knotens bewirkt.

    Dieses Buch bietet Ihnen eine breite Palette grundlegender Algorithmen, mit denen Sie solche Schlüsselprobleme in verteilten Systemen lösen können. Sie können beispielsweise bestimmen, wann die Berechnungen abgeschlossen sind und wann die Knoten ein gemeinsames Bild des globalen Systemzustands erstellen. Hauptziel ist es, die algorithmische Denkweise der Studierenden so zu gestalten, dass sie grundlegende Probleme im Bereich des Distributed Computing erkennen und lösen können. Sie werden zu einem umfassenden Überblick über diese Probleme aus der Vogelperspektive sowie zum Nachweis der Korrektheit "an den Fingern" und zu ungefähren Methoden zur Beurteilung der Komplexität eingeladen.

    Die beiden Hauptkommunikationsparadigmen bei der verteilten Datenverarbeitung sind Nachrichtenübertragung, bei der Knoten über Kanäle Nachrichten aneinander senden, und gemeinsamer Speicher, wenn verschiedene ausführbare Threads in gemeinsame Speicherbereiche lesen und schreiben können. Das Buch ist in zwei Teile unterteilt, die diesen beiden Kommunikationsparadigmen gewidmet sind. Der Rest der Einleitung enthält vorläufige Informationen zu beiden Ansätzen.

    Viele


    Wie üblich bezeichnen S1 ≤ S2, S1 \ S2 und S1 ≤ S2 die Vereinigung, Differenz und Einbeziehung von Mengen; s ∈ S bedeutet, dass s ein Element der Menge S ist. Die Mengen natürlicher und reeller Zahlen werden mit und bezeichnet. Boolesche (boolesche) Variablen haben die Werte true (true) und false (false). Eine Menge kann in der Form {... | ...} geschrieben werden, in der ihre Elemente links von der vertikalen Leiste angegeben sind und die Bedingung, die sie erfüllen müssen, rechts. Zum Beispiel {n ∈ | n> 5} steht für eine Menge natürlicher Zahlen größer als 5. Eine leere Menge wird mit dem Symbol Ø gekennzeichnet. Für jede endliche Menge S wird die Anzahl der darin enthaltenen Elemente mit | S | bezeichnet.

    Komplexitätsmaßnahmen


    Komplexitätsmaße zeigen, wie der Ressourcenverbrauch (Nachrichten, Zeit, Speicher) im Verhältnis zur Größe der Eingabedaten zunimmt. Wenn zum Beispiel der Algorithmus im schlimmsten Fall eine Komplexität von 0 (n2) Nachrichten aufweist, dann erfordert der Algorithmus für Eingabedaten der Größe n im schlimmsten Fall die Übertragung der Größenordnung von n2 Nachrichten plus oder minus einer Konstanten.

    Bild

    Bild

    Teil I des Messaging-Paradigmas befasst sich hauptsächlich mit der Komplexität von Nachrichten. Bit-Komplexität ist nur dann interessant, wenn Nachrichten sehr lang sein können. Bei der Analyse der Zeitkomplexität wird davon ausgegangen, dass die Verarbeitung von Ereignissen keine Zeit erfordert und der Empfang einer Nachricht nach dem Senden maximal eine Zeiteinheit dauert. Unterschiedliche Starts können zu unterschiedlichem Ressourcenverbrauch führen. Wir betrachten Komplexität für den ungünstigsten Fall und die durchschnittliche Komplexität, und für letztere geben wir eine bestimmte Wahrscheinlichkeitsverteilung über alle Starts an.

    Ordnungsverhältnisse


    Eine Beziehung der (strengen) Ordnung auf einer Menge S ist eine irreflexive, asymmetrische und transitiv binäre Beziehung auf ihren Elementen. Dies bedeutet, dass für jedes a, b, c ≤ S, a <a; wenn a <b, dann b <a; und wenn a <b und b <c, dann a <c. Eine Reihenfolge heißt streng, wenn für ein anderes a b ∈ S entweder a <b oder b <a ist; Andernfalls wird die Bestellung als teilweise bezeichnet. Es seien zwei Mengen S1 und S2 mit Beziehungen der Ordnung <1 bzw. <2 gegeben. Dann ist die lexikographische Ordnungsrelation <bei Paaren aus S1 × S2 definiert als (a1, a2) <(b1, b2), wenn entweder a1 <1 b1 oder a1 = b1 und a2 <2 b2. Wenn <1 und <2 strenge Ordnungsrelationen sind, ist die entsprechende lexikografische Ordnungsrelation eine strenge Ordnungsrelation.

    Modulare Arithmetik


    Eine ganzzahlige Ringmodulo-positive ganze Zahl n wird durch die Elemente {0 ... n - 1} dargestellt. Jede ganze Zahl k hat einen repräsentativen Rest der Division durch n, der mit k mod n bezeichnet wird. Dies ist das einzige ℓ ∈ {0 ... n - 1}, bei dem k - ится vollständig durch n teilbar ist. Dies bedeutet, dass bei Erreichen von n eine zyklische Rückkehr auftritt: n mod n ist 0, (n + 1) mod n ist 1 usw. Addition und Subtraktion werden auf einfache Weise in modulare Arithmetik übertragen: (j mod n) + (k mod n) = (j + k) mod n und (j mod n) · (k mod n) = (j · k) mod n.

    Übungen


    Bild

    »Weitere Informationen zum Buch finden Sie auf der Website des Herausgebers.
    » Inhalt
    » Auszug

    für Khabrozhiteley 25% Rabatt auf Coupon - Algorithmen
    Das Buch ist leider nur in Papierform erhältlich.

    Jetzt auch beliebt: