- Thiết kế và phân tích giải thuật duy trì dữ liệu chung phân tán. - Abstract: Giới thiệu hệ phân tán, các mô hình phân tán, vai trò, đặc trưng của các hệ phân tán, các khái niệm cơ bản về cấu hình, thực hiện và phương pháp đánh giá độ phức tạp của giải thuật phân tán.Trình bày bài toán duy trì dữ liệu chung trong hệ phân tán và các giải thuật sơ đẳng, bao gồm giải thuật phát tỏa đầy đủ và giải thuật cập nhật tăng trưởng, trình bày mô hình bài toán, tiêu chuẩn đánh giá độ phức tạp và trình bày giải thuật cập nhật với tri thức bộ phận, giải thuật AS. - Đề 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 mang lại 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. - Từ đó đưa ra những ý kiế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ê phán. - Keywords: Duy trì dữ liệu, Giải thuật, Hệ 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. - Mục tiêu của luận văn này là xem xét, đánh giá một số giải thuật cập nhật “khung nhìn”. - về đối tượng chung đó, đồng thời đưa ra đề xuất cải tiến các giải thuật đã xem xét nếu có thể.. - Các giải thuật duy trì dữ liệu chung trong hệ phân tán, và đặc biệt phương pháp Phát tỏa với Tri thức Bộ phận, được tìm hiểu trong luận văn này bao gồm Phát tỏa Đầy đủ, Cập nhật Tăng trưởng [4], giải thuật AS [3]. - Từ các tìm hiểu về giải thuật trên, tác giả luận văn đã đưa ra một đề xuất cải tiến giải thuật AS. - Cải tiến này được thực hiện bằng cách cắt bỏ các thông báo dư thừa được sử dụng trong giải thuật AS. - Kết quả cải tiến được tác giả luận văn đánh giá và chứng minh. - Ngoài ra, trong luận văn này, tác giả đã quan tâm đến các khía cạnh thực tế khi áp dụng những giải thuật được xem xét hoặc đề xuất, trong đó khả năng kháng lỗi với tính tự ổn định [7] được đặc biệt chú ý. - Với mỗi giải thuật đã được xem xét hoặc đề xuất, tác giả đã chỉ ra một phiên bản tự ổn định của nó.. - Luận văn được trình bày trong năm chương với nội dung mỗi chương như sau:. - Chương 1 giới thiệu hệ phân tán, các mô hình hệ phân tán, vai trò, đặc trưng của các hệ phân tán, các khái niệm cơ bản về cấu hình, thực hiện và phương pháp đánh giá độ phức tạp của giải thuật phân tán . - Phần cuối chương trình bày các vấn đề về khả năng kháng lỗi với tính chất tự ổn định [7].. - Tiếp theo, Chương 2 trình bày bài toán duy trì dữ liệu chung trong hệ phân tán và các giải thuật sơ đẳng, bao gồm giải thuật Phát tỏa Đầy đủ và giải thuật Cập nhật Tăng trưởng [4]. - Mô hình bài toán, tiêu chuẩn đánh giá độ phức tạp được trình bày. - Với mỗi giải thuật, sau phần xem xét và trình bày giải thuật, tác giả đều đưa ra một ví dụ minh họa thực hiện của giải thuật.. - Chương 3 trình bày giải thuật cập nhật với tri thức bộ phận, giải thuật AS [3]. - Sau phần trình bày tư tưởng và chi tiết giải thuật là phần chứng minh tính đúng đắn và đánh giá các độ phức tạp. - Một ví dụ được tác giả đưa ra để minh họa cho hoạt động của giải thuật AS.. - 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.. - Tho05 Nguyễn Đại Thọ, Tập các bài giảng Các giải thuật phân tán, 2005.