Nachrichtenübermittlung und gemeinsamer Speicher

Nachrichtenübermittlung (Message Passing) und gemeinsamer Speicher (Shared Memory) sind die zwei grundlegenden Abstraktionen, über die nebenläufige Prozesse interagieren. Ein Großteil der verteilten Datenverarbeitung befasst sich damit, wie man das eine mit dem anderen simulieren kann.

Definition

Im Nachrichtenübermittlungsmodell kommunizieren Prozesse nur durch Senden und Empfangen von Nachrichten über Kanäle; im Shared-Memory-Modell kommunizieren sie durch Lesen und Schreiben von Shared Objects wie Registern. Jedes ist ein präzises Berechnungsmodell mit eigenen Korrektheitsbedingungen.

Scope

Dieses Thema behandelt Punkt-zu-Punkt- und Broadcast-Nachrichtenübermittlungsmodelle mit ihren Zustell- und Ordnungssemantiken, Shared-Memory-Modelle, die aus Lese-/Schreibregistern und stärkeren Synchronisationsobjekten aufgebaut sind, sowie die klassischen Ergebnisse, die zeigen, wie Shared Memory über Nachrichtenübermittlung (und umgekehrt) unter verschiedenen Fehlerannahmen emuliert werden kann. Es behandelt auch die Registerhierarchie und die Konsensushierarchie, die die Leistungsfähigkeit von Shared Objects bewerten.

Core questions

• Welche Zustell- und Ordnungsgarantien bietet ein Kanal, und wie beeinflussen sie den Algorithmusentwurf?
• Kann eine Shared-Memory-Abstraktion zuverlässig auf einem unzuverlässigen Nachrichtenübermittlungsnetzwerk aufgebaut werden?
• Wie unterscheiden sich Synchronisationsobjekte in ihrer Fähigkeit, Konsens zu lösen?

Key theories

Register- und Konsensushierarchie

Shared Objects werden nach ihrer Konsensusnummer geordnet – der maximalen Anzahl von Prozessen, für die sie einen wartefreien Konsens lösen können –, wobei einfache Lese-/Schreibregister am unteren Ende und universelle Objekte wie Compare-and-Swap am oberen Ende platziert werden.

Registerkonstruktionen

Lamports Hierarchie von sicheren, regulären und atomaren Registern sowie Konstruktionen, die stärkere Register aus schwächeren aufbauen, formalisieren genau, was es bedeutet, dass nebenläufige Lese- und Schreibvorgänge korrekt funktionieren.

Simulieren von Shared Memory über Nachrichtenübermittlung

Atomare Single-Writer- und Multi-Writer-Register können über ein asynchrones Nachrichtenübermittlungsnetzwerk emuliert werden, das eine Minderheit von Absturzfehlern toleriert, unter Verwendung von Quorum-Techniken, wodurch die beiden Kommunikationsmodelle vereinheitlicht werden.

Clinical relevance

Die Unterscheidung zwischen Nachrichtenübermittlung und gemeinsamem Speicher lässt sich direkt auf reale Plattformen übertragen: Cluster und die Cloud sind Nachrichtenübermittlungssysteme, Multicore-Server stellen Shared Memory bereit, und verteilte Schlüssel-Wert-Speicher bieten effektiv eine Shared-Register-Abstraktion über ein Nachrichtenübermittlungsnetzwerk.

History

Lamports Arbeiten von 1986 formalisierten nebenläufige Register; Herlihys wartefreie Hierarchie von 1991 ordnete Synchronisationsprimitive nach ihrer Konsensusnummer; und Attiya und Welchs Text konsolidierte die Simulationen, die Nachrichtenübermittlung und Shared Memory in Beziehung setzen, und etablierte die Dualität, die den Kern des Feldes bildet.

Key figures

• Leslie Lamport
• Maurice Herlihy
• Nir Shavit
• Hagit Attiya
• Jennifer Welch

Seminal works

• herlihy2008
• attiya2004
• lamport1986

Frequently asked questions

Sind Nachrichtenübermittlung und gemeinsamer Speicher äquivalent?

Sie sind in Bezug auf die Rechenleistung unter geeigneten Fehlerannahmen äquivalent – jedes kann das andere simulieren –, unterscheiden sich jedoch stark in Bezug auf Programmierkomfort und Leistung, weshalb Systeme eines als ihr natives Modell wählen.