1
THUẬT TOÁN GẮN BÓ TRÊN CƠ SỞ DẤU VÀ
BÀI TOÁN DUY TRÌ MỘT SỰ GẮN BÓ MẠNH
GIỮA CÁC BẢN SAO
Giáo viên hướng dẫn:PGS. TS. Lê Văn Sơn
Học viên: Trần Thị Thùy Dương
Ngành: Khoa học máy tính
Khóa học: 2008 - 2010
ĐẠI HỌC ĐÀ NẴNG
TRƯỜNG ĐẠI HỌC BÁCH
KHOA

2
Thuật toán duy trì sự gắn bó trên cơ sở 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.
- Mỗi một yêu cầu được phát đi cho tập hợp các trạm.
- Tê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.
- Có sự gắn bó yếu giữa các bản sao.
3
Thuật toán duy trì sự gắn bó trên cơ sở dấu
2. Triển khai hệ ổn định (1)
- Các giao dịch cần xét là các khả năng đọc, ghi hay cập
nhật.
- Mỗi 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.
- 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

2 Hoạt động
Trạm đã nhận một yêu cầu cập nhật cục bộ mà yêu
cầu này đã được truyền cho các trạm khác để kiểm
tra
3 Thụ động
Trạm đồng ý cho một cập nhật và chờ trật tự tương
ứng
4 Cập nhật
Trạm đang trong tình trạng chuyển của cập nhật,
trong khi đó tất cả các yêu cầu khác truyền đến đều
được lưu trữ. Chúng sẽ được xử lý khi quay về một
trong các trạng thái khác
7
1
1
2
2
3
3
4
4
Lựa chọn yêu cầu có thời gian dấu dài
nhất nếu có nhiều yêu cầu được đưa ra
Nghỉ ngơi
Hoạt động
Thụ động
Cập nhật
Duy trì sự gắn bó mạnh giữa các bản sao
2. Sơ đồ thuật toán
8

= = b
n2

b
1m
= b
2m
= = b
nm
Gọi M là cực đại của các cập
nhật có thể diễn ra đồng thời
M = n x m
9
Xử lý sự cố trên một trạm (1)
Sau khi cập nhật
(thay đổi)
Trước khi cập nhật
(thay đổi)
Gắn bó
Không Gắn bó
1

2

3
Ba giai đoạn của một giao dịch
10
Xử lý sự cố trên một trạm (2)
Cơ chế cho phép duy trì gắn bó trong môi
trường phân tán có sự cố: