ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ CAO HÙNG CƯỜNG ỨNG DỤNG CÂY QUYẾT ĐỊNH MỜ TRONG KHAI
PHÁ DỮ LIỆU

Ngành: Công nghệ thông tin
Mã số: 1.01.10

LUẬN VĂN THẠC SỸ

NGƯỜI HƯỚNG DẪN KHOA HỌC:
PGS. TS. HỒ THUẦN
Hà Nội - 2007
2

MỤC LỤC

LỜI CẢM ƠN 1
MỤC LỤC 2
CÁC THUẬT NGỮ VÀ TỪ VIẾT TẮT 4
DANH SÁCH CÁC HÌNH VẼ 6

4.2. Thực hiện cải tiến 45
4.3. Tính đúng đắn và độ phức tạp 49
4.4. Ví dụ một thực hiện 52
CHƢƠNG 5. GIẢI THUẬT DUY TRÌ DỮ LIỆU CHUNG PHÂN TÁN ÁP DỤNG
TRONG THỰC TIỄN 58
5.1. Hệ thống động với tôpô bất kỳ 58
5.2. Dữ liệu chung phân tán 59
5.3. Độ dài dữ liệu không cố định 59
5.4. Khả năng kháng lỗi và tính tự ổn định 60
KẾT LUẬN 63
TÀI LIỆU THAM KHẢO 64

4
CÁC THUẬT NGỮ VÀ TỪ VIẾT TẮT

TT
Tiếng Việt
Tiếng Anh
Ý nghĩa
1
Bộ xử lý
Processor
Một thực thể trong mạng
2
Cập nhật Tăng
trưởng
Incremental
Update
Cập nhật đƣợc thực hiện lần lƣợt trên
từng bộ xử lý

7
Dẫn ống
Pipeline
Khi nhận đƣợc thông báo từ bộ xử trƣớc
thì chuyển ngay thông báo này cho bộ xử
lý liền sau.
8
Dữ liệu chung
Common data
Dữ liệu đƣợc nhìn nhận nhƣ nhau bởi
mọi thực thể trong hệ thống
9
Hệ phân tán
Distributed
system
Hệ thống bao gồm các thiết bị tính riêng
rẽ có thể giao tiếp với nhau
10
Khứ lỗi
Fault tolerance
Khả năng hệ thống bỏ qua một số hữu
5
hạn lỗi để những bộ phận chƣa bị lỗi vẫn
hoạt động bình thƣờng
11
Phát tỏa
Broadcast
Gửi thông tin đến tất cả các bộ xử lý
trong thành phần liên thông
12

Một thực thể trong mạng
18
Tự ổn định
Self-stabilizing
Tính chất của hệ thống có thể xuất phát
từ trạng thái bất kỳ luôn thể hiện đƣợc
hành vi hợp lệ mong muốn.
19
Khung nhìn
View
“Hình ảnh” mà một bộ xử lý nhận đƣợc
từ một bộ xử lý khác
20
Nguồn
Source
Bộ xử lý nguồn

6
DANH SÁCH CÁC HÌNH VẼ

Hình 1.1
Mô hình tổng quát hệ thống phân tán
(12)
Hình 1.2

Hoạt động của một tiến trình (mũi tên biểu diễn thông báo
sửa lỗi )
(36)
Hình 3.5
Một thực hiện của giải thuật AS (vùng chữ nhật đầu tiên).
(39)
Hình 4.1
Giải thuật AS cải tiến
(48)
Hình 4.2
Một thực hiện của giải thuật AS cải tiến (vùng chữ nhật đầu
tiên).
(53)
Hình 5
Khung chung cho các phiên bản tự ổn định của các giải thuật
Cập nhật Tăng trưởng, giải thuật AS, và giải thuật AS cải
tiến.
(61)
7

MỞ ĐẦU

Trong tính toán phân tán có rất nhiều công việc liên quan đến việc duy trì khung
nhìn (view) đến các đối tƣợng chung tại các trạm (sites) khác nhau của hệ thống phân
tán. Với đối tƣợng chung là tôpô của hệ thống ta có yêu cầu cập nhật tôpô, hay nếu đối
tƣợng chung là một tài nguyên cụ thể đƣợc lƣu trữ trên một trạm nào đó ta có yêu cầu
liệt kê danh sách tài nguyên trên mỗi trạm, hoặc một cơ sở dữ liệu tổng quát.
Các đối tƣợng này bị tác động bởi những thay đổi, ví dụ liên kết giữa hai nút mạng
đƣợc thêm mới hay mất đi làm thay đổi tôpô mạng, một tài nguyên đƣợc chiếm dụng
rồi giải phóng, một bản ghi cơ sở dữ liệu đƣợc sửa đổi. Nhƣ vậy, vấn đề đặt ra ở đây là

Trong Chương 4, tác giả đƣa ra một đề xuất cải tiến giải thuật AS bằng cách cắt bỏ
các thông báo không cần thiết trong giải thuật AS. Hiệu quả tiết kiệm thời gian và
thông báo của giải thuật AS cải tiến so sánh với giải thuật gốc đƣợc phát biểu và
chứng minh. Giải thuật cũng đƣợc mô tả bằng mã hình thức.Cuối cùng là minh hoạ
một thực hiện của giải thuật AS cải tiến.
Chương 5 bàn về các thay đổi cần thực hiện để các giải thuật duy trì dữ liệu có thể
thực thi đƣợc trong một số vấn đề hiện thực của hệ phân tán, đó là các vấn đề về Hệ
thống với tôpô bất kỳ, Dữ liệu chung phân tán, Độ dài dữ liệu thay đổi, Khả năng
kháng lỗi và tự ổn định.

Chắc chắn, luận văn còn có những thiếu sót trong nội dung cũng nhƣ trong trình
bày. Tác giả của luận văn rất mong nhận đƣợc sự đóng góp ý kiến của các thầy cô giáo
và của các anh/chị học viên. 9
CHƯƠNG 1. HỆ PHÂN TÁN

1.1. Khái niệm hệ phân tán
Có rất nhiều khái niệm khác nhau về hệ phân tán. Một cách tổng quan, hệ phân tán
là tập hợp các thiết bị tính riêng rẽ có thể giao tiếp với nhau. Đây là một khái niệm hết
sức tổng quát, bao trùm một phạm vi rộng các hệ thống máy tính ngày nay, từ các bộ
chíp VLSI đến các bộ đa xử lý, các mạng cục bộ, và Internet. Nếu nhƣ hệ song song
phối hợp nhiều bộ xử lý nhằm giải quyết một vấn đề cho trƣớc một cách nhanh nhất
thì hệ phân tán bao gồm một tập các bộ xử lý có chƣơng trình làm việc riêng bán độc
lập, vì những lý do gì đó, ví dụ chia sẻ tài nguyên, tăng tính sẵn sàng, khứ lỗi, các bộ
xử lý cần phối hợp hành động với nhau.
Ta có thể thấy các hệ phân tán ở khắp mọi nơi. Điển hình, các hệ phân tán đƣợc sử
dụng để chia sẻ tài nguyên và chia sẻ dữ liệu. Các máy tính kết nối mạng với nhau có
thể dùng chung máy in, máy quét, chia sẻ các tệp tài liệu, chƣơng trình… Tính toán

Các ƣu điểm của hệ phân tán so với máy tính cá nhân và so với hệ tập trung đƣợc
chỉ ra ngắn gọn trong các bảng sau.

Bảng 1.1. Ưu điểm của hệ phân tán so với máy tính cá nhân.
Ưu điểm
Mô tả
Chia sẻ dữ liệu
Cho phép nhiều người dung cùng truy cập vào một cơ
sở dữ liệu chung
Chia sẻ thiết bị
Cho phép nhiều người dung dung chung các thiết bị đắt
tiền như máy in màu, máy quét,
Truyền thông
Giúp truyền thông giữa người với người dễ dàng hơn,
ví dụ bằng thư điện tử
Mềm dẻo
Phân công việc cho bất kỳ máy nào sẵn sàng

11
Bảng 1.2. Ưu điểm của hệ phân tán so với hệ tập trung.
Ưu điểm
Mô tả
Hiệu năng
Máy tính đa bộ xử lý có hiệu năng cao hơn máy tính
mainframe
Tốc độ
Tổng năng lực tính toán của một hệ phân tán có thể
cao hơn máy tính mainframe
Phân tán
Một số ứng dụng chạy trên nhiều máy tính xa nhau về

là một máy trạng thái. Một hệ phân tán đƣợc mô hình hóa bằng tập n máy trạng thái.
Ký hiệu máy thứ i là P
i
.
Truyền thông giữa các thực thể có thể thực hiện bằng cách chuyển thông báo hay
sử dụng bộ nhớ dùng chung. Truyền thông bằng cách ghi vào và đọc ra từ bộ nhớ dùng
chung thƣờng hạn chế hệ thống với các thực thể gần nhau về mặt địa lý, ví nhƣ hệ
thống đa bộ xử lý hay các máy tính đa nhiệm. Truyền thông theo cách chuyển thông
báo không có giới hạn nhƣ vậy, có thể thực hiện trong cả hệ thống mà các thực thể rất
xa nhau về mặt địa lý nhƣ các mạng máy tính. Hình 1.1. dƣới đây là minh họa mô hình
tổng quát của các hệ thống phân tán. Hinh 1.1. Mô hình tổng quát hệ thống phân tán.

Tùy theo phƣơng pháp truyền thông đƣợc sử dụng, ta có mô hình chuyển thông báo
hay mô hình với bộ nhớ dùng chung.
13
1.4.1. Mô hình chuyển thông báo
Trong mô hình chuyển thông báo, các láng giềng trao đổi thông tin cho nhau bằng
cách gửi và nhận thông báo. Liên kết giữa các thực thể có thể đơn hoặc lƣỡng hƣớng.
Liên kết đơn hƣớng từ thực thể P
i
đến thực thể P
j
đƣợc sử dụng để chuyển thông báo
từ P
i
đến P
j

đến P
j
và q
j,i
cho hƣớng từ P
j
đến P
i
.
Trạng thái của hệ thống phân tán chuyển thông báo tại một thời điểm cụ thể đƣợc
xác định bởi trạng thái của các bộ xử lý và nội dung của các hàng đợi chứa thông báo
tại thời điểm đó. Cấu hình hệ thống (hay cấu hình) đƣợc dùng để chỉ trạng thái này.
Một cấu hình đƣợc ký hiệu c = (s
1
, s
2
, …, s
n
, q
1,2
q
1,3
, …, q
i,j
, …., q
n, n-1
), trong đó s
i
, 1
≤ i ≤ n , là trạng thái của P

m
), trong đó s
i
, 1 ≤ i
≤ n, là trạng thái của P
i
, r
j
, 1 ≤ j ≤ m, là nội dung của ô nhớ dùng chung thứ j.

Hình 1.3. Mô hình với bộ nhớ dùng chung.

1.4.3. Mô hình xen kẽ
Mô hình xen kẽ đƣợc sử dụng để lý giải hành vi của hệ thống phân tán. Trong mô
hình này, tại mỗi thời điểm có duy nhất một bộ xử lý thực hiện một bƣớc tính (còn gọi
là bƣớc nguyên tử). Mỗi bƣớc nguyên tử bao gồm một số phép tính bên trong bộ xử lý,
hay còn gọi là sự kiện tính, và một phép giao, hay còn gọi là sự kiện giao - một phép
gửi hoặc nhận trong hệ thống chuyển thông báo hay một phép ghi hoặc đọc trong hệ
thống sử dụng bộ nhớ dùng chung.
1.4.4. Thực hiện và những tính chất của thực hiện
Trong một hệ thống phân tán, các bộ xử lý có thể thực hiện các bƣớc tính một cách
đồng thời; tuy nhiên, chúng ta giả thiết bƣớc tính này không ảnh hƣởng đến bƣớc tính
khác. Điều này đúng trong mô hình chuyển thông báo vì một thông báo đƣợc gửi đi
không thể nhận đƣợc bởi thao tác nhận xảy ra đồng thời với thao tác gửi. Trong mô
hình bộ nhớ dùng chung, chúng ta giả thiết kiến trúc bộ nhớ dùng chung đảm bảo tuần
tự hóa: có thể sắp xếp các thao tác đọc và ghi theo thứ tự hoàn toàn để kết quả của
15
thao tác đọc từ một ô nhớ là giá trị đƣợc ghi vào ô nhớ tại lần ghi cuối cùng vào ô nhớ
trƣớc thao tác đọc.
Trong các phần sau đây, chúng ta sử dụng thuật ngữ bước cho bƣớc nguyên tử và

c
2
 … c
n-1

an-1
c
n
= c’. Bƣớc tính a’
đƣợc gọi là áp dụng được trên cấu hình c nếu tồn tại cấu hình c’ để c 
a'
c’.
Một thực hiện E = (c
1
, a
1
, c
2
, a
2
, …) là một dãy xen kẽ các cấu hình và bƣớc tính
trong đó c
i-1

a
i-1
c
i
(i > 1); nói cách khác, cấu hình c
i

i, j
(m) – thông báo m đƣợc P
i
gửi cho P
j

nhƣng bị mất và P
j
không nhận đƣợc. Sự kiện loss
i, j
(m) áp dụng đƣợc trên cấu hình c
k

nếu trong c
k
, q
i,j
chứa m. Kết quả áp dụng loss
i, j
(m) trên c
k
đƣợc cấu hình c
k+1
trong đó
m bị loại khỏi q
i,j
còn các thành phần khác không thay đổi so với trong c
k
. Khác với
các sự kiện tính đƣợc thực hiện bởi các bộ xử lý, trong các thực hiện thỏa đáng, chúng

các giải thuật khác, giải thuật phân tán đƣợc đánh giá độ phức tạp trên hai khía cạnh:
độ phức tạp tính toán và độ phức tạp bộ nhớ. Thoạt nhìn, việc đánh giá độ phức tạp
tính toán dƣờng nhƣ trái ngƣợc với tính không đồng bộ của hệ thống phân tán. Theo
định nghĩa về các hệ thống không đồng bộ, không có giới hạn trên về thời gian xử
lý/truyền thông báo. Tuy nhiên, để có thể đánh giá và so sánh các giải thuật với nhau,
ngƣời ta sử dụng số vòng không đồng bộ để đánh giá độ phức tạp của một thực hiện cụ
thể. Vòng không đồng bộ (hay vòng) thứ nhất trong thực hiện E là tiền tố ngắn nhất E’
của E sao cho mỗi bộ xử lý thực hiện ít nhất một bƣớc trong E’. Gọi E’’ là hậu tố của
E theo liền sau E’, E=E’E’’. Vòng thứ hai của E là vòng thứ nhất của E’’, vv… Số
17
vòng trong thực hiện của một giải thuật phân tán đƣợc dùng để đánh giá độ phức tạp
thời gian của giải thuật.
Một cách trực quan, định nghĩa vòng không đồng bộ bỏ qua tốc độ của các bộ xử
lý bằng việc kéo dài vòng đủ dài để trong mỗi vòng, bộ xử lý có tốc độ chậm nhất
cũng thực hiện đƣợc một bƣớc tính.
Độ phức tạp thời gian của một hệ thống đồng bộ là số sung trong thực hiện (bằng
số vòng).
Độ phức tạp bộ nhớ của một giải thuật là tổng số bit nhớ (dùng chung và cục bộ)
đƣợc sử dụng để cài đặt giải thuật.
Độ phức tạp thông báo là tổng số thông báo (hoặc tổng kích thƣớc các thông báo)
đƣợc gửi/nhận khi thực hiện giải thuật.
1.6. Khả năng kháng lỗi và tính tự ổn định
1.6.1. Khả năng kháng lỗi
Khả năng kháng lỗi là một trong những đặc tính quan trọng của bất cứ hệ thống
nào, không chỉ các hệ phân tán. Khả năng kháng lỗi của một hệ thống đƣợc thể hiện ở
số lƣợng và số loại lỗi mà hệ thống có thể gặp phải nhƣng có thể khắc phục để hoạt
động bình thƣờng trở lại sau khi gặp lỗi. Nhƣ vậy, một hệ thống thực sự tin cậy phải
có khả năng kháng lỗi tốt.
Có nhiều phƣơng pháp kháng lỗi, trong đó phƣơng pháp lý tƣởng nhất là làm cho
hệ thống có tính tự ổn định để sau khi hệ thống gặp bao nhiêu, bất kỳ loại lỗi gì cũng

một số lỗi thƣờng gặp. Chúng ta không thể kể ra tất cả các lỗi tiềm tàng, do vậy không
thể đảm bảo hệ thống không còn lỗi. Một khi, hệ thống gặp lỗi lạ, tức là lỗi không có
trong danh sách lỗi, nó không biết giải quyết nhƣ thế nào và mãi mãi trong trạng thái
nhƣ vậy. Một cách giải quyết khác là khứ lỗi [AS04, Lyn97]. Tuy nhiên, cách này
cũng chỉ khắc phục đƣợc hữu hạn lỗi. Khi số lỗi vƣợt quá hệ số kháng lỗi, hệ thống rơi
vào trạng thái lỗi và không thể hoạt động bình thƣờng trừ khi nó đƣợc khởi động lại.
19
1.6.4. Đánh giá độ phức tạp
Cũng nhƣ các giải thuật phân tán khác, giải thuật tự ổn định đƣợc đánh giá độ phức
tạp thời gian dựa trên số vòng không đồng bộ. Số vòng trong thực hiện của một giải
thuật tự ổn định đƣợc dùng để đánh giá độ phức tạp thời gian của giải thuật.
Giải thuật tự ổn định không bao giờ kết thúc, và các bộ xử lý phải tiếp tục liên lạc
với các láng giềng của chúng. Trong mô hình với bộ nhớ dùng chung, các bộ xử lý
phải tiếp tục đọc các ô nhớ dùng chung của các láng giềng. Trong mô hình chuyển
thông báo, các bộ xử lý phải tiếp tục gửi và nhận thông báo. Tính chất không kết thúc
của giải thuật tự ổn định đƣợc giải thích nhƣ sau: giả sử các bộ xử lý kết thúc, P
i
kết
thúc ở trạng thái s
i
. Theo tính chất tự ổn định của giải thuật, hệ thống phải đạt đến cấu
hình an toàn xuất phát từ bất kỳ cấu hình nào. Khi hệ thống đƣợc bắt đầu từ cấu hình c
tại đó bộ xử lý P
i
có trạng thái s
i
, không có bộ xử lý nào thực hiện bất kỳ bƣớc nào,
nhƣ vậy c là một cấu hình an toàn. Do vậy, nhiệm vụ của giải thuật đã đạt đƣợc khi
mỗi bộ xử lý P
i

đƣợc gửi/nhận khi thực hiện giải thuật.

21

22
Khi xảy ra sự cố gây ra đứt đoạn kết nối trong mạng hoặc có thể do một nguyên
nhân bất kỳ nào đó, các nút mạng có thể có các khung nhìn khác nhau về cơ sở dữ liệu
chung, một số nút mạng vẫn chứa các bản ghi đã cũ. Do vậy, khi kết nối đƣợc thiết lập
trở lại, sự khác biệt giữa các khung nhìn giữa các nút sẽ cần phải đƣợc loại bỏ. Hai nút
liền kề liên kết đƣợc khôi phục gửi khung nhìn cho nhau và thống nhất với nhau một
khung nhìn chung. Tiếp đó, mỗi nút đƣơng sự sẽ gửi khung nhìn chung đến tất cả các
nút trong cùng thành phần liên thông. Phát biểu hình thức của bài toán này đƣợc cho
trong mục 2.2 liền sau đây.
Một phƣơng pháp sơ đẳng để thực hiện việc truyền khung nhìn chung đến tất cả
các nút trong mạng là phát tỏa thông tin đến tất cả các nút. Phƣơng pháp này, đƣợc gọi
là Phát tỏa Đầy đủ (Full Broadcast), có thể rất lãng phí về truyền thông vì nó không
tận dụng tri thức có trƣớc trong hệ thống. Các nút chỉ cần thông báo về các thay đổi
nếu chúng đã có khung nhìn gần đúng về cơ sở dữ liệu. Phƣơng pháp Cập nhật Tăng
trưởng (Incremental Update) [4], [2] tận dụng toàn bộ các tri thức đã có trong hệ
thống, chỉ gửi duy nhất một thông báo trên một lỗi.
Phát tỏa Đầy đủ và Cập nhật Tăng trưởng là hai đại diện cho hai thái cực; một thái
cực tốn kém cho truyền thông nhất nhƣng có độ phức tạp thời gian gần tối ƣu, thái cực
kia hiệu quả nhất cho truyền thông nhƣng có độ phức tạp thời gian lớn. Trong khi Cập
nhật Tăng trưởng tốt hơn Phát tỏa Đầy đủ ở độ phức tạp truyền thông, nó lại xấu hơn
Phát tỏa Đầy đủ khi xét về độ phức tạp thời gian. Thực tế này là do Phát tỏa Đầy đủ
đã tận dụng tối đa kỹ thuật dẫn ống (pipeline) thông điệp trong khi Cập nhật Tăng
trưởng không sử dụng kỹ thuật này [5].
Bài toán Phát tỏa với Tri thức Bộ phận (Broadcast with Partial Knowledge), đƣợc
phát biểu trong [5], là bài toán cập nhật khung nhìn của tất cả các nút trong khi tận
dụng đƣợc cả tri thức có trƣớc và cả kỹ thuật dẫn ống - nhằm giảm thiểu cả độ phức
tạp thông báo và độ phức tạp thời gian.
Một kết quả quan trọng của [4] là bài toán Cập nhật Tôpô có thể rút gọn về bài
toán Phát tỏa với Tri thức Bộ phận. Cụ thể hơn, mọi giao thức Phát tỏa với Tri thức
Bộ phận có thể chuyển thành giao thức Cập nhật Tôpô với cùng độ phức tạp thời gian


24

Hình 2.1. Ví dụ minh họa bài toán Duy trì dữ liệu chung trong hệ phân tán. Trong
ví dụ này, chúng ta có n+1 = 5 bộ xử lý duy trì một khung nhìn với m = 4 mục. Nguồn
là bộ xử lý 0. Các mục sai so với nguồn được gạch chân. Độ sai khác cục bộ là số mục
gạch chân tại một bộ xử lý. Độ sai khác tổng là ∆ = 7.

Dữ liệu đƣợc lƣu tại mỗi bộ xử lý (gồm m bít) là khung nhìn của nó về dữ liệu
nguồn. Nhiệm vụ đặt ra cho các bộ xử lý là cập nhật khung nhìn của chúng mỗi khi dữ
liệu nguồn thay đổi sao cho khung nhìn của tất cả các bộ xử lý giống nhau và giống dữ
liệu nguồn.
Ký hiệu các bộ xử lý trong chuỗi bắt đầu từ bộ xử lý nguồn lần lƣợt là P
0
(nguồn),
P
1
, , và P
n
. Gọi x
0
, x
1
, , x
n
lần lƣợt là dữ liệu/khung nhìn của P
0
, P
1
, , P

đƣợc hiểu là khoảng trắng giữa hai cột dữ liệu ứng với chúng; các số 0 hoặc 1 ghi ở
một khoảng trắng chỉ bít 0 hoặc 1 đang đƣợc truyền trên liên kết tƣơng ứng.
3
2
1
0
0
1
0
0 1
1
0
1 0
1
0
0 1
0
1