Tiểu luận: Hệ phân tán GVHD: PGS-TS. Lê Văn Sơn
BỘ GIÁO DỤC VÀ ĐÀO TẠO
ĐẠI HỌC ĐÀ NẴNG

TIỂU LUẬN
HỆ TIN HỌC PHÂN TÁN
Đề tài :
- VẤN ĐỀ GẮN BÓ DỮ LIỆU TRONG BÀI TOÁN BÃI ĐỖ XE
- SẮP XẾP CÁC MESSAGE DỰA TRÊN ĐỒNG HỒ LOGIC
GVHD: PGS-TS Lê Văn Sơn
Học viên: Nguyễn Đình Lâm Khánh
Khóa 2012 - 2014
Đà Nẵng – 8/2014
Học viên: Nguyễn Đình Lâm Khánh Trang 1
Tiểu luận: Hệ phân tán GVHD: PGS-TS. Lê Văn Sơn
LỜI MỞ ĐẦU
Cùng với sự phát triển ngày càng cao của công nghệ thông tin. Sự ra đời và phát
triển ồ ạt của máy vi tính và các phương tiện xử lý thông tin khác, cũng như nhu cầu trao
đổi thông tin trong mọi hoạt động xã hội loài người. Đòi hỏi sự phát triển đồng bộ các
phương pháp truyền thông. Mạng máy tính ra đời làm cho mọi người trên thế giới trở nên
gần nhau hơn. Hệ tin học phân tán ra đời nhằm phát triển nhu cầu của công nghệ thông
tin .
Hệ tin học phân tán hay nói ngắn gọn là hệ phân tán (Distributed System) 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 phương tiện viễn thông dưới sự điều khiển
thống nhất của một hệ điều hành.
Để đảm bảo tính gắn bó của hệ, yêu cầu đặt ra trước hết là đồng bộ hóa các tiến
trình. Trình tự và đồng bộ các tiến trình trong hệ phân tán chỉ ra cho ta các vấn đề đồng
bộ có thể sẽ dẫn đến phải thiết chế một trật tự tổng quát của các sự kiện diễn ra trong hệ.
Cần phải xác định mối liên hệ trao đổi thông qua các thông điệp với thời gian truyền khác
nhau, những thông tin tạm thời trao đổi không có giá trị tuyệt đối và trình tự tổng quát

Người sử dụng là một khái niệm được hiểu theo nghĩa rộng, dưới góc độ hệ điều
hành. Đó có thể là các nhà chuyên môn, các máy tính, các hệ tự động vận hành gắn với
máy tính. . . đang khai thác hệ thống qua các lệnh điều khiển theo một thuật toán nào đó
nhằm đạt được mục tiêu xác định từ trước.
Hệ điều hành các máy tính và mạng máy tính được đặt sát phần cứng. Nó gắn kết chặt
chẽ với thiết bị bởi một hệ thống các chương trình điều khiển và sắp xếp nhằm khai thác
phần cứng phục vụ cho các chương trình ứng dụng khác nhau với kết quả và hiệu năng
chấp nhận được.
Học viên: Nguyễn Đình Lâm Khánh Trang 3
II III

I
HỆ ĐIỀU HÀNH
PHẦN
CỨNG
Tiểu luận: Hệ phân tán GVHD: PGS-TS. Lê Văn Sơn
Như vậy, xét về mặt quản lý - điều hành các hoạt động của hệ thống thì các thực thể
vừa nêu trên bao gồm phần cứng, phần mềm và dữ liệu. Là những đối tượng mà hệ điều
hành phải quan tâm. Những đối tượng này chính là thực thể cơ bản của hệ tin học và
được mô tả hình 1.2
Hình 1.2 Ba thực thể của hệ tin học
Như vậy, hệ thống tin học là một hệ thống bao gồm hai phần cơ bản là phần cứng và
phần mềm gắn bó hữu cơ với nhau và có khả năng xử lý thông tin.
1.2. HỆ TẬP TRUNG
Tiêu biểu là hệ thống máy đơn, là máy không kết nối vật lý và logic với các máy khác
như hình vẽ sau:
Hình 1.3 Hệ thống máy đơn
Ở một thời điểm nhất định, máy đơn được điều hành bởi một hệ điều hành duy nhất.
Hệ thống như vậy được gọi là hệ tin học tập trung, thích hợp với các máy tính loại trung
và loại lớn.

dựng các ứng dụng lớn như thương mại điện tử, giáo dục điện tử, chính phủ điện tử, thư
viện điện tử, . . .
Hiện nay, đứng trên những phương diện khác nhau, có thể có các định nghĩa khác
nhau về hệ tin học phân tán, nhưng phổ biến hơn cả là định nghĩa sau:
Hệ tin học phân tán (hệ phân tán) là hệ thống xử lý thông tin bao gồm nhiều bộ xử lý
hay 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 phương tiện
viễn thông dưới sự điều khiển thống nhất của một hệ điều hành.
Từ định nghĩa trên, hệ phân tán có các ưu điểm căn bản so với hệ tập trung, như sau:
- Tăng tốc độ bình quân trong tính toán, xử lý.
- Cải thiện tình trạng luôn sẵn sàng của các loại tài nguyên.
- Tăng độ an toàn cho dữ liệu.
- Đa dạng hoá các loại hình dịch vụ tin học.
- Đảm báo tính toàn vẹn của thông tin.
Học viên: Nguyễn Đình Lâm Khánh Trang 5
Phần
cứng
Phần
mềm
Dữ
liệu
Truyề
n
thông
Tiểu luận: Hệ phân tán GVHD: PGS-TS. Lê Văn Sơn
CHƯƠNG 2
PHƯƠNG PHÁP ĐẢM BẢO GẮN BÓ DỮ LIỆU
2.1. ĐẶT VẤN ĐỀ
Vấn đề gắn bó dữ liệu trong các hệ thống phân tán nói chung và các hệ thống
thông tin đăng ký trên mạng nói riêng như việc đăng ký các tour du lịch, mua bán
trong các giao dịch thương mại điện tử, đăng ký giữ chỗ trong giao thông vận tải,

Tiểu luận: Hệ phân tán GVHD: PGS-TS. Lê Văn Sơn
Một cơ sở dữ liệu nào đó được gọi là gắn bó, nếu nó thỏa mãn một tập các
ràng buộc về toàn vẹn ngữ nghĩa. Để đảm bảo tính gắn bó dữ liệu nhiều cơ chế
khác nhau như điều khiển hoạt động đồng thời [5], kiểm soát tính toàn vẹn ngữ
nghĩa, …được sử dụng [4].
Việc kiểm soát tính toàn vẹn ngữ nghĩa tốt sẽ đảm bảo được tính gắn bó dữ
liệu của hệ thống thông tin. Hiện nay, người ta đang áp dụng hai phương pháp chủ
yếu :
1. Loại bỏ các chương trình/thủ tục cập nhật có thể dẫn đến trạng thái
không gắn bó dữ liệu trong các cơ sở dữ liệu [CKP
1
]
2. Triệu gọi các chương trình/thủ tục đặc biệt đã được cài đặt trên hệ thống
nhằm khôi phục trạng thái ban đầu trước khi cập nhật [CKP
2
].
Các ràng buộc toàn vẹn được phân làm hai loại chủ yếu :
1. Ràng buộc cấu trúc (Structural Constraint) diễn tả những đặc tính ngữ
nghĩa cơ bản vốn có trong mô hình. Ví dụ như ràng buộc thể hiện bằng khóa duy
nhất trong mô hình quan hệ hoặc các liên kết theo kiểu 1 – n, (n > 1) giữa các đối
tượng trong mô hình mạng
2. Ràng buộc hành vi (Behavioral Constraint) nhằm điều hòa các hoạt động
của các ứng dụng.
Trong quá trình nghiên cứu bài toán, các tác giả vận dụng phương pháp tổng
quát đảm bảo gắn bó dữ liệu và các ràng buộc toàn vẹn thông tin phục vụ công tác
phân tích, thiết kế hệ quản trị cơ sở dữ liệu cho hệ thống cơ sở dữ liệu đăng ký với
thông tin gắn bó trong điều kiện phân tán. Những thông tin chi tiết có thể tham
khảo trong tài liệu [7].
Để có thể khôi phục lại dữ liệu và trạng thái gắn bó thông tin của toàn hệ
thống khi có sự cố diễn ra, một trong những vấn đề quan trọng hàng đầu là cần

hành hệ thống. Lỗi này có thể bắt nguồn
từ phần thiết bị như bộ xử lý/bộ vi xử
lý, bộ nhớ, các thiết bị ngoại vi, bị sự
cố. Khi bị sự cố, hệ thống lập tức bị
ngừng hoạt động. Hệ thống chương
trình, đặc biệt là các chương trình điều
khiển cũng có thể sinh lỗi. Đó là các lỗi
do thuật toán, do lệnh viết sai, do phần
lưu trữ chương trình hay do virus. Các
lỗi này thường là ở các chương trình và
cơ sở dữ liệu
3
Sự cố phương tiện
Media Failure
Do sự cố của các thiết bị lưu trữ thứ cấp
dùng để lưu cơ sở dữ liệu. Khi có sự cố
này thì một phần hoặc tất cả cơ sở dữ
liệu trên thiết bị đó được xem như bị
hủy hoại hoặc không thể truy cập một
cách bình thường được
4
Sự cố
đường truyền
Transmission
Failure
Do lỗi trong các thông điệp, các thông
điệp vô trật tự, thông điệp bị thất lạc
hoặc không phân phối thông điệp và sự
cố khác liên quan đến đường truyền.
Phương pháp tổng quát cho việc khắc phục bốn loại sự cố này được trình bày

BÓ DỮ LIỆU
Để dễ dàng mô tả các giải thuật đảm bảo gắn bó dữ liệu phân tán, chúng ta
giả thiết rằng, tại vị trí nguồn của giao dịch một tiến trình thực hiện các thao tác
của nó, tiến trình này được gọi là điều phối viên (Coordinator). Điều phối viên trao
đổi với các thành viên (Participant) tại những vị trí có tham gia vào việc thực hiện
các thao tác của giao dịch.
Cải tiến giải thuật hai pha tuyến tính ( Linear 2PC ) [4], giải thuật MAONT
[1], ta thiết kế giải thuật mà trong đó các thành viên có thể trao đổi với nhau.
Có một thứ tự giữa các vị trí trong hệ thống dành cho việc giao tiếp. Chúng ta
hãy giả thiết rằng thứ tự giữa các vị trí có tham gia vào việc thực hiện một giao
dịch là 1, 2,…, N với điều phối viên là vị trí đầu tiên trong thứ tự này (Giải thuật
được minh họa bằng hình 1).
Theo mô hình trong hình vẽ, ta có các đối tượng sau :
1. C
1
, C
2
, , C
n
là các Client truy cập Web Server bằng trình duyệt Web
2. Servlets là các đối tượng xử lý yêu cầu được gửi từ các C
i
, i=1,n
Học viên: Nguyễn Đình Lâm Khánh Trang 9
Tiểu luận: Hệ phân tán GVHD: PGS-TS. Lê Văn Sơn
3. TPC-Server-App1, TPC-Server-App2, , TPC-Server-AppN là các RMI
Server cài đặt thuật toán 2PC tuyến tính (Linear Two Phase Commit - TPC)
4. TPCMonitorServer là một trình giám sát cho phép hiển thị quá trình dịch
chuyển của danh sách di chuyển [6] trong quá trình xử lý của các TPC-Server-
Appi, i = 1,N

danh sách và trả về kết quả là danh sách kết quả truy vấn của chính nó và các
Server đứng phía sau nó trong danh sách di chuyển.
public interface TPCApp extends Remote
{
public ResultQueryList queryApp(MovableList movableList,int index)
throws RemoteException;
}
Nếu quá trình xử lý tại bất kỳ một TPC-Server-App nào bị lỗi thì kết quả trả
về là null. Dựa vào kết quả trả về này, các TPC-Server-App commit hoặc rollback
transaction đang quản lý. Như vậy, khi TPC-Server-App đầu tiên nhận được danh
sách di chuyển, TPC-Server-App bắt đầu một transaction để thực hiện các câu
lệnh SQL truy vấn CSDL cục bộ thông qua kết nối CSDL được lấy từ
ConnectionPool cục bộ .Tiếp theo, TPC-Server-App tăng chỉ mục hiện tại của
danh sách di chuyển lên 1 và chuyển danh sách di chuyển này đến TPC-Server-
App kế tiếp. Quá trình này được lặp lại cho đến khi kết thúc danh sách di chuyển.
Tại Server cuối cùng trong danh sách di chuyển, nếu việc truy vấn CSDL cục bộ
thành công, TPC-Server-App commit transaction và trả về kết quả là
ResultQueryList khác null. Dựa vào kết quả trả về này, Server đứng trước trong
danh sách di chuyển sẽ commit hoặc rollback transaction cục bộ và trả về kết quả
cho Server liền trước. Khi Servlet nhận được kết quả là null có nghĩa là xử lý
không thành công. Ngược lại, Servlet sẽ tiếp tục xử lý kết quả nhận được để trả về
cho Client.
Các bước cơ bản của giải thuật đề xuất nhằm minh họa cho việc cải tiến giải
thuật MAONT và giải thuật hai pha tuyến tính được mô tả qua hình 2. Việc triển
khai xây dựng chương trình bằng ngôn ngữ lập trình Java cùng với thư viện RMI
và tiến hành thực nghiệm sau đó đã đạt được kết quả nhất định.
Học viên: Nguyễn Đình Lâm Khánh Trang 11
Tiểu luận: Hệ phân tán GVHD: PGS-TS. Lê Văn Sơn
Học viên: Nguyễn Đình Lâm Khánh Trang 12
Tiểu luận: Hệ phân tán GVHD: PGS-TS. Lê Văn Sơn

C
2
: Nếu A là phát thông điệp bởi một trạm nào đó và nếu B là thu của thông điệp
này thì ta có A → B.
3.3. GIẢ ĐỊNH CÁC ĐIỀU KIỆN CHUNG
Các hệ phân tán được xây dựng trên cơ sở các trạm làm việc được mắc nối với nhau
(nối mạng). Mỗi một trạm có bộ nhớ riêng của mình và tuyệt đối không có bộ nhớ chung.
Học viên: Nguyễn Đình Lâm Khánh Trang 13
Tiểu luận: Hệ phân tán GVHD: PGS-TS. Lê Văn Sơn
STT K.H Thuyết minh
1 H
1
Một trạm trong các trạm đều có thể liên lạc với các trạm còn lại
trong hệ
2 H
2
Không có lỗi truyền thông tin và không mất thông điệp
3 H
3
Trật tự nhận trên trạm j của dãy các thông điệp cũng giống như
chính tại trạm I là giống với trật tự của nơi phát
4 H
4
Sự cố hay gián đoạn vật lý tại một trạm nào đó được phát hiện sẽ
lập tức thông báo đến tất cả các trạm có ý định liên lạc với nó.
3.4. BÀI TOÁN QUẢN LÝ BÃI ĐỖ XEHình 1:
Tình huống thứ 1 :

BV
BV
BV
BV
Trong đó
BV - người bảo vệ có nhiệm vụ phân
phối chổ cho các xe ô tô.
VT - Vị trí cho từng xe ô tô cụ thể.
Trong bài toán
- Bãi đậu xe chính là tài nguyên
- Xe chính là các tiến trình
- Nếu một cửa là tập trung còn nhiều
của sẽ diến ra tranh chấp
Tiểu luận: Hệ phân tán GVHD: PGS-TS. Lê Văn Sơn
Nếu ta có bãi để xe có nhiều cổng vào và tại mỗi cổng có một người bảo vệ thì mỗi
người bảo vệ chỉ có thể biết được trạng thái với độ trễ nhất định và điều đó dẫn đến tình
huống thứ 2. Đó là tình huống có nhiều trung tâm ra quyết định như trong hình vẽ.
Trên thực tế một người bảo vệ nào đó tin rằng không còn chỗ trống nữa, trong khi
một người bảo vệ khác lại vừa mới cho ra khỏi bãi một số xe mà anh ta chưa kịp báo cho
các người bảo vệ khác. Cũng có thể diễn ra trường hợp là cùng một lúc các người bảo vệ
giải quyết các xe vào cùng một vị trí trong bãi do vì họ thiếu thông tin
3.5. GẮN BÓ DỮ LIỆU BÀI TOÁN QUẢN LÝ BÃI ĐỖ XE
Tình huống thứ 3 :
Giả sử rằng ở thời điểm cho trước ta có 4 ngưòi bảo vệ và có 100 chỗ còn trống. Tất
cả các người bảo vệ đều có thông tin đó. Trạng thái lúc này của hệ là gắn bó. Ba trong số
họ phát đi các thông tin sau :
STT Ký hiệu Thông tin phát đi
1 M1 Thêm 20 chỗ trống
2 M2 Đã có 10 chỗ bị chiếm
3 M3 Dành 10% chỗ trống để quét dọn sân bãi

M
1
M
2
M
2
M
2
M
3
M
3
M
3
Bảo vệ 4
Tiểu luận: Hệ phân tán GVHD: PGS-TS. Lê Văn Sơn
Trật tự
xử lý
Bảo vệ 1 Bảo vệ 2 Bảo vệ 3 Bảo vệ 4
Thông
điệp
Giá
Trị
Thông
điệp
Giá
Trị
Thông
điệp
Giá

Giá
Trị
Thông
điệp
Giá
Trị
Thông
điệp
Giá
Trị
100 100 100 100
1 M1 120 M2 90 M3 90 M1 120
2 M3 108 M3 81 M1 110 M2 110
3 M2 118 M1 101 M2 100 M3 99
Bảng 2: Sự không gắn bó giữa các bảo vệ
3.6. KẾT LUẬN
Trong bài toán hệ quản lý đổ xe việc không gắn bó dữ liệu luôn luôn xảy ra ở
các trạm nếu không có một cơ chế để thực hiện đồng bộ hoá các tiến trình (cho phép các
ô tô vào bãi đậu theo một trình tự). Khi thực hiện phân tán chức năng cung cấp trên nhiều
trạm khác nhau (các bảo vệ) sự hoạt động gắn bó với nhau giữa các chương trình cung
cấp là rất cần thiết để đảm bảo cho hoạt động cung cấp hoàn toàn chính xác. Trên cơ sở
phân tích bài toán ở trên chúng ta nhận thấy vấn đề không gắn bó dữ liệu trên các hệ phân
tán cần phải có cách giải quyết thích hợp. Phương pháp giải quyết vấn đề này được nêu
lên ở phần tiếp theo.
Học viên: Nguyễn Đình Lâm Khánh Trang 17
Bảo vệ 1
Bảo vệ 2 Bảo vệ 3 Bảo vệ 4
t
M
1

• Trong hệ thống không đồng bộ, thường không thể biết sự kiện nào xảy ra trước sự
kiện nào
• Một số ví dụ
– Ví dụ A
• p0 gửi thông báo m0 cho p1
• Trước khi m0 tới p1, p1 gửi thông báo m1 cho p0
• p0 và p1 không thể biết thông báo nào đã được gửi trước
– Ví dụ B
• p0 gửi thông báo m0 cho p1
• Sau khi m0 tới p1, p1 gửi thông báo m1 cho p0
• p0 và p1 biết m0 được gửi và nhận trước khi m1 được gửi
• Cần sắp xếp các sự kiện theo thứ tự bộ phận
4.1.3. Thứ tự bộ phận xảy ra trước
• Trong một thực hiện, sự kiện tính a xảy ra trước sự kiện tính b, ký hiệu a → b,
nếu
1. a và b xuất hiện trên cùng một bộ xử lý và a xảy ra trước b trong thực hiện trên
bộ xử lý đó, hoặc
Học viên: Nguyễn Đình Lâm Khánh Trang 18
Tiểu luận: Hệ phân tán GVHD: PGS-TS. Lê Văn Sơn
2. a gây ra việc gửi thông báo m và b bao hàm việc nhận thông báo m, hoặc
3. ∃ sự kiện tính c sao cho a → c và c → b
• Xảy ra trước có nghĩa là thông tin từ sự kiện a có thể ảnh hưởng đến sự kiện b
• Nếu trong hai sự kiện không có sự kiện nào xảy ra trước thì chúng tương tranh,
ký hiệu ║
4.1.4. Đồng hồ logic
• Khái niệm đồng hồ logic
– Là các giá trị gán cho các sự kiện tính để cung cấp thông tin về thứ tự xảy
ra của chúng
• Số nguyên L(e) gán cho sự kiện e trong một thực hiện thỏa mãn
điều kiện a → b ⇒ L(a) < L(b)

c d e f
g h i
1
2
1 2 3 4
1
2
5
Tiểu luận: Hệ phân tán GVHD: PGS-TS. Lê Văn Sơn
• Đồng hồ vector tổng quát hóa của đồng hồ logic
– Các giá trị được lấy từ một tập thứ tự bộ phận thay vì một tập thứ tự toàn
phần
• Khái niệm đồng hồ vector
– Là các giá trị gán cho các sự kiện để cung cấp các thông tin không nhân
quả và nhân quả giữa chúng
• Giá trị V(e), thuộc tập thứ tự bộ phận, gán cho sự kiện e trong một
thực hiện thỏa đáng thỏa mãn a → b ⇔ V(a) < V(b)
4.1.6. Giải thuật nhãn thời gian vector (vector timestamps)
• Mỗi bộ xử lý pi duy trì một vector Vi n chiều, có giá trị ban đầu là (0, , 0)
• Mọi thông báo pi gửi đi được gán nhãn thời gian giá trị hiện thời của Vi
• Với mỗi sự kiện tính a của pi
– Gán Vi[i] := Vi[i] + 1
– Với mỗi thông báo pi nhận được có nhãn thời gian T
• Cập nhật Vi[j] := max(T[j], Vi[j]) ∀ j ≠ i
– Nhãn thời gian vector V(a) = Vi(a) là giá trị của Vi khi sự kiện a kết thúc
4.1.6. So sánh nhãn thời gian vector
• Cho V1 và V2 là hai vector nguyên n chiều
• Bằng
– V1 = V2 ⇔ V1[i] = V2[i] ∀ i
– E.g. (3,2,4) = (3,2,4)

• Duyệt mảng store từ chỉ số nhỏ nhất đến chỉ số lớn nhất, giả lập lại các bước tính
• Ghi dấu các thông báo định gửi trong quá trình giả lập
• Ngừng giả lập khi tìm thấy m' gần nhất sao cho store[m'] có nhãn vector ≤ K
Giải pháp 1
Học viên: Nguyễn Đình Lâm Khánh Trang 21
Tiểu luận: Hệ phân tán GVHD: PGS-TS. Lê Văn Sơn
– Mỗi pi thực hiện
• pi gửi tới mỗi bộ xử lý kề cận pj số thông báo nhận được từ pj theo thông tin trong
store[m']
• pj sau khi kết thúc giả lập sẽ xác định được các thông báo nó định gửi cho pi nhưng
chưa đến (trạng thái kênh truyền)
• Đó là các thông báo thuộc nhát cắt nhất quán gần nhất
• Giải pháp với chụp trạng thái
– Mỗi pi ghi lại chuỗi các thông báo nhận được từ pj giữa thời điểm pi thiết lập biến
answer và thời điểm pi nhận được thông báo đánh dấu từ pj
– Đó là các thông báo đang di chuyển thuộc nhát cắt
nhất quán
4.1.10. Hàng đợi
Queue: là một danh sách tuyến tính mà phép thêm được tiến hành một đầu danh
sách, phép loại bỏ được tiến hành tại đầu còn lại của danh sách. Queue còn gọi là danh
sách FIFO (First In First Out)
4.2. GIẢI THUẬT
Giải thuật được trình bày ở đây là giải thuật Lamport nhằm cho phép ghi lại các sự kiện
của hệ tin học phân tán. Giải thuật này nhằm giải quyết vấn đề trình tự (vấn đề mấu chốt
của hệ phân tán) dựa trên giá trị đồng hồ lo gích để sắp xếp các thông điệp đến.
Mỗi trạm s đều có trang bị công tơ với các giá trị nguyên gọi là Hs. Đó chính là đồng hồ
logic tăng lên giữa hai sự kiện kế tiếp. Trạm e phát thông điệp ghi dấu E của mình dựa
trên giá trị hiện hành của He. Khi nhận được thông điệp, trạm r cập nhật đồng hồ Hr
riêng của mình bằng giải thuật sau đây :
Học viên: Nguyễn Đình Lâm Khánh Trang 22

2 REL Thông điệp REL được phát đi cho tất cả các trạm, khi
trạm i đã rời khỏi đoạn găng
3 ACQ Thông điệp ACQ được gửi bởi trạm i cho trạm j đã
nhận được từ trạm i thông điệp REQ.
2. Khi có một thông điệp được gởi đi bởi trạm i đồng thời nó cũng được ghi trong
hàng đợi của trạm này.
Giả sử rằng mỗi hàng đợi ban đầu chứa các thông điệp :
Trong đó, i, Hinit là thời điểm khởi sự giống nhau cho tất cả các trạm.
Tiêu chí để sắp xếp dựa vào Hi
Học viên: Nguyễn Đình Lâm Khánh Trang 23
a → b ⇔ H
i
(a) < H
i
(b)
a ⇒ b ⇒ (H
i
(a) < H
i
(b)) hay (H
i
(a) = H
i
(b) và i<j)
M
i
= (REL, H
init
, i)
Tiểu luận: Hệ phân tán GVHD: PGS-TS. Lê Văn Sơn

đồng hồ lôgíc của trạm 1 lại nhỏ hơn trạm 2
Học viên: Nguyễn Đình Lâm Khánh Trang 24
M
i
= (REL, H
init
, i)
Tiểu luận: Hệ phân tán GVHD: PGS-TS. Lê Văn Sơn
- Rõ ràng là yêu cầu trạm i phải có mặt trong hàng đợi của trạm j khi trạm j đang vào
đoạn găng. Điều này cung cấp sự mâu thuẫn yêu cầu của chính tạm j ở tại đỉnh của hàng
đợi yêu cầu khi một đồng hồ logic nhỏ hơn đang có mặt.
Học viên: Nguyễn Đình Lâm Khánh Trang 25