Tài liệu Truyền bá thông tin phân tán giữa các tác tử di động luận văn ths. công nghệ thông tin 60 48 15

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ LÊ TRỌNG HÙNG TRUYỀN BÁ THÔNG TIN PHÂN TÁN GIỮA CÁC TÁC TỬ DI ĐỘNG LUẬN VĂN THẠC SĨ Hà Nội, 2008 ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ LÊ TRỌNG HÙNG TRUYỀN BÁ THÔNG TIN PHÂN TÁN GIỮA CÁC TÁC TỬ DI ĐỘNG Ngành: Công nghệ Thông tin Chuyên ngành: Truyền dữ liệu và Mạng máy tính Mã số: 60 48 15 LUẬN VĂN THẠC SĨ HƯỚNG DẪN KHOA HỌC TS. NGUYỄN ĐẠI THỌ Hà Nội, 2008 1 MỤC LỤC LỜI CAM ĐOAN.......................................................... Error! Bookmark not defined. LỜI CẢM ƠN ............................................................... Error! Bookmark not defined. MỤC LỤC .................................................................................................................. 1 BẢNG THUẬT NGỮ VÀ CÁC TỪ VIẾT TẮT ....................................................... 3 DANH MỤC HÌNH VẼ, GIẢI THUẬT.................................................................... 5 MỞ ĐẦU .................................................................................................................... 7 CHƯƠNG 1. HỆ PHÂN TÁN ................................................................................. 10 1.1. Khái niệm hệ phân tán ..................................................................................... 10 1.2. Vai trò hệ phân tán .......................................................................................... 10 1.3. Đặc trưng hệ phân tán...................................................................................... 11 1.4. Mô hình truyền thông báo................................................................................ 11 1.5. Công nghệ tác tử di động ................................................................................. 14 1.5.1. Sự tiến hóa ................................................................................................ 14 1.5.2. Các đặc tính của tác tử di động ................................................................. 15 1.5.3. Ứng dụng của tác tử di động ..................................................................... 15 CHƯƠNG 2. BẦU THỦ LĨNH TRÊN MẠNG ĐẦY ĐỦ ...................................... 17 2.1. Giới thiệu bài toán ........................................................................................... 17 2.2. Mô hình tính toán phân tán .............................................................................. 17 2.3. Giải thuật bầu thủ lĩnh Villadangos ................................................................. 18 CHƯƠNG 3. XÂY DỰNG CÂY KHUNG TỐI THIỂU ........................................ 27 3.1. Bài toán cây khung tối thiểu ............................................................................ 27 3.2. Giải thuật GHS83 ............................................................................................ 27 3.3. Giải thuật SB95 ............................................................................................... 36 CHƯƠNG 4. TRUYỀN BÁ THÔNG TIN PHÂN TÁN ......................................... 47 GIỮA CÁC TÁC TỬ DI ĐỘNG ............................................................................. 47 4.1. Bài toán MAGP – Mobile Agent Gossip Problem............................................ 47 4.2. Một số khái niệm ............................................................................................. 47 4.3. Mối quan hệ giữa MAGP và NLEP ................................................................. 48 4.3.1. Hệ thống truyền thông báo ........................................................................ 49 4.3.2. Mô phỏng một giải thuật truyền thông báo ................................................ 50 4.4. Giải thuật hẹn gặp (Rendezvous Algorithm) .................................................... 53 4.5. Các giải thuật cho MAGP ................................................................................ 54 4.5.1. Mạng bất kỳ .............................................................................................. 54 4.5.2. Mạng đầy đủ không cảm hướng ................................................................ 68 4.5.3. Mạng đầy đủ cảm hướng ........................................................................... 69 2 CHƯƠNG 5. GIẢI THUẬT ĐỀ XUẤT CHO MAGP TRÊN MẠNG ĐẦY ĐỦ... 74 5.1. Phát biểu bài toán ............................................................................................ 74 5.2. Ý tưởng, cấu trúc dữ liệu ................................................................................. 74 5.3. Giải thuật......................................................................................................... 76 CHƯƠNG 6. GIẢI THUẬT ĐỀ XUẤT CHO MAGP TRÊN MẠNG BẤT KỲ ... 94 6.1. Phát biểu bài toán ............................................................................................ 94 6.2. Ý tưởng, cấu trúc dữ liệu ................................................................................. 94 6.3. Giải thuật......................................................................................................... 97 KẾT LUẬN ............................................................................................................ 112 TÀI LIỆU THAM KHẢO ..................................................................................... 115 3 BẢNG THUẬT NGỮ VÀ CÁC TỪ VIẾT TẮT Mobile Agent Tác tử di động, là một chương trình tự trị có khả năng di chuyển trên mạng và thực hiện nhiệm vụ tại mỗi nút. Bài toán truyền bá thông tin phân tán giữa các tác tử di MAGP (Mobile Agent Gossip Problem) động, ban đầu mỗi tác tử có một thông tin riêng, mục đích của MAGP là mỗi tác tử biết thông tin của tất cả các tác tử còn lại. NLEP (Node Leader Election Problem) Rendezvous Algorithm Bài toán bầu thủ lĩnh giữa các nút trong mô hình truyền thông báo. Giải thuật hẹn gặp, một cách tiếp cận để giải quyết bài toán MAGP. GHS83 Giải thuật xây dựng cây khung tối thiểu phân tán của R.G. Gallager, P.A. Humblet, P.M. Spira [19]. SB95 Giải thuật xây dựng cây khung tối thiểu phân tán của Gurdip Singh, Arthur J. Bernstein [8]. MST (MinimumWeight Spanning Tree) Cây khung có trọng số tối thiểu. RPC (Remote Procedure Call) Một giao thức cho phép gọi thủ tục từ xa. REV (Remote Evaluation) Một giao thức cho phép gửi hàm đến nút mạng, thực thi hàm này trên nút đó, rồi trả về kết quả. INF (Inform) Báo tin REQ (Request) Yêu cầu REP (Reply) Trả lời Node Một địa điểm lưu trữ và xử lý dữ liệu trên mạng. MOE (Minimum – weight Outgoing Edge) Cạnh ngoài có trọng số tối thiểu trong số các cạnh ngoài của một mảnh thuộc cây khung MST. Whiteboard Delivering move Bảng trắng của một nút, là nơi tác tử có thể ghi, đọc và xóa thông tin. Bước chuyển giao: bước di chuyển với một thông báo của một tác tử. 4 Backtracking move Rendezvous Algorithm Bước chuyển quay lui của một tác tử. Giải thuật hẹn gặp, các tác tử hẹn gặp nhau ở một điểm nút nào đó trên mạng để trao đổi thông tin. DFS (Depth First Search) Duyệt mạng theo chiều sâu. MOL (Minimum Outgoing Link) Liên kết ngoài tối thiểu của một cây khung. Gossip, Gossiping Giải pháp truyền bá phân tán phỏng theo quá trình phổ biến tin đồn hay lây nhiễm bệnh tật trong xã hội. 5 DANH MỤC HÌNH VẼ, GIẢI THUẬT Hình 1.5.1-1. Sự tiến hóa của mô hình Mobile agents 16 Giải thuật 2.3-1. Giải thuật bầu chọn thủ lĩnh Villadangos 20 Hình 2.3-1.a. Trạng thái ban đầu của mạng 23 Hình 2.3-1.b. Nút 2, 4 khởi tạo giải thuật 24 Hình 2.3-1.c. Nút 1, 3 chuyển thông báo 24 Hình 2.3-1.d. Nút 4 gửi yêu cầu tới nút 2 25 Hình 2.3-1.e. Nút 2 trả lời nút 4 25 Hình 2.3-1.f. Nút 4 trở thành thủ lĩnh 25 Hình 3.2-1. Minh họa chứng minh tính chất 1 30 Hình 3.2-2. Minh họa chứng minh tính chất 2 31 Giải thuật 3.2-1. Giải thuật GHS83 32 Hình 3.2-1.a. Mạng ban đầu 36 Hình 3.2-1.b. Khởi động giải thuật 36 Hình 3.2-1.c. Đánh thức nút kề cận 36 Hình 3.2-1.d. Đợt sát nhập đầu tiên 36 Hình 3.2-1.e. Kết thúc đợt sát nhập đầu 37 Hình 3.2-1.f. Kết thúc giải thuật 37 Giải thuật 3.3-1. Giải thuật SB95 39 Hình 3.3-1.a. Mạng ban đầu 43 Hình 3.3-1.b. Nút 1 đánh thức các nút khác 43 Hình 3.3-1.c. Đợt trộn mảnh đầu tiên 44 Hình 3.3-1.d. Mảnh F3, F7 hấp thu mảnh khác 44 Hình 3.3-1.e. Mảnh F3, F7 tìm MOE 44 Hình 3.3-1.f. F7 chính là cây khung MST 44 Giải thuật 4.3-1. Giải thuật mô phỏng giải thuật A 53 Giải thuật 4.5.1-1. Giải thuật cho MAGP với mạng tùy ý 57 Giải thuật 4.5.1-2. Giải thuật chi tiết cho MAGP với mạng bất kỳ 60 6 Hình 4.5.1-1.a. Trạng thái mạng ban đầu 64 Hình 4.5.1-1.b. Đợt khởi tạo 64 Hình 4.5.1-1.c. Tác tử tìm liên kết có trọng số tối thiểu 65 Hình 4.5.1-1.d. Kết thúc lần lặp đầu tiên 65 Hình 4.5.1-1.e. Thực hiện sát nhập cây khung T2 và T3 66 Hình 4.5.1-1.f. Kết thúc đợt bầu chọn tác tử thủ lĩnh 66 Giải thuật 4.5.2-1. Giải thuật cho MAGP với mạng đầy đủ không cảm hướng 70 Hình 4.5.3-1.a. Mạng đầy đủ cảm hướng 72 Hình 4.5.3-1.b. Một tác tử di chuyển ở bước 1 72 Hình 4.5.3-1.c. Vòng rút gọn ở bước 2 72 Giải thuật 4.5.3-1. Giải thuật cho MAGP với mạng đầy đủ cảm hướng 73 Giải thuật 5.3-1. Giải thuật đề xuất cho MAGP với mạng đầy đủ 79 Hình 5.3-1.a. Trạng thái ban đầu của mạng 86 Hình 5.3-1.b. Vòng ảo rút gọn 87 Hình 5.3-1.c. Khởi tạo đợt bầu chọn 87 Hình 5.3-1.d. Các tác tử thực hiện thủ tục INF 88 Hình 5.3-1.e. Tác tử 1 thực hiện thủ tục INF tại nút 5 88 Hình 5.3-1.f. Tác tử 1 thực hiện thủ tục REP tại nút 7 89 Hình 5.3-1.g. Tác tử 1 thực hiện thủ tục REQ tại nút 1 89 Hình 5.3-1.h. Tác tử 4 được bầu chọn làm thủ lĩnh 90 Giải thuật 6.3-1. Giải thuật đề xuất cho MAGP với mạng bất kỳ 100 Hình 6.3-1.a. Trạng thái mạng ban đầu 105 Hình 6.3-1.b. Đợt khởi tạo 106 Hình 6.3-1.c. Tác tử p2 tìm thấy liên kết ngoài tối thiểu 106 Hình 6.3-1.d. Cây khung T3 hấp thu T2, p3 tìm thấy MOL3 = (2, 5) 107 Hình 6.3-1.e. Cây khung T3 hấp thu T1, p3 tìm kiếm MOL3 107 Hình 6.3-1.f. Tác tử p3 được bầu chọn làm tác tử thủ lĩnh 108 Bảng 1. Bảng so sánh giải thuật đề xuất với giải thuật gốc 116 7 MỞ ĐẦU Với sự phát triển mạnh mẽ của Internet và đặc biệt là các công nghệ truyền thông, cùng với sự bùng nổ nhanh chóng các dịch vụ và nguồn thông tin trên mạng đã làm gia tăng số người sử dụng lên con số khổng lồ. Trao đổi và quảng bá thông tin là một nhu cầu thiết yếu của các thành phần tham gia vào mạng, ngoài ra nó còn đóng vai trò hạ tầng cho nhiều dịch vụ quan trọng khác như: cải tiến hiệu năng của mạng, chuẩn đoán lỗi và duy trì sự ổn định của hệ thống mạng, quản lý cấu hình, lập lịch hội họp, tính toán thông tin gộp, nhân bản nội dung,...Vì vậy, việc nghiên cứu các giải pháp truyền bá thông tin phân tán hiệu quả cao luôn là một chủ đề hấp dẫn đối với các học giả khắp nơi trên thế giới. Giải thuật gossiping là một giải pháp truyền bá thông tin phân tán, phỏng theo quá trình phổ biến tin đồn hay lây nhiễm bệnh tật trong xã hội. Trong bài toán gossip, mỗi bộ xử lý ban đầu có phần thông tin riêng được gọi là tin đồn, mục đích là mỗi bộ xử lý nhận được các tin đồn của tất cả các bộ xử lý khác. Phương pháp này đã được nhiều tác giả tập trung nghiên cứu và đã có những thành quả nhất định [5,12,21,22]. Tác tử di động (Mobile Agent) là một chương trình tự trị có khả năng di chuyển từ nơi này đến nơi khác trên mạng và thực hiện nhiệm vụ nào đó thay cho người dùng. Phương pháp tác tử di động giúp làm giảm tải mạng, tạo ra những ứng dụng phân tán có tính thích nghi và độ linh hoạt cao, có thể giải quyết hiệu quả hơn các bài toán được giải quyết bằng phương pháp khác trong các hệ phân tán [2]. Truyền bá thông tin phân tán giữa các tác tử di động (Mobile Agent Gossip Problem – MAGP) là một hướng nghiên cứu mới, thu hút nhiều sự quan tâm của giới nghiên cứu. Ở đây mỗi tác tử có một thông tin riêng, có không quá một tác tử khởi tạo trên cùng một nút, mục đích của MAGP là làm cho mỗi tác tử thu thập thông tin của tất cả các tác tử còn lại. Rendezvous (hẹn gặp) là một trong những cách tiếp cận để giải quyết bài toán truyền bá thông tin phân tán giữa các tác tử, tất cả các tác tử được yêu cầu hẹn gặp trên một nút tại cùng một thời điểm, bằng cách trao đổi thông tin của tất cả các tác tử tại điểm hẹn gặp, chúng ta giải được bài toán MAGP. Như vậy, mỗi tác tử phải biết rõ hình trạng của toàn mạng, thời điểm và vị trí hẹn gặp, để đạt được điều này, ngoài việc xử lý phức tạp, giải thuật còn chịu nhiều phí tổn về độ phức tạp di chuyển [7,14,16,20]. Tomoko Suzuki và đồng sự đề xuất cách giải quyết bài toán MAGP hiệu quả hơn: một tác tử sẽ được bầu làm thủ lĩnh trong số các tác tử trong mạng, tác tử thủ lĩnh sẽ duyệt toàn mạng để thu thập và truyền bá thông tin cho các tác tử khác [23,24]. Từ khẳng định hai bài toán MAGP và NLEP (Node Leader Election Problem - NLEP) có 8 thể quy về nhau, và dựa trên ý tưởng của các giải thuật bầu thủ lĩnh trong mô hình truyền thông báo, Tomoko Suzuki và đồng sự đã đưa ra một loạt các giải thuật cho bài toán MAGP với các hình trạng mạng khác nhau như: mạng cây không biết gốc, mạng đầy đủ không cảm hướng, mạng đầy đủ cảm hướng, mạng tùy ý, mạng vòng không đồng bộ, mạng vòng đồng bộ, với độ phức tạp tốt hơn hẳn giải thuật hẹn gặp. Tuy nhiên, giải thuật cho mạng bất kỳ mới chỉ đưa ra ở mức ý tưởng, giải thuật cho mạng đầy đủ phải dùng thêm giả thiết cảm hướng để đạt được độ phức tạp di chuyển tuyến tính, những đánh giá về các giải thuật này mới ở mức sơ lược về độ phức tạp di chuyển. Trên cơ sở ý tưởng của giải thuật gốc, tác giả luận văn đã trình bày một giải thuật chi tiết cho bài toán MAGP trên mạng bất kỳ, và đưa ra một số phương pháp tối ưu bước di chuyển của tác tử, nâng cao tốc độ thực hiện của giải thuật, có chứng minh tính đúng đắn, đánh giá đầy đủ về độ phức tạp di chuyển và thời gian của giải thuật. Tác giả luận văn đề xuất một giải thuật cho bài toán MAGP trên mạng bất kỳ, có đợt bầu chọn tác tử thủ lĩnh là một cải biến từ giải thuật xây dựng cây khung SB95[8]. Giải thuật không cần dùng đến số hiệu mức. Trong giải thuật gốc, mỗi cây khung sẽ được gắn một số hiệu mức, các cây khung được trộn với nhau dựa vào số hiệu mức, tức cây khung T với số hiệu mức L chỉ có thể trộn với cây khung T với số hiệu mức L, qua liên kết ngoài có trọng số tối thiểu của T chỉ khi L  L, vì vậy giải thuật gốc có độ phức tạp thời gian O(N log k + |E|) không tối ưu. Với giải thuật đề xuất, khi tác tử chủ đã xác định được liên kết ngoài có trọng số tối thiểu trên cây khung của nó, tác tử tiến hành sát nhập ngay cây khung của nó với cây khung khác qua liên kết này, điều này làm tăng tốc độ hội tụ của giải thuật. Giải thuật đề xuất có độ phức tạp thời gian O(N + |E|) tối ưu hơn hẳn độ phức tạp thời gian của giải thuật gốc. Độ phức tạp di chuyển của giải thuật đề xuất trong trường hợp xấu nhất là O(N k + |E|), độ phức tạp này không tối ưu. Tuy nhiên, khi mỗi cây khung là sự kết hợp của ít nhất k/log k cây khung ban đầu, thì độ phức tạp của giải thuật chỉ còn là O(N log k + |E|). Tác giả luận văn đề xuất một giải thuật giải quyết bài toán MAGP trên mạng đầy đủ tối ưu hơn giải thuật gốc, bằng cách vận dụng ý tưởng giải thuật bầu thủ lĩnh trên mạng đầy đủ hiệu quả hơn trong mô hình truyền thông báo. Luận văn được tổ chức thành 6 chương, nội dung cụ thể từng chương như sau: Chương 1: Giới thiệu tổng quan về hệ phân tán, vai trò, đặc trưng, mô hình truyền thông báo và công nghệ tác tử di động [1,2,11,17,25]. Chương 2: Trình bày một giải thuật bầu thủ lĩnh hiệu quả trên mạng đầy đủ của tác giả J. Villadangos và đồng sự [13]. Chỉ với giả thiết tồn tại một vòng ảo kết nối logic tất cả các nút trong mạng, mỗi nút trên vòng ảo biết nút kế tiếp nó trên vòng, mà không cần phải biết tất cả các nút cũng như tổng số nút trong mạng, giải thuật vẫn đạt được độ phức tạp tuyến tính cả về thông báo và thời gian. 9 Chương 3: Trình bày hai giải thuật xây dựng cây khung tối thiểu: giải thuật GHS83 của Gallager và đồng sự [19], giải thuật SB95 của Singh và Bernstein [8]. Cả hai giải thuật này đều xây dựng cây khung tối thiểu phân tán từ rừng cây khung, mỗi cây khung trộn với cây khung khác qua cạnh ngoài có trọng số tối thiểu của nó, cho đến khi chỉ còn một cây khung duy nhất bao trùm toàn bộ mạng, đây chính là cây MST cần tìm. Trong GHS83, mỗi mảnh được gắn một số hiệu mức, các mảnh được trộn trên cơ sở số hiệu mức, chính điều này làm chậm tốc độ hội tụ của GHS83, giải thuật có độ phức tạp thời gian O(N log N) không tối ưu. Giải thuật SB95 không sử dụng số hiệu mức, ngay khi mảnh tìm được cạnh ngoài có trọng số tối thiểu của nó, mảnh sẽ thực hiện sát nhập với mảnh khác qua cạnh này, giải thuật có độ phức tạp thời gian là O(N) tối ưu hơn hẳn GHS83. Chương 4: Trình bày mô hình hệ tác tử di động, mối quan hệ giữa hai bài toán MAGP và NLEP, giải thuật hẹn gặp, các giải thuật cho MAGP được đề xuất bởi Tomoko Suzuki và đồng sự trên mạng bất kỳ, mạng đầy đủ không cảm hướng, mạng đầy đủ cảm hướng [23,24]. Trong phần này, tác giả luận văn đóng góp một giải thuật chi tiết cho bài toán MAGP trên mạng bất kỳ, dựa trên giải thuật ở mức ý tưởng về mạng bất kỳ của Tomoko Suzuki và đồng sự. Chương 5: Trình bày giải thuật đề xuất cho bài toán MAGP trên mạng đầy đủ, vận dụng ý tưởng của giải thuật bầu thủ lĩnh trên mạng đầy đủ của J. Villadangos và đồng sự. Giải thuật không cần dùng giả thiết cảm hướng, mỗi nút trong mạng không cần biết tất cả các nút trong mạng cũng như là tổng số nút trong mạng, mà chỉ cần biết nút kế tiếp nó trên vòng ảo nối tất cả các nút trong mạng, nhưng vẫn đạt được độ phức tạp bước di chuyển tốt hơn giải thuật gốc. Chương 6: Trình bày giải thuật đề xuất cho bài toán MAGP trên mạng bất kỳ. Giải thuật có đợt bầu chọn tác tử lĩnh là một cải biến từ giải thuật xây dựng cây khung SB95. Giải thuật có độ phức tạp thời gian tối ưu hơn hẳn so với giải thuật gốc. Cuối cùng là kết luận, tóm lược những đóng góp của luận văn, đồng thời đưa ra một số hướng phát triển tiếp theo. 10 CHƯƠNG 1. HỆ PHÂN TÁN 1.1. Khái niệm hệ phân tán Hệ phân tán là tập các thiết bị tính toán riêng rẽ có thể giao tiếp với nhau. Đây là một định nghĩa 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 hiện đại ngày nay, từ chíp VLSI đến các bộ đa xử lý, các mạng cục bộ và Internet. Mục đích của xử lý song song là phân bổ một nhiệm vụ lớn cho tất cả các bộ xử lý thực hiện. Trong khi với hệ phân tán, mỗi bộ xử lý nói chung có chương trình làm việc riêng bán độc lập, nhưng vì các lý do khác nhau như chia sẻ tài nguyên, tính sẵn sàng, khả năng kháng lỗi, nên các bộ xử lý cần phối hợp hành động với nhau. Hiện nay, hệ phân tán có ở khắp nơi, trong các doanh nghiệp, học viện, chính phủ, quốc phòng,...Điển hình, hệ phân tán cung cấp những phương tiện để chia sẻ các tài nguyên như các máy in màu, máy quét, và chia sẻ dữ liệu. Tính toán ngang hàng cũng là một mô hình hệ phân tán, chúng ngày càng càng trở nên phổ biến trong việc cung cấp các tài nguyên và dịch vụ tính toán. Các hệ thống phân tán tham vọng hơn cố gắng cải tiến hiệu năng bằng cách kết hợp giải quyết các bài toán con một cách song song, và tăng tính sẵn sàng trong trường hợp một số thành phần của hệ thống bị lỗi. 1.2. Vai trò hệ phân tán Với nhiều ứng dụng nổi bật trong thực tiễn, hệ phân tán đang ngày càng trở nên phổ biến, bởi nó nắm giữ những vai trò quan trọng sau: Trao đổi thông tin: Các hệ phân tán cung cấp khả năng chia sẻ thông tin rộng rãi. Các chi nhánh khác nhau của một ngân hàng tại các vị trí địa lý rất xa nhau có thể trao đổi, chia sẽ thông tin cho nhau. Hệ phân tán cũng cung cấp khả năng chia sẻ thông tin giữa các thiết bị hỗn tạp, một máy tính có thể giao tiếp các thiết bị viễn thông khác như điện thoại cố định, di động, các PDA, … Chia sẻ tài nguyên: Các hệ phân tán cung cấp khả năng chia sẻ tài nguyên cả phần cứng lẫn phần mềm, giúp giảm chi phí hệ thống. Các máy tính kết nối mạng có thể dùng chung máy in, máy quét ảnh, có thể chia sẻ các tệp dữ liệu, các tệp chương trình. Nâng cao độ tin cậy, tính sẵn sàng thông qua sao lặp: Bằng việc sao lặp, nhân bản, các hệ phân tán cho độ tin cậy và tính sẵn sàng cao. Nếu toàn bộ dữ liệu của một chi nhánh ngân hàng lưu trong máy tính bị mất do sự cố nào đó, người ta có thể khôi phục lại bằng cách sao phần dữ liệu nhân bản đã được lưu tại một nơi khác trên hệ thống máy tính. 11 Nâng cao hiệu suất thông qua song song hóa: Thông qua song song hóa, các thành phần trong hệ phân tán có thể chia sẻ công việc, thực hiện đồng thời công việc chung, làm tăng hiệu suất hoạt động hệ thống. Đơn giản thiết kế thông qua chuyên dụng hóa: Hệ phân tán làm đơn giản việc thiết kế các hệ thống phức tạp. Người ta có thể phân một hệ thống phức tạp thành các bộ phận con chuyên dụng thực hiện một số tác vụ chuyên biệt nào đó và hợp tác với nhau để giải quyết nhiệm vụ lớn. 1.3. Đặc trưng hệ phân tán Một hệ phân tán có thể được mô tả như là một tập các bộ xử lý tự trị liên lạc với nhau qua một mạng truyền thông và có các đặc trưng sau: Không có đồng hồ chung: Không thể đồng bộ hóa đồng hồ của các bộ xử lý khác nhau vì không biết chắc độ trễ truyền thông. Chúng ta có thể dùng khái niệm nhân quả thay cho đồng hộ vật lý để đạt được tính đồng bộ của hệ thống. Không có bộ nhớ toàn cục: Các bộ xử lý không thể biết được trạng thái toàn cục của hệ thống. Bởi vậy để biết được trạng thái hệ thống, người thiết kế hệ phân tán cần phải xây dựng giải thuật đánh giá các tính chất toàn cục. Không có cơ chế phát hiện sự cố chính xác: Trong hệ phân tán, chúng ta không thể phân biệt được bộ xử lý chậm hay bị sự cố. Khi một bộ xử lý gặp sự cố, các bộ xử lý còn lại vẫn phải tiếp tục làm việc để đạt được kết quả mong muốn. Do đó, cần xây dựng cơ chế phát hiện lỗi và kháng lỗi. Khoảng cách địa lý: Các bộ xử lý trong một hệ thống phân tán có thể nằm cách xa nhau về mặt địa lý. Cấu hình mạng các trạm làm việc hoặc cụm các trạm làm việc trên mạng LAN đang được quan tâm nhiều hơn khi xây dựng các hệ phân tán cỡ nhỏ. Cấu hình mạng các trạm làm việc đang trở nên phổ biến bởi tận dụng được hạ tầng sẵn có, tiết kiệm chi phí. Động cơ tìm kiếm Google dựa trên kiến trúc mạng các trạm làm việc. Sự tự trị và tính hỗn tạp: Các bộ xử lý có tốc độ khác nhau và chúng có thể chạy một hệ điều hành khác nhau, nhưng hợp tác với nhau để giải quyết một vấn đề chung. 1.4. Mô hình truyền thông báo Trong một hệ thống truyền thông báo, các bộ xử lý giao tiếp với nhau bằng cách gửi thông báo qua các kênh truyền thông, mỗi kênh truyền là một kết nối hai chiều giữa hai bộ xử lý. Tô pô của hệ thống được biểu diễn bởi một đồ thị vô hướng, trong đó mỗi nút là một bộ xử lý, mỗi cạnh là một kênh truyền thông giữa các bộ xử lý tương ứng. Giải thuật cho hệ thống truyền thông báo bao gồm một chương trình cục bộ 12 cho mỗi bộ xử lý, các chương trình này cung cấp khả năng cho bộ xử lý thực hiện tính toán cục bộ, gửi và nhận các thông báo từ mỗi hàng xóm của nó. Có thể hình thức hóa như sau: Một hệ thống hay giải thuật bao gồm n bộ xử lý p0, p1,…, pn-1; i là chỉ mục của bộ xử lý pi. Mỗi bộ xử lý pi được coi như một máy trạng thái với tập trạng thái Qi. Bộ xử lý được xác định bởi một nút cụ thể trong đồ thị. Các cạnh liên thuộc với pi trong đồ thị được gắn nhãn bởi các số nguyên từ 1 đến r, trong đó r là bậc của pi. Mỗi trạng thái của bộ xử lý pi chứa 2r thành phần đặc biệt, outbufi(  ) và inbufi(  ), với mọi  thỏa mãn 1 ≤  ≤ r. Thành phần đặc biệt này là tập các thông báo: outbufi(  ) chứa các thông báo mà pi đã gửi tới hàng xóm của nó qua kênh  , nhưng chưa đến nơi, và inbufi(  ) chứa các thông báo nhận được trên kênh  , nhưng chưa xử lý. Tập trạng thái Qi chứa tập con các trạng thái đáng chú ý ban đầu, trạng thái ban đầu của các inbufi(  ) phải là rỗng. Trạng thái của bộ xử lý, ngoại trừ các thành phần outbufi(  ), bao gồm các trạng thái tới được của pi. Hàm chuyển của bộ xử lý pi đưa các đầu vào cho trạng thái tới được của pi, tạo ở đầu ra một giá trị cho trạng thái tới được của pi trong đó mỗi inbufi(  ) rỗng, hàm chuyển cũng tạo ở đầu ra nhiều nhất một thông báo cho mỗi kênh  : thông báo này sẽ được gửi tới hàng xóm trên kênh  . Vì vậy, thông báo gửi trước đó bởi pi đang đợi được chuyển không ảnh hưởng đến bước hiện thời của pi; mỗi bước xử lý tất cả các thông báo đang đợi được chuyển tới pi , dẫn đến thay đổi trạng thái và có nhiều nhất một thông báo được gửi tới mỗi hàng xóm. Cấu hình: Cấu hình là một vec tơ C = (q0 ,…, qn-1) trong đó qi là trạng thái của pi. Các trạng thái của các biến outbuf trong một cấu hình mô tả các thông báo chuyển qua các kênh truyền thông. Cấu hình ban đầu là một vec tơ (q0 ,…, qn-1) sao cho mỗi qi là trạng thái ban đầu của pi. Sự kiện: Với các hệ thống truyền thông báo, chúng ta xem xét hai loại sự kiện, một loại là sự kiện tính, ký hiệu comp(i), biểu diễn một bước tính của bộ xử lý pi, trong đó hàm chuyển của pi được áp dụng cho trạng thái tới được hiện thời. loại còn lại là sự kiện giao, ký hiệu del(i,j,m), biểu diễn sự giao thông báo m từ bộ xử lý pi đến bộ xử lý pj. Thực hiện: Là một chuỗi cấu hình xen kẽ sự kiện mô tả hoạt động của hệ thống, chuỗi này phải thỏa mãn các điều kiện khác nhau. Có hai loại điều kiện là điều kiện an toàn và điều kiện sống động. Điều kiện an toàn là điều kiện phải đúng với mọi tiền tố hữu hạn của chuỗi mô tả, có nghĩa rằng không có gì xấu xảy ra. Điều kiện sống động là điều kiện phải đúng với một số lần nhất định (có thể vô hạn lần), có nghĩa rằng cuối cùng điều tốt sẽ đến. Bất kỳ chuỗi mô tả nào thỏa mãn mọi điều kiện an toàn đặt ra được gọi là một thực hiện. Một thực hiện cũng thỏa mãn tất cả các điều kiện sống động đặt ra được gọi là thực hiện thỏa đáng. 13 Hệ thống không đồng bộ: Một hệ thống được gọi là không đồng bộ nếu nó không có cận trên đối với thời gian. Đoạn thực hiện  trong hệ thống truyền thông báo không đồng bộ là một chuỗi cấu hình xen kẽ sự kiện có dạng: C0, 1, C1, 2, C2, 3,…, trong đó mỗi Ck là một cấu hình và mỗi k là một sự kiện. Nếu  hữu hạn thì nó phải kết thúc trong một cấu hình, và những điều kiện sau phải được thỏa mãn: - Nếu k = del(i, j, m), thì m phải là một phần tử của outbufi(  ) trong Ck-1, với  là nhãn kênh truyền (pi , pj) của bộ xử lý pi. Sự thay đổi từ cấu hình Ck-1 sang Ck là m được loại bỏ khỏi outbufi(  ) trong Ck-1 và được bổ sung vào inbufi(h) trong Ck. Nói cách khác, một thông báo đã được giao nếu và chỉ nếu nó được chuyển từ outbuf của bên gửi sang inbuf của bên nhận. - Nếu k = comp(i), thì sự thay đổi từ cấu hình Ck-1 sang Ck là pi thay đổi trạng thái theo hàm chuyển của nó thực hiện trên trạng thái tới được của pi trong Ck-1, và tập các thông báo xác định bởi hàm chuyển của pi được bổ sung vào các outbufi trong Ck. Nói cách khác, pi thay đổi trạng thái và gửi các thông báo ra ngoài theo hàm chuyển của nó dựa trên trạng thái hiện thời, bao gồm tất cả các thông báo đang chờ được giao. Hàm chuyển của bộ xử lý đảm bảo rằng các inbuf rỗng. Thực hiện là một đoạn thực hiện C0, 1, C1, 2, C2, 3,…, trong đó C0 là cấu hình ban đầu. Trong mô hình không đồng bộ, một thực hiện là thực hiện thỏa đáng nếu mỗi bộ xử lý có số vô hạn lần các sự kiện tính và mỗi thông báo được gửi cuối cùng sẽ được giao. Hệ thống đồng bộ: Trong mô hình đồng bộ các bộ xử lý thực hiện theo các vòng nhịp: thực hiện được phân chia thành các vòng, trong mỗi vòng, mọi bộ xử lý có thể gửi một thông báo tới hàng xóm của nó, các thông báo đã được giao, và mọi bộ xử lý tính toán dựa trên các thông báo vừa nhận. Mô hình này, mặc dù nói chung không khả thi trong những hệ thống phân tán thực hành, nhưng lại rất tiện lợi cho việc thiết kế giải thuật vì không phải tính đến nhiều điều không chắc chắn. Thực hiện trong mô hình đồng bộ là chuỗi cấu hình và sự kiện xen kẽ có thể được phân chia thành các vòng riêng biệt. Mỗi vòng bao gồm sự kiện giao mọi thông báo trong các outbuf, cho đến khi tất cả các outbuf rỗng, sau đó mỗi bộ xử lý thực hiện một bước tính. Trong mô hình đồng bộ, một thực hiện gọi là thực hiện thỏa đáng nếu nó là dãy vô hạn, hàm ý rằng mọi bộ xử lý thực hiện vô hạn bước tính, và mọi thông báo trong các outbuf nhất định sẽ được giao. Kết thúc: Chúng ta giả thiết rằng mỗi tập trạng thái của bộ xử lý bao gồm một tập con các trạng thái kết thúc và mỗi hàm chuyển của bộ xử lý ánh xạ các trạng thái kết thúc chỉ đến các trạng thái kết thúc. Chúng ta nói rằng hệ thống đã kết thúc khi tất 14 cả các bộ xử lý ở trạng thái kết thúc và không còn thông báo nào đang chuyển. Chú ý rằng thực hiện thỏa đáng vẫn vô hạn, nhưng khi bộ xử lý đã vào trạng thái kết thúc, nó sẽ ở lại trạng thái đó, thực hiện các bước “giả”. Độ phức tạp được xác định bằng hai độ đo: độ phức tạp thông báo và độ phức tạp thời gian. Độ phức tạp thông báo là số tối đa các thông báo gửi đi trong thực hiện thỏa đáng. Độ phức tạp thời gian là thời gian tối đa đến khi kết thúc trong thực hiện thỏa đáng. Với mô hình đồng bộ, độ phức tạp thời gian là số vòng tối đa. Với mô hình không đồng bộ, bộ đo dựa trên giả thiết thời gian xử lý sự kiện là không đơn vị và thời gian truyền thông báo (từ sự kiện gửi đến sự kiện xử lý thông báo) tối đa là một đơn vị. 1.5. Công nghệ tác tử di động 1.5.1. Sự tiến hóa Theo truyền thống, một ứng dụng phân tán có cấu trúc xây dựng trên mô hình client - server sẽ thực hiện việc giao tiếp thông qua cơ chế truyền thông điệp hoặc các lời gọi hàm từ xa (Remote Procedure Call – RPC). Trong mô hình REV (Remote Evaluation), thay vì yêu cầu thực hiện các hàm từ xa thì client chỉ việc gởi mã nguồn các hàm của nó đến server và yêu cầu server thực hiện rồi trả về kết quả. Tham số (dữ liệu) Client Server RPC Server REV Kết quả (dữ liệu) Hàm (mã nguồn) Client Kết quả (dữ liệu) Server - 1 Agent Code, data, context 2. agent di trú 1. agent gửi đi Client 4. agent di trú Server - 2 Mobile agents 3. agent di trú Server - 3 Hình 1.5.1-1. Sự tiến hóa của mô hình Mobile agents 15 Tác tử di động (Mobile Agent) là một trong những hướng nghiên cứu thu hút nhiều sự quan tâm nhất từ những năm 1990 đến nay, với những đặc điểm rất thích hợp cho việc phát triển các ứng dụng phân tán. Tác tử di động là một phần mềm tự trị có khả năng di chuyển trên mạng để thực hiện một công việc xác định. Khi di chuyển, các tác tử di động đóng gói mã nguồn, dữ liệu và cả trạng thái thi hành, nhờ vậy tác tử di động có thể dừng việc thi hành đang thực hiện tại máy này, di chuyển sang máy khác và khôi phục lại sự thi hành tại máy đích. Hình 1.5.1-1 minh họa sự tiến hóa của mô hình tác tử di động. 1.5.2. Các đặc tính của tác tử di động Tác tử di động có một số đặc tính quan trọng sau đây:  Tính tự trị (autonomous): Một tác tử có thể hoạt động không cần có sự can thiệp trực tiếp của người sử dụng.  Tính di động (mobility): Một tác tử có thể di chuyển từ nơi này đến nơi khác với các tình huống khác nhau.  Tính cộng tác (collaboration): Một tác tử có thể giao tác với tác tử khác hay với con người, để trao đổi tri thức, thông tin với nhau.  Tính thích ứng (reactiveness): Là khả năng của tác tử di động có thể thực thi trên những môi trường lạ.  Tính liên tục về mặt thời gian: Một tác tử có thể vừa di chuyển vừa xử lý công việc trên mạng hoặc có thể tiếp tục công việc tại vị trí mới.  Tính bền vững (durability): Một tác tử có thể được lưu lại tại bộ nhớ thứ cấp và có thể được gọi hoạt động trở lại sau. 1.5.3. Ứng dụng của tác tử di động Với các đặc tính như trên, mô hình tác tử di động có thể được sử dụng hiệu quả trong nhiều trường hợp khác nhau:  Tương tác dữ liệu thay cho người sử dụng: Các ứng dụng thường xuyên yêu cầu phản ứng ngay với các luồng dữ liệu thời gian thực, không cần phân biệt người sử dụng là ai và có mặt hay không.  Xử lý và tính toán song song: Các tính toán phức tạp được chia nhỏ thành nhiều đơn vị để phân tán trên các máy khác nhau, mỗi đơn vị giao cho một tác tử di động điều phối.  Làm việc trên mạng có độ tin cậy kém, bị ngắt kết nối: Trong trường hợp này có thể phục hồi mạng bằng cách di chuyển tác tử di động tới nguồn dữ liệu mới để thực hiện thay vì chỉ tập trung vào việc kết nối lại. 16  Thu thập thông tin phân tán: Tác tử di động thu thập thông tin ở các điểm nút khác nhau trong mạng.  Tìm kiếm và lọc thông tin: Tác tử di động có thể di chuyển tới các site, tìm kiếm và lọc ra những thông tin thật sự cần thiết.  Giám sát theo thời gian: Nhiều trường hợp thông tin tìm kiếm chưa có sẵn mà phải đợi đến thời điểm nó xuất hiện. Tác tử di động được tung đến điểm cần thiết, giám sát và chờ đợi để thu thập các thông tin theo yêu cầu.  Phân phát thông tin: Tác tử di động di chuyển trên mạng và phân phát các thông tin theo yêu cầu.  Thương lượng, đàm phán: Các tác tử di động có thể tương tác với nhau để thương lượng, đàm phán những vấn đề cụ thể. Ví dụ, thương lượng để tổ chức một cuộc họp.  Quản trị hệ thống mạng: Với các hệ thống mạng lớn, việc chẩn đoán lỗi, duy trì sự ổn định của hệ thống là các công việc rất khó khăn. Tác tử di động giúp cho các công việc chẩn đoán lỗi và duy trì từ xa sự ổn định của hệ thống được dễ dàng hơn.  Thương mại điện tử: Tác tử di động có thể thực hiện các hoạt động thương mại điện tử. Với các đặc tính và khả năng ứng dụng nêu trên, tác tử di động thực sự là một công cụ mạnh trong hệ phân tán. Trong chương 4, chúng ta sẽ trình bày mô hình phân tán có sự tham gia của các tác tử. Trên nền tảng đó, giải quyết bài toán truyền bá thông tin phân tán giữa các tác tử di động. 17 CHƯƠNG 2. BẦU THỦ LĨNH TRÊN MẠNG ĐẦY ĐỦ 2.1. Giới thiệu bài toán Bầu thủ lĩnh là một vấn đề cơ bản trong tính toán phân tán và đã được nghiên cứu trong các mô hình tính toán và các hình thái mạng với giả định khác nhau. Giải thuật bầu thủ lĩnh cho mạng n nút với định danh phân biệt, phải đưa mạng đến cấu hình kết thúc, mà ở đó có chính xác một nút được bầu là thủ lĩnh, và tất cả các nút khác trong mạng biết định danh của thủ lĩnh. Mọi mạng có hình trạng là một đồ thị liên thông đều có thể đưa về mạng phủ mà ở đó các nút được kết nối đầy đủ với nhau. Vì vậy, bầu thủ lĩnh trên mạng đầy đủ đã được nhiều tác giả nghiên cứu và thu được các kết quả khác nhau, [10] đề xuất một giải thuật cho mạng đầy đủ không cảm hướng với độ phức tạp thông báo O(n log n) và O(n /log n) thời gian, [4] đề xuất giải thuật cho mạng đầy đủ cảm hướng với độ phức tạp thông báo và thời gian đều là O(n), [9] đề xuất một giải thuật mạnh hơn cho mạng đầy đủ cảm hướng với độ phức tạp thông báo O(n) và O(log n) thời gian. Tuy nhiên các giải thuật ở trên đều yêu cầu mỗi nút biết tất cả các nút còn lại trong mạng, việc hiện thực hóa giả thiết này mất nhiều chi phí trong thực tế. Tác giả J. Villadangos và đồng sự [13] đã đề xuất giải thuật cho mạng đầy đủ không cần giả thiết về hướng, không đòi hỏi mỗi nút biết trước tất cả các nút trong hệ thống, chỉ giả định có một vòng ảo kết nối logic các nút trong hệ thống, mà vẫn đạt được độ phức tạp tuyến tính về thời gian và thông báo là O(n). Chương này sẽ mô tả chi tiết giải thuật của tác giả J. Villadangos và đồng sự. Xuất phát từ ý tưởng thiết kế giải thuật này, chúng ta sẽ thiết kế một giải thuật cho bài toán MAGP (Mobile Agent Gossip Problem) với giả thiết ban đầu về mạng yếu hơn giả thiết của các giải thuật cho mạng đầy đủ của tác giả Tomoko Suzuki và đồng sự [23,24], nhưng vẫn đạt được độ phức tạp di chuyển tối ưu hơn. 2.2. Mô hình tính toán phân tán Mạng là một đồ thị đầy đủ với các nút biểu diễn các bộ xử lý và các cạnh biểu diễn các kênh truyền thông hai chiều giữa các bộ xử lý. Thời gian truyền thông báo được giả thiết là hữu hạn nhưng không thể đoán trước. Chúng ta giả thiết các kênh truyền không bị mất mát thông báo cũng như ngắt thông báo. Tuy nhiên các thông báo có thể được sắp xếp lại. Chúng ta giả định có một vòng ảo kết nối logic các nút trong hệ thống theo một hướng nhất định. Các nút không biết toàn bộ định danh của các nút khác trong hệ thống, mỗi nút chỉ cần biết một nút kế tiếp trên vòng ảo. Trong bài toán bầu thủ lĩnh, ban đầu tất cả các nút ở trạng thái bị động. Một tập con bất kỳ các nút, thức dậy tự phát và bắt đầu giải thuật, và trở thành các nút ứng 18 viên. Các nút có thể bắt đầu giải thuật ở thời điểm khác nhau. Thủ lĩnh được xác định từ tập các nút ứng viên tại thời điểm giải thuật được khởi tạo. 2.3. Giải thuật bầu thủ lĩnh Villadangos Ý tưởng: Ban đầu, tập tất cả các nút ở trạng thái passive, các nút có thể tự phát bắt đầu giải thuật, các nút này là ứng viên có thể trở thành thủ lĩnh. Để thu gọn dần vòng bao gồm các nút ứng viên, chúng ta thiết lập cơ chế hợp tác giữa các ứng viên. Mỗi ứng viên gửi định danh của nó cho ứng viên kế tiếp trên vòng ảo, nút ở trạng thái passsive khi nhận được thông báo này, sẽ tự thiết lập trạng thái là dummy, và chuyển thông báo này đến nút kế tiếp trên vòng ảo. Ứng viên u có định danh lớn hơn ứng viên liền trước v, yêu cầu ứng viên v thông tin về ứng viên liền trước v, nút v sẽ thay đổi trạng thái của nó thành dummy, sau khi đã trả lời u về ứng viên liền trước nút v. Vậy, khi một ứng viên nhận được trả lời, nó biết định danh của ứng viên mới trước nó trên vòng ứng viên. Cuối cùng, ứng viên có định danh lớn nhất biết tất cả các nút trong hệ thống (ngoại trừ nó) ở trạng thái dummy, ứng viên này chính là thủ lĩnh. Trong giải thuật 2.3-1, biến statusi là trạng thái của nút i, cand_succi là ứng viên kế tiếp nút i, cand_predi là ứng viên liền trước nút i. Giải thuật được mô tả chi tiết dưới đây. Procedure initiatei begin if statusi = passive then statusi  candidate; cand_succi  NULL; cand_predi  NULL; send INF(i) to neighi; end if end Procedure rcvINFi(j, m) begin init = j; if statusi = passive then statusi  dummy; send INF(init) to neighi; end if