Truyền thông điệp và Bộ nhớ chia sẻ

Truyền thông điệp và bộ nhớ chia sẻ là hai trừu tượng cơ bản mà qua đó các tiến trình đồng thời tương tác, và phần lớn các nghiên cứu về điện toán phân tán tập trung vào cách mô phỏng cái này bằng cái kia.

Definition

Trong mô hình truyền thông điệp, các tiến trình chỉ giao tiếp bằng cách gửi và nhận thông điệp qua các kênh; trong mô hình bộ nhớ chia sẻ, chúng giao tiếp bằng cách đọc và ghi các đối tượng chia sẻ như thanh ghi. Mỗi mô hình là một mô hình tính toán chính xác với các điều kiện đúng đắn riêng.

Scope

Chủ đề này bao gồm các mô hình truyền thông điệp điểm-điểm và quảng bá với ngữ nghĩa phân phối và sắp xếp của chúng, các mô hình bộ nhớ chia sẻ được xây dựng từ các thanh ghi đọc/ghi và các đối tượng đồng bộ hóa mạnh hơn, cũng như các kết quả kinh điển cho thấy cách bộ nhớ chia sẻ có thể được mô phỏng trên nền truyền thông điệp (và ngược lại) trong các giả định lỗi khác nhau. Nó cũng bao gồm hệ thống phân cấp thanh ghi và hệ thống phân cấp đồng thuận để xếp hạng sức mạnh của các đối tượng chia sẻ.

Core questions

• Các đảm bảo về phân phối và sắp xếp mà một kênh cung cấp là gì, và chúng ảnh hưởng đến thiết kế thuật toán như thế nào?
• Liệu một trừu tượng bộ nhớ chia sẻ có thể được xây dựng một cách đáng tin cậy trên một mạng truyền thông điệp không đáng tin cậy không?
• Các đối tượng đồng bộ hóa khác nhau như thế nào về khả năng giải quyết vấn đề đồng thuận?

Key theories

Hệ thống phân cấp thanh ghi và đồng thuận

Các đối tượng chia sẻ được xếp hạng theo số đồng thuận của chúng—số lượng tiến trình tối đa mà chúng có thể giải quyết đồng thuận không chờ—đặt các thanh ghi đọc/ghi đơn giản ở dưới cùng và các đối tượng phổ quát như so sánh-và-hoán đổi ở trên cùng.

Các cấu trúc thanh ghi

Hệ thống phân cấp thanh ghi an toàn, thông thường và nguyên tử của Lamport, và các cấu trúc xây dựng các thanh ghi mạnh hơn từ các thanh ghi yếu hơn, chính thức hóa chính xác ý nghĩa của việc đọc và ghi đồng thời hoạt động đúng đắn.

Mô phỏng bộ nhớ chia sẻ qua truyền thông điệp

Các thanh ghi nguyên tử một người ghi và nhiều người ghi có thể được mô phỏng trên một mạng truyền thông điệp không đồng bộ chịu được một số lỗi sập thiểu số bằng cách sử dụng các kỹ thuật quorum, thống nhất hai mô hình giao tiếp.

Clinical relevance

Sự phân biệt truyền thông điệp/bộ nhớ chia sẻ ánh xạ trực tiếp lên các nền tảng thực tế: các cụm và đám mây là các hệ thống truyền thông điệp, các máy chủ đa lõi cung cấp bộ nhớ chia sẻ, và các kho dữ liệu khóa-giá trị phân tán thực sự trình bày một trừu tượng thanh ghi chia sẻ trên một mạng truyền thông điệp.

History

Các bài báo năm 1986 của Lamport đã chính thức hóa các thanh ghi đồng thời; hệ thống phân cấp không chờ của Herlihy năm 1991 đã xếp hạng các nguyên thủy đồng bộ hóa theo số đồng thuận; và văn bản của Attiya và Welch đã củng cố các mô phỏng liên quan đến truyền thông điệp và bộ nhớ chia sẻ, thiết lập tính đối ngẫu là cốt lõi của lĩnh vực này.

Key figures

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

Seminal works

• herlihy2008
• attiya2004
• lamport1986

Frequently asked questions

Truyền thông điệp và bộ nhớ chia sẻ có tương đương nhau không?

Chúng tương đương về sức mạnh tính toán dưới các giả định lỗi phù hợp—mỗi cái có thể mô phỏng cái kia—nhưng chúng khác biệt rõ rệt về sự tiện lợi trong lập trình và hiệu suất, đó là lý do tại sao các hệ thống chọn một trong số chúng làm mô hình gốc của mình.