Tiểu luận Hệ Phân Tán Vấn đề nhiều bản sao trong điều kiện số lượng cập nhật lớn
GVHD: PGS.TS. Lê V
ăn Sơn
Trang 5
HVTH: Lê Quốc Dũng -KHMT K16
Định nghĩa dữ liệu tại mỗi vị trí : tại mỗi phút phải xây dựng lược đồ dữ liệu cục bộ
LIS (local Internal Schema)
Mô tả cấu trúc logic toàn cục: Lược đồ khái niệm toàn cục GCS(Global Conceptual
Schema)
Mô tả cấu trúc logic tại mỗi vị trí , điều nảy xảy ra do nhân bản và phân mảnh , gọi là
lược đồ khái niệm cục bộ LCS (Local Conceptual Schema)
Mô tả cấu trúc dữ liệu của các ứng dụng gọi là lược đồ ngoại giới ES (External
Schema)
Cấu trúc hệ thống bao gồm hai thành phần chính : Bộ tiếp nhận người dùng (User Processor) và bộ
phận xử lý dữ liệu (Data Processor).Hai modul này được đặt chung trên mỗi máy chứ không tách biệt
như hệ thống khách đại lý .
Các chức năng cơ bản của từng modul như sau :
User Interface Handler – Giao tiếp người sử dụng : Diễn dịch yêu cầu , định dạng kết
quả .
Semantic Data Controler – Kiểm soát dữ liệu ngữ nghĩa. Dựa vào lược đồ khái niệm
toàn cục để kiểm tra câu truy vấn tin có thực hiện được hay không
Global Query Optimizer – Tối ưu hóa câu hỏi toàn cục : Định ra chiến lược thực thi tốt
nhất trên các nút .
Global Execution Monitor – Điều khiển thực thi câu truy vấn toàn cục .
Local Query Processor – Xử lý câu truy vấn cục bộ .
Local Recovery Manager – Quản lý khôi phục cục bộ : Quản lý sự nhất quán khi có sự
cố
Run-time Support Processor – Bộ hận hỗ trợ thực thi : Quản lý truy xuất cơ sở dữ liệu.
Tiểu luận Hệ Phân Tán Vấn đề nhiều bản sao trong điều kiện số lượng cập nhật lớn
GVHD: PGS.TS. Lê V
ăn Sơn
Trang 6
HVTH: Lê Quốc Dũng -KHMT K16
2.3.Mô hình tương tác trong hệ phân tán:
Thực hiện truyền thông:
Sự tiềm ẩn (Latency):
•
Sự trì hoãn lan truyền: thời gian cần thiết để một bit đầu tiên của một thông điệp truyền
đến được đích.
•
Sự trì hoãn truyền: là khoảng thời gian giữa sự truyền bit đầu tiên và bit sau cùng của
một thông điệp.
•
Sự trì hoãn xử lý: là thời gian cần để hệ điều hành xử lý/gữi/nhận thông điệp.
Tiểu luận Hệ Phân Tán Vấn đề nhiều bản sao trong điều kiện số lượng cập nhật lớn
GVHD: PGS.TS. Lê V
ăn Sơn
Trang 7
HVTH: Lê Quốc Dũng -KHMT K16
•
Sự trì hoãn xếp hàng: thời gian cần để một thông điệp xếp hàng ở cuối máy chủ hoặc ở
các node trung gian đợi để truyền đi.
Băng thông (bandwidth): Tổng số thông tin có thể được truyền đi trong một thời gian đã
cho.
Sự biến đống tạp (Jitter): thời gian khác nhau giữa các sự trì hoãn ảnh hưởng bởi các
thông điệp khác nhau.
Đồng hồ và thứ tự các sự kiện:
Không có khái niệm toàn cục của thời gian.
Nhịp độ đồng hồ trôi: nhịp độ tương đối ở một đồng hồ máy tính trôi dạt ra khỏi từ một
đồng hồ tham chiếu hoàn hảo.
Đồng bộ hóa đồng hồ:
Hệ thống định vị toàn cầu (GPS): một ít máy tính có thể sử dụng máy thu radio để nhận
thời gian đọc từ GPS với độ chính xác là 1 micro-giây. Chúng có thể gữi các thông điệp thời
gian đến các máy tính khác trong mạng tương ứng của chúng.
Các đồng hồ logic: mỗi thông điệp là thời gian đóng dấu lên với một số nối tiếp mà phản
chiếu thứ tự lôgic của chúng.
Tiểu luận Hệ Phân Tán Vấn đề nhiều bản sao trong điều kiện số lượng cập nhật lớn
GVHD: PGS.TS. Lê V
ăn Sơn
Trang 8
HVTH: Lê Quốc Dũng -KHMT K16
CHƯƠNG II: GIẢI QUYẾT VẤN ĐỀ NHIỀU BẢN SAO
I.Đặt vấn đề
Tại sao sử dụng bản sao? Có hai lý do sau đây:
- Tăng độ tin cậy và tính sẵn sàng của hệ thống: khi dữ liệu bị lỗi hay vì một nguyên nhân
nào đó mà không thể dùng được, ta có thể dùng ngay bản sao dữ liệu đó để hệ thống không
phải dừng lại và tránh được tình trạng sử dụng các dữ liệu không chính xác.
- Tăng hiệu năng của hệ thống: có thể tăng quy mô hệ thống cả về số lượng lẫn phạm vi địa
lý.
Tuy nhiên việc sử dụng nhân bản cũng phải trả giá, đó là tính nhất quán dữ liệu của hệ thống bị
suy giảm. Do sử dụng bản sao nên có thể xảy ra trường hợp có sự thay đổi trên một dữ liệu mà
không cập nhật trên các bản sao của nó. Điều này sẽ gây ra các sai sót trong hệ thống. Do đó phải
tốn nhiều công sức để xây dựng các mô hình đảm bảo tính nhất quán của dữ liệu.
II.Các mô hình nhất quán lấy dữ liệu làm trung tâm
1. Mô hình nhất quán chặt
Thao tác đọc bất kỳ trên mục dữ liệu x đều trả về một giá trị tương ứng với kết quả của thao
tác ghi gần nhất trên x đó. Mô hình này khó áp dụng cho hệ phân tán.
2. Mô hình nhất quán tuần tự và mô hình nhất quán tuyến tính
Mô hình nhất quán tuần tự
Là mô hình lỏng lẻo hơn, yếu hơn mô hình nhất quán chặt. Kết quả của sự thực hiện
bất kỳ là như nhau nếu thao tác đọc và ghi do các tiến trình thực hiện trên mục dữ liệu một
cách tuần tự và các thao tác của mỗi tiến trình xuất hiện trong chuỗi thao tác này chỉ ra bởi
chương trình của nó
Mô hình nhất quán tuyến tính
Là mô hình yếu hơn mô hình nhất quán chặt nhưng mạnh hơn mô hình nhất quán tuần
tự. Kết quả của bất kì sự thực hiện nào là như nhau nếu các thao tác (đọc và ghi) của tất cả
các tiến trình lên dữ liệu được thực hiện môt cách tuần tự và các thao tác của mỗi tiến trình
xuất hiện trong chuỗi thao tác này phải theo thứ tự đã được chỉ ra trong chương trình của nó.
Thêm vào đó, nếu ts
op1
(x) < ts
op2
(y) thì thao tác op1(x) phải được thực hiện trước op2(y)
trong chuỗi thao tác.
3. Mô hình nhất quán nhân quả
Nếu sự kiện b được gây ra hoặc bị tác động bởi một sự kiện a xảy ra sớm hơn thì tính nhân
quả đòi hỏi mọi thực thể khác phải “nhìn” thấy a trước rồi mới thấy b sau. Các thao tác ghi có quan
hệ nhân quả tiềm năng phải được nhận biết bởi tất cả các tiến trình khác trong cùng một thứ tự. Các
thao tác ghi đồng thời có thể nhận biết được theo thứ tự khác nhau trên các máy khác nhau.
4. Mô hình nhất quán FIFO
Nhất quán FIFO còn được gọi là nhất quán PRAM. Đây là mô hình yếu nhất vì mô hình này
bỏ qua giới hạn về trật tự của bất kì thao tác đồng thời nào. Các thao tác ghi bởi một tiến trình đơn
phải được tất cả các tiến trình khác nhìn thấy theo cùng một trật tự mà chúng đề ra. Nhưng thao tác
Tiểu luận Hệ Phân Tán Vấn đề nhiều bản sao trong điều kiện số lượng cập nhật lớn
GVHD: PGS.TS. Lê V
ăn Sơn
Trang 9
HVTH: Lê Quốc Dũng -KHMT K16
ghi bởi nhiều tiến trình khác nhau có thể được thấy theo những trật tự khác nhau bởi các tiến trình
khác nhau.
5. Mô hình nhất quán yếu
Mô hình nhất quán yếu không tập trung vào các thao tác trên dữ liệu như các mô hình trên mà
chúng quan tâm đến trật tự các nhóm lệnh bằng việc sử dụng các biến được đồng bộ.
- Việc truy cập đến một biến đồng bộ hóa được kết hợp với kho dữ liệu là một nhất quán tuần
tự.
- Không có thao tác nào lên các biến đồng bộ hóa được phép thực hiện cho đến khi tất cả các
thao tác ghi trước đó được hoàn thành ở mọi nơi.
- Không có thao tác đọc hay ghi dữ liệu lên các mục dữ liệu nào được phép thực hiện cho đến
khi tất cả các thao tác trước đó lên các biến đồng bộ hóa được thực hiện.
6. Mô hình nhất quán đi ra
- Trước khi thực hiện một thao tác đọc hay ghi lên dữ liệu chia sẻ thì tất cả các thao tác
acquire do tiến trình này thực hiện trước đó phải hoàn tất.
- Trước khi một thao tác release được phép thực hiện thì tất cả các thao tác đọc và ghi do tiến
trình này thực hiện trước đó phải được hoàn tất.
- Truy cập vào các biến đồng bộ hóa là nhất quán FIFO (Không yêu cầu nhất quán tuần tự).
7. Mô hình nhất quán đi vào
Cũng giống mô hình nhất quán đi ra, mô hình nhất quán đi vào cũng sử dụng hai lệnh acquired
và release khi muốn sử dụng vào vùng tới hạn. Nhưng các lệnh này thao tác trên từng mục dữ liệu
của vùng dữ liệu chia sẻ. Tiến trình nào muốn sử dụng mục dữ liệu thì phải đợi cho tất cả các tiến
trình khác giải phóng mục dữ liệu đó.
- Một thao tác acquire để truy cập vào một biến đồng bộ hóa không được phép thực hiện
trong một tiến trình cho đến khi tất cả các cập nhật lên mục dữ liệu trong tiến trình đó được
thực hiện.
- Trước khi một truy cập trong chế độ dành riêng của một tiến trình tới một biến đồng bộ hóa
được phép thực hiện thì không tiến trình nào khác còn được giữ các biến đồng bộ hóa, trong
chế độ không dành riêng thì không cần yêu cầu như vậy.
- Sau khi một truy cập trong chế độ dành riêng lên một biến đồng bộ hóa được thực hiện thì
bất kì sự truy cập của tiến trình nào khác trong chế độ không dành riêng lên biến đó cũng
không được thực hiện cho đến khi chủ nhân của biến đồng bộ thực hiện xong việc truy cập
của mình.
III. Các mô hình nhất quán lấy client làm trung tâm
1. Nhất quán cuối cùng
Khi một dữ liệu có nhiều bản sao thì yêu cầu đưa ra là sau các thao tác cập nhật thì tất cả các
bản sao cuối cùng là phải bằng nhau Phải luôn đảm bảo rằng ngay cả khi client thay đổi về vị trí
vật lý thì việc sử dụng các bản sao cũng phải chính xác. Tức là các bản sao luôn luôn là nhất quán.
2. Nhất quán đọc đều
Một tiến trình thực hiện thao tác đọc trên một mục dữ liệu thì phải đảm bảo bất kì thao tác
đọc nào cũng đều cho cùng một kết quả hay kết quả gần đây nhất. Client sẽ luôn nhìn thấy những dữ
Tiểu luận Hệ Phân Tán Vấn đề nhiều bản sao trong điều kiện số lượng cập nhật lớn
GVHD: PGS.TS. Lê V
ăn Sơn
Trang 10
HVTH: Lê Quốc Dũng -KHMT K16
liệu mới hơn và không bao giờ phải nhìn thấy những dữ liệu cũ hơn những gì mà mình đã đọc trước
đó.
3. Nhất quán ghi đều
Thao tác ghi trên mục dữ liệu x của một tiến trình phải được hoàn thành trước bất kỳ một
thao tác ghi nào khác trên x bởi cùng một tiến trình.
4. Nhất quán đọc thao tác ghi
Tác động của một thao tác ghi của một tiến trình lên mục dữ liệu x sẽ luôn được nhìn thấy
bởi một thao tác đọc lần lượt trên x của cùng tiến trình đó.
5. Nhất quán ghi theo sau đọc
Tác động bởi một thao tác ghi của một tiến trình lên mục dữ liệu x sẽ luôn được nhìn thấy bởi
một thao tác đọc liên tiếp lên x của cùng tiến trình đó.
IV. Các giao thức phân phối
1. Phân loại bản sao
Có 3 loại bản sao:
Các bản sao thường trực:
Trong tiến trình hay trên máy luôn có một bản sao. Số lượng các bản sao thường xuyên
này rất ít, thường được tập hợp lại thành nhóm các máy trạm (COWs) hoặc trong các hệ
thống phản chiếu (mirrored), thường là các Web server hay là các server có chứa cơ sở dữ
liệu dự phòng.
Bản sao khởi đầu từ server:
Các bản sao này được sử dụng để làm tăng hiệu năng. Các bản sao này được xếp đặt
động dựa vào yêu cầu của server khác. Một ví dụ điển hình là chúng được các công ty web
hosting sử dụng để định vị vị trí địa lý của các bản sao gần nhất khi họ cần.
Các bản sao khởi đầu từ client:
Các bản sao này được tạo ra từ yêu cầu của client, chẳng hạn như việc cache dữ liệu của
một trình duyệt. Chúng được xếp đặt động dựa vào yêu cầu của client.
2. Lan truyền cập nhật
Có 3 cách lan truyền các cập nhật:
Chỉ thông báo là có cập nhật:
Thường dùng trong việc cache dữ liệu.Thông báo về việc mất hiệu lực của một giao
thức.Phương pháp này tốt khi tỉ lệ các thao tác đọc so với thao tác ghi nhỏ.
Truyền dữ liệu cập nhật từ bản sao này tới một bản sao khác.
Thực hiện tốt khi có nhiều thao tác đọc. Ghi lại các thay đổi và tập hợp các cập nhật lại
để truyền đi (chỉ truyền đi các thay đổi chứ không truyền cả dữ liệu đã bị thay đổi, vì thế tiết
kiệm được băng thông).
Lan truyền các thao tác cập nhật tới các bản sao khác (nhân bản chủ động).
Tốn ít băng thông nhưng đòi hỏi năng lực xử lý cao vì trong nhiều trường hợp thì các
thao tác là rất phức tạp.
Tiểu luận Hệ Phân Tán Vấn đề nhiều bản sao trong điều kiện số lượng cập nhật lớn
GVHD: PGS.TS. Lê V
ăn Sơn
Trang 11
HVTH: Lê Quốc Dũng -KHMT K16
Hai các tiếp cận lan truyền cập nhật:
Đẩy cập nhật: là giao thức do server khởi tạo, trong giao thức này các cập nhật được lan
truyền mỗi khi có một server khác yêu cầu.
Kéo cập nhật: là giao thức do client khởi tạo khi client muốn được cập nhật.
V. Phân tích vấn đề
Hệ tin học phân tán hay nói ngắn gọn là hệ phân tán là hệ thống xử lý thông tin bao gồm
nhiều bộ xử lý hoặc bộ vi xử lý nằm tại các vị trí khác nhau và được liên kết với nhau thông qua hệ
thống viễn thông dưới sự điều hành thống nhất của một hệ điều hành.
Hệ phân tán được xây dựng nhằm mục đích phân tán hoá các quá trình xử lý thông tin và
thực hiện công việc đó trên các trạm xa nhau. Đó là những cơ sở căn bản cho việc xây dựng các ứng
dụng lớn như thương mại điện tử, giáo dục điện tử, thư viện điện tử số, xây dựng các cơ sở dữ liệu
tìm kiếm…
Thời gian truy cập trung bình vào thông tin trong hệ phân tán có thể được rút ngắn, nhờ vào
phương pháp nhân nhiều bản và được gọi là nhiều bản sao của một đối tượng thông tin.
Trong các hệ loại này, từng hệ thống cục bộ đều có lưu trữ một bản sao của tất cả các thông
tin liên quan đang có ở tất cả các hệ cục bộ.
Ưu điểm nổi bậc của kiểu tổ chức này là:
1. Dễ dàng thực hiện việc truy cập thông tin cần thiết cho các yêu cầu ngay tại hệ thống
cục bộ của mình.
2. Cho kết quả truy cập một cách nhanh chóng.
Tuy nhiên, kiểu truy vấn này chỉ cho kết quả tương đối chính xác và phụ thuộc rất nhiều vào
phương pháp và thời hạn cập nhật thông tin trong các cơ sở dữ liệu cục bộ.
Sự tồn tại nhiều bản sao trong hệ phân tán có thể dẫn đến các hệ quả sau :
1. Cập nhật thông tin diễn (gần hoặc xa) hoặc sự thay đổi thông tin cục bộ trên một hệ
cục bộ nào đó cần phải được tiến hành cho tất cả các hệ thống cục bộ và không được
phép bỏ sót hệ nào cả. Trong khoảng thời gian làm tươi thông tin phải đảm bảo sao
cho việc truy vấn dữ liệu cho kết quả kịp thời hoặc đặt truy vấn trong trạng thái treo.
2. Cần phải tránh trường hợp các thao tác trên hai bản sao khác nhau nhưng chứa cùng
thông tin được truy cập bởi hai hay nhiều yêu cầu dẫn đến không gắn bó . Ví dụ : một
mặt hàng nào đó đã cung cấp cho khách hàng rồi thì không được phép cung cấp cho
khách hàng tiếp theo nữa.
Hai vấn đề vừa nêu trên xác định về các ràng buộc đối với đề gắn bó dữ liệu . Nhằm đảm bảo
sự gắn bó này điều kiện đủ là bắt buộc tuân thủ trình tự nào đó cho tất cả các bản sao, các cập nhật
thông tin.
Biện pháp hàng đầu là áp dụng cơ chế then cài nhằm thực hiện việc loại trừ tương hỗ tổng
quát trên tập hợp các bản sao, biện pháp này có mặt hạn chế là không cho phép các chương trình
thực hiện song song.
Một biện pháp khác là cho phép thực hiện các giao dịch trên tất cả các bản sao và thực hiện
cùng một trình tự cho mỗi hệ thống cục bộ. Khó khăn trong việc triển khai trình tự tổng quát có thể
Tiểu luận Hệ Phân Tán Vấn đề nhiều bản sao trong điều kiện số lượng cập nhật lớn
GVHD: PGS.TS. Lê V
ăn Sơn
Trang 12
HVTH: Lê Quốc Dũng -KHMT K16
so sánh với khó khăn của biện pháp đầu tiên đã nêu, nhưng lại cho phép các chương trình hoạt động
song song.
Trong môi trường phân tán, sơ đồ vị trí của các bản sao và việc cập nhật chúng có thể mô tả
trong hình vẽ sau đây.
Các bản sao có thể đặt trên các server S
1
, S
2
, .,S
n
trên các tập tin hay vùng nhớ đặc biệt e
ij
, i=1 n,
j=1 m, trong đó i chỉ server, j chỉ bản sao, n là số lượng server được mắc nối trong mạng, m là số
lượng các bản sao cần phải cập nhật. Mỗi server có thể quản lý một mạng con. Ngoài ra, các bản sao
có thể được bố trí trên các trạm thể hiện bằng các t
k
, k=1 q, k là trạm và q là số trạm được mắc nối.
Nếu ta có n bản sao của đối tượng e nào đó, thì ràng buộc toàn vẹn phải là:
Trên bản sao của 1 đối tượng
e
1
=e
2
=e
3
= .=e
n
Trên các bản sao của toàn bộ các đối tượng
e
11
=e
21
= .=e
n1
e
12
=e
22
= .=e
n2
.
e
1m
=e
2m
= .=e
nm
Để tham chiếu đến đối tượng e, cần thực hiện giao dịch sau (áp dụng thuật toán then cài):
Để thực hiện việc cập nhật vào các bản sao , ta cần phải cài then chúng như sau (áp dụng
thuật toán then cài):
V_doc(
e
i
)
Doc(
e
i
)
Giai_phong(
e
i
)
Để cho i:=1 đến n thực hiện V_viet(
e
i
)
< thực hiện các cập nhật và chép lại chúng vào
tất cả các bản >
Để cho i:=1 đến n thực hiện Giai_phong(
e
i
)
Tiểu luận Hệ Phân Tán Vấn đề nhiều bản sao trong điều kiện số lượng cập nhật lớn
GVHD: PGS.TS. Lê V
ăn Sơn
Trang 13
HVTH: Lê Quốc Dũng -KHMT K16
Để tránh bế tắc diễn ra, việc cài then các bản sao luôn luôn phải được thực hiện trong cùng
một trật tự.
Nói cách khác, hoặc là đối tượng đang trong quá trình cập nhật và tất cả các bản sao của nó
được dự trữ cho tiến trình thực hiện cập nhật, hoặc là tất cả các bản sao được truy cập chỉ để đọc và
giống nhau hoàn toàn.
Gọi M là cực đại của các cập nhật có thể diễn ra đồng thời, thì M có thể tính theo công thức
M=n x m.
Căn cứ vào nội dung thông tin cần phải đảm bảo sự gắn bó mà người ta chia ra hai loại giải
thuật:
• Giải thuật toán gắn bó mạnh
• Giải thuật toán gắn bó yếu.
Hệ thống viễn thông là đối tượng có thể diễn ra các sự cố kỹ thuật và ùn tắt đường truyền, ta
có số lần truy cập bản sao trên thực tế sẽ lớn hơn M rất nhiều; hiệu năng hoạt động của hệ trong
trường hợp này sẽ bị giảm.
Một trong những giải pháp khắc phục vấn đề vừa nêu là áp dụng kỹ thuật đánh dấu bản điều
khiển và căn cứ vào hệ thống tín hiệu này, người ta có thể chọn các giải thuật cập nhật thích hợp, rút
ngắn được tốc độ cập nhật bình quân.
Tiểu luận Hệ Phân Tán Vấn đề nhiều bản sao trong điều kiện số lượng cập nhật lớn
GVHD: PGS.TS. Lê V
ăn Sơn
Trang 14
HVTH: Lê Quốc Dũng -KHMT K16
CHƯƠNG III: MỘT SỐ THUẬT TOÁN QUẢN LÝ NHIỀU BẢN SAO
I.Thuật toán đảm bảo sự gắn bó yếu nhờ dấu
1.Nguyên lý
Tập hợp các yêu cầu cập nhật được sắp xếp theo cùng một kiểu trên tất cả các trạm nhờ cơ
chế dấu. Theo đó mỗi một yêu cầu được phát đi cho tập hợp các trạm. Trên mỗi trạm, tồn tại một
tiến trình Server đảm nhận nhiệm vụ tiếp nhận các yêu cầu theo trật tự của dấu. Điều đó cho phép có
được một sự gắn bó yếu giữa các bản sao.
2.Triển khai hệ ổn định
Các giao dịch cần xét là các khả năng đọc, ghi hay cập nhật. Cập nhật được xác định như là
một dãy các thao tác đọc và ghi, thao tác kiểm tra đọc tức thì trạng thái hiện hành của một bản sao.
Mỗi một server tiếp nhận các yêu cầu ghi đến từ trạm cục bộ ở thời điểm cho trước. Nó tiếp
nhận các yêu cầu và tính toán trên cơ sở dấu theo tiêu chí lâu nhất.
Khi trạm i truyền các thông điệp cho trạm j, Trật tự nhận các thông điệp tại j là hoàn toàn
giống với trật tự của các thông điệp phát đi. Giả thiết này được kiểm tra trong các mạng thông
thường. Việc xác định các yêu cầu cần xử lý trên một trạm là hoàn toàn có thể .
Có 2 trường hợp cần xem xét:
STT Trường hợp
1
Tập hợp các yêu cầu ghi khi chờ chứa các yêu cầu từ tất cả các trạm khác. Trong
trường hợp này các yêu cầu đi qua, nếu chúng tồn tại, là mới hơn so với các yêu cầu đã
đi qua. Nói cách khác, yêu cầu lâu nhất chính là yêu cầu đang chờ.
2
Tồn tại các trạm mà không có bất kỳ yêu cầu nào được truyền đến. Ta được đưa các
trường hợp trước đây bằng cách truyền cho tất cả các trạm một thông điệp yêu cầu và
bắt buột phải xác nhận. Do vây, sau một khoảng thời gian, theo giả thiết về độ ổn định,
ta sẽ nhận hoặc là các yêu cầu đi qua, hoặc là các trả lời cho thông điệp yêu cầu. Lúc
này, ta có được các thông điệp đến từ tất cả các trạm.
3. Các hành vi ngoài chế độ bình thường
Hai vấn đề mở rộng hơn đối với thuật toán này cho phép rút ra hay chen vàotùy ý một trạm
nào đó. Ngược lại, thuật toán chỉ sống trong trường hợp có sự cố, nếu các điều kiện sau đây được
tôn trọng:
STT Điều kiện
1 Việc đột nhiên biến mất đi một trạm nào đó phải được các trạm khác nhận biết tự động.
2
Việc phát một thông điệp là một phép toán không chia cắt được nữa. Đó là một thông
điệp hoặc là tất cả đều phải nhận được hoặc là không trạm nào nhận được cả.
Không có nhận xét nào:
Đăng nhận xét