Luận văn thạc sĩ về truyền bá thông tin phân tán giữa các tác tử di động

Nghiên cứu hệ thống truyền bá thông tin phân tán giữa các tác tử di động, phương pháp định lượng kết hợp định tính, góp phần phát triển chuyên ngành

• Tác giả: Lê Trọng Hùng
• Người hướng dẫn: TS. Nguyễn Đại Thọ
• Trường học: Đại học Quốc gia Hà Nội
• Chuyên ngành: Công nghệ thông tin
• Đề tài: Truyền bá thông tin phân tán giữa các tác tử di động
• Loại tài liệu: luận văn thạc sĩ
• Năm xuất bản: 2008
• Địa điểm: Hà Nội

Mục lục chi tiết

• LỜI CAM ĐOAN
• 1. CHƯƠNG 1: GIỚI THIỆU TỔNG QUAN
• 1.1. Khái niệm hệ phân tán
• 1.2. Vai trò hệ phân tán
• 1.3. Đặc trưng hệ phân tán
• 1.4. Mô hình truyền thông báo
• 1.5. Công nghệ tác tử di động
• 2. CHƯƠNG 2: GIẢI THUẬT BẦU THỦ LĨNH TRÊN MẠNG ĐẦY ĐỦ
• 2.1. Giới thiệu bài toán
• 2.2. Mô hình tính toán phân tán
• 2.3. Giải thuật bầu thủ lĩnh Villadangos
• 3. CHƯƠNG 3: GIẢI THUẬT XÂY DỰNG CÂY KHUNG TỐI THIỂU
• 3.1. Bài toán cây khung tối thiểu
• 3.2. Giải thuật GHS83
• 3.3. Giải thuật SB95
• 4. CHƯƠNG 4: TRUYỀN BÁ THÔNG TIN PHÂN TÁN GIỮA CÁC TÁC TỬ DI ĐỘNG
• 4.1. Bài toán MAGP – Mobile Agent Gossip Problem
• 4.2. Một số khái niệm
• 4.3. Mối quan hệ giữa MAGP và NLEP
• 4.4. Hệ thống truyền thông báo
• 4.5. Mô phỏng một giải thuật truyền thông báo
• 4.6. Giải thuật hẹn gặp (Rendezvous Algorithm)
• 4.7. Các giải thuật cho MAGP
• 4.8. Mạng bất kỳ
• 4.9. Mạng đầy đủ không cảm hướng
• 4.10. Mạng đầy đủ cảm hướng
• 5. CHƯƠNG 5: GIẢI THUẬT ĐỀ XUẤT CHO MAGP TRÊN MẠNG ĐẦY ĐỦ
• 5.1. Phát biểu bài toán
• 5.2. Ý tưởng, cấu trúc dữ liệu
• 6. CHƯƠNG 6: GIẢI THUẬT ĐỀ XUẤT CHO MAGP TRÊN MẠNG BẤT KỲ
• 6.1. Phát biểu bài toán
• 6.2. Ý tưởng, cấu trúc dữ liệu
• TÀI LIỆU THAM KHẢO

Tóm tắt

I. Giới thiệu về truyền bá thông tin phân tán

Nghiên cứu truyền bá thông tin phân tán giữa các tác tử di động (MAGP) là một lĩnh vực đang thu hút sự quan tâm lớn trong cộng đồng nghiên cứu. Thông tin phân tán đề cập đến việc chia sẻ và truyền tải thông tin giữa các nút trong một mạng mà không cần một trung tâm điều khiển. Mỗi tác tử di động có khả năng tự động di chuyển và thực hiện nhiệm vụ, giúp giảm tải cho mạng và tăng cường tính linh hoạt. Mục tiêu chính của MAGP là đảm bảo rằng mỗi tác tử có thể thu thập thông tin từ tất cả các tác tử khác trong mạng. Điều này không chỉ giúp cải thiện hiệu suất của hệ thống mà còn tạo ra một môi trường giao tiếp hiệu quả hơn giữa các tác tử.

1.1. Khái niệm và vai trò của tác tử di động

Tác tử di động là một chương trình tự trị có khả năng di chuyển qua mạng và thực hiện nhiệm vụ tại mỗi nút. Công nghệ di động cho phép các tác tử này hoạt động độc lập, giảm thiểu tải cho mạng và tối ưu hóa quy trình truyền tải thông tin. Việc sử dụng tác tử di động trong hệ thống phân tán không chỉ giúp cải thiện hiệu suất mà còn tạo ra các ứng dụng linh hoạt hơn, có khả năng thích nghi với các điều kiện thay đổi trong môi trường mạng.

II. Mô hình truyền thông báo trong hệ phân tán

Mô hình truyền thông báo là một phương pháp quan trọng trong việc giao tiếp giữa các bộ xử lý trong hệ thống phân tán. Mỗi bộ xử lý gửi và nhận thông báo qua các kênh truyền thông, tạo thành một mạng lưới giao tiếp. Tô pô của hệ thống được biểu diễn bằng đồ thị, trong đó mỗi nút là một bộ xử lý và mỗi cạnh là một kênh truyền thông. Điều này cho phép các bộ xử lý tương tác với nhau một cách hiệu quả, đảm bảo rằng thông tin được truyền tải một cách nhanh chóng và chính xác. Giải thuật truyền thông báo cung cấp khả năng cho các bộ xử lý thực hiện tính toán cục bộ và gửi thông báo đến các hàng xóm của nó, từ đó tạo ra một mạng lưới thông tin phong phú.

2.1. Đặc điểm của hệ thống truyền thông báo

Hệ thống truyền thông báo có một số đặc điểm nổi bật như không có đồng hồ chung, không có bộ nhớ toàn cục và không có cơ chế phát hiện sự cố chính xác. Điều này tạo ra những thách thức trong việc thiết kế các giải thuật hiệu quả cho việc truyền tải thông tin. Các bộ xử lý cần phải phối hợp hành động với nhau để đạt được mục tiêu chung, đồng thời phải có khả năng xử lý các thông báo một cách linh hoạt và hiệu quả. Việc xây dựng các giải thuật truyền thông báo cần phải xem xét đến các yếu tố này để đảm bảo tính khả thi và hiệu suất của hệ thống.

III. Giải thuật cho bài toán MAGP

Bài toán MAGP được giải quyết thông qua nhiều giải thuật khác nhau, trong đó có giải thuật hẹn gặp và các giải thuật bầu thủ lĩnh. Giải thuật hẹn gặp yêu cầu tất cả các tác tử phải gặp nhau tại một nút cụ thể để trao đổi thông tin. Tuy nhiên, phương pháp này có thể gặp khó khăn trong việc xác định thời điểm và vị trí hẹn gặp. Để khắc phục điều này, các tác giả đã đề xuất giải thuật bầu thủ lĩnh, trong đó một tác tử được bầu làm thủ lĩnh để thu thập và truyền bá thông tin cho các tác tử khác. Giải thuật này không chỉ giúp giảm thiểu độ phức tạp trong việc giao tiếp mà còn nâng cao hiệu quả truyền tải thông tin trong mạng.

3.1. Các giải thuật bầu thủ lĩnh

Giải thuật bầu thủ lĩnh được phát triển dựa trên ý tưởng của các giải thuật truyền thông báo, cho phép một tác tử duyệt toàn mạng để thu thập thông tin. Các giải thuật này đã được áp dụng cho nhiều loại mạng khác nhau, bao gồm mạng cây không biết gốc, mạng đầy đủ không cảm hướng và mạng đầy đủ cảm hướng. Mỗi giải thuật đều có những ưu điểm và nhược điểm riêng, tuy nhiên, mục tiêu chung vẫn là tối ưu hóa quá trình truyền tải thông tin giữa các tác tử. Việc nghiên cứu và phát triển các giải thuật này không chỉ có giá trị lý thuyết mà còn có ứng dụng thực tiễn trong các hệ thống phân tán hiện đại.

IV. Đánh giá và ứng dụng thực tiễn

Nghiên cứu về truyền bá thông tin phân tán giữa các tác tử di động không chỉ mang lại những hiểu biết sâu sắc về cách thức hoạt động của các hệ thống phân tán mà còn mở ra nhiều cơ hội ứng dụng thực tiễn. Các giải thuật được phát triển có thể được áp dụng trong nhiều lĩnh vực như quản lý mạng, truyền thông không dây, và các hệ thống IoT. Việc tối ưu hóa quá trình truyền tải thông tin giúp cải thiện hiệu suất của hệ thống, đồng thời giảm thiểu chi phí và thời gian xử lý. Điều này đặc biệt quan trọng trong bối cảnh hiện nay, khi mà nhu cầu về thông tin và dữ liệu ngày càng tăng cao.

4.1. Tính ứng dụng trong thực tiễn

Các giải thuật truyền bá thông tin phân tán có thể được áp dụng trong nhiều lĩnh vực khác nhau, từ quản lý mạng đến các ứng dụng trong IoT. Việc sử dụng công nghệ di động trong các hệ thống này không chỉ giúp cải thiện hiệu suất mà còn tạo ra các ứng dụng linh hoạt hơn, có khả năng thích nghi với các điều kiện thay đổi trong môi trường mạng. Điều này cho thấy giá trị thực tiễn của nghiên cứu này, không chỉ trong lý thuyết mà còn trong ứng dụng thực tế.

Nội dung chính

Tổng quan nghiên cứu

Trong bối cảnh sự phát triển mạnh mẽ của Internet và các công nghệ truyền thông, nhu cầu trao đổi và truyền bá thông tin phân tán ngày càng trở nên thiết yếu. Theo ước tính, số lượng người sử dụng mạng và các dịch vụ phân tán đã tăng lên hàng triệu, đòi hỏi các giải pháp truyền thông hiệu quả, đặc biệt trong các hệ thống phân tán. Bài toán 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 sự quan tâm của nhiều học giả. Mục tiêu của MAGP là làm sao để mỗi tác tử trong mạng thu thập được thông tin của tất cả các tác tử còn lại, trong khi mỗi tác tử chỉ có thông tin riêng ban đầu và không biết trước số lượng tác tử hay cấu trúc mạng.

Nghiên cứu tập trung vào việc phát triển các giải thuật truyền bá thông tin phân tán hiệu quả, giảm thiểu độ phức tạp di chuyển và thời gian thực hiện. Phạm vi nghiên cứu bao gồm các mạng bất kỳ, mạng đầy đủ không cảm hướng và mạng đầy đủ cảm hướng, với các giả thiết về cấu trúc mạng và khả năng di chuyển của tác tử. Ý nghĩa của nghiên cứu được thể hiện qua việc nâng cao hiệu suất truyền thông trong các hệ phân tán, hỗ trợ các ứng dụng như quản trị mạng, thu thập dữ liệu phân tán, và các dịch vụ thương mại điện tử.

Cơ sở lý thuyết và phương pháp nghiên cứu

Khung lý thuyết áp dụng

Nghiên cứu dựa trên các lý thuyết và mô hình sau:

• Hệ phân tán và mô hình truyền thông báo: Mạng được mô hình hóa như một đồ thị vô hướng, trong đó các nút là bộ xử lý và các cạnh là kênh truyền thông hai chiều. Mô hình truyền thông báo cho phép các bộ xử lý gửi và nhận thông báo không đồng bộ, với các điều kiện an toàn và sống động đảm bảo tính đúng đắn của hệ thống.

• Công nghệ tác tử di động (Mobile Agent): Tác tử di động là 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 các nút. Các đặc tính chính bao gồm tính tự trị, di động, cộng tác, thích ứng và bền vững. Tác tử di động giúp giảm tải mạng và tăng tính linh hoạt trong các hệ phân tán.

• Giải thuật bầu thủ lĩnh (Leader Election): Giải thuật bầu thủ lĩnh Villadangos và đồng sự được áp dụng trên mạng đầy đủ với giả thiết tồn tại một vòng ảo kết nối logic các nút. Giải thuật đạt độ phức tạp tuyến tính O(n) về thời gian và thông báo, không yêu cầu mỗi nút biết toàn bộ các nút khác trong mạng.

• Giải thuật xây dựng cây khung tối thiểu (Minimum Spanning Tree - MST): Hai giải thuật phân tán tiêu biểu là GHS83 và SB95 được sử dụng để xây dựng cây khung tối thiểu trong mạng không đồng bộ. GHS83 có độ phức tạp thời gian O(N log N) và thông báo O(|E| + N log N), trong khi SB95 tối ưu thời gian xuống O(N) nhưng có thể có độ phức tạp thông báo lên đến O(N²) trong trường hợp xấu nhất.

• Mối quan hệ giữa MAGP và NLEP: Hai bài toán này có thể quy về nhau, cho phép sử dụng các kết quả và giải thuật từ bài toán bầu thủ lĩnh để 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.

Phương pháp nghiên cứu

Nghiên cứu sử dụng phương pháp phân tích và thiết kế giải thuật dựa trên mô hình hệ tác tử di động trong mạng phân tán. Cụ thể:

• Nguồn dữ liệu: Dữ liệu mô phỏng các mạng phân tán với số nút N và số tác tử k khác nhau, cùng các cấu trúc mạng đa dạng như mạng đầy đủ, mạng bất kỳ.

• Phương pháp chọn mẫu: Mạng được giả định là đồ thị vô hướng liên thông, các tác tử được khởi tạo ngẫu nhiên trên các nút khác nhau, không quá một tác tử trên một nút.

• Phương pháp phân tích: Thiết kế và mô phỏng các giải thuật truyền bá thông tin phân tán, đánh giá độ phức tạp di chuyển và thời gian thực hiện. So sánh hiệu quả giữa giải thuật đề xuất và các giải thuật gốc như giải thuật hẹn gặp, giải thuật bầu thủ lĩnh Villadangos, giải thuật GHS83 và SB95.

• Timeline nghiên cứu: Nghiên cứu được thực hiện trong khoảng thời gian từ năm 2007 đến 2008, với các giai đoạn thiết kế giải thuật, mô phỏng, chứng minh tính đúng đắn và đánh giá hiệu năng.

Kết quả nghiên cứu và thảo luận

Những phát hiện chính

1. Giải thuật đề xuất cho MAGP trên mạng bất kỳ: Giải thuật chi tiết được xây dựng dựa trên ý tưởng của Tomoko Suzuki và đồng sự, cải tiến từ giải thuật xây dựng cây khung SB95. Giải thuật không sử dụng số hiệu mức, cho phép sát nhập các mảnh ngay khi tìm được liên kết ngoài có trọng số tối thiểu, tăng tốc độ hội tụ. Độ phức tạp thời gian đạt O(N + |E|), tối ưu hơn so với giải thuật gốc có độ phức tạp O(N log k + |E|).

2. Độ phức tạp di chuyển: Trong trường hợp xấu nhất, độ phức tạp di chuyển của giải thuật đề xuất là O(Nk + |E|). 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, độ phức tạp giảm còn O(N log k + |E|).

3. Giải thuật đề xuất cho MAGP trên mạng đầy đủ: Vận dụng ý tưởng giải thuật bầu thủ lĩnh Villadangos, giải thuật không cần giả thiết cảm hướng và không yêu cầu mỗi nút biết toàn bộ các nút khác trong mạng. Độ phức tạp bước di chuyển được cải thiện so với giải thuật gốc, đạt hiệu quả cao trong thực tế.

4. So sánh hiệu năng: Bảng so sánh cho thấy giải thuật đề xuất có độ phức tạp thời gian và di chuyển thấp hơn đáng kể so với các giải thuật truyền thống như giải thuật hẹn gặp và giải thuật của Tomoko Suzuki. Ví dụ, độ phức tạp thời gian giảm từ O(N log k + |E|) xuống O(N + |E|), giúp tăng tốc độ truyền bá thông tin trong mạng lớn.

Thảo luận kết quả

Nguyên nhân chính của sự cải tiến là việc loại bỏ số hiệu mức trong quá trình sát nhập các mảnh, cho phép các mảnh kết hợp ngay khi tìm được liên kết ngoài tối thiểu, thay vì phải chờ đợi như trong giải thuật GHS83. Điều này làm giảm đáng kể thời gian hội tụ và số bước di chuyển của tác tử.

So với các nghiên cứu trước, giải thuật đề xuất không chỉ tối ưu về mặt thời gian mà còn giảm thiểu chi phí di chuyển, phù hợp với các mạng có cấu trúc phức tạp và số lượng tác tử lớn. Việc áp dụng giải thuật bầu thủ lĩnh Villadangos trong mạng đầy đủ cũng giúp giảm yêu cầu về kiến thức mạng của các nút, từ đó giảm chi phí triển khai thực tế.

Dữ liệu mô phỏng có thể được trình bày qua biểu đồ so sánh độ phức tạp thời gian và di chuyển giữa các giải thuật, cũng như bảng tổng hợp các chỉ số hiệu năng chính. Điều này giúp minh họa rõ ràng sự vượt trội của giải thuật đề xuất trong các kịch bản mạng khác nhau.

Đề xuất và khuyến nghị

1. Triển khai giải thuật đề xuất trong các hệ thống phân tán thực tế: Các tổ chức phát triển mạng phân tán nên áp dụng giải thuật MAGP đề xuất để nâng cao hiệu quả truyền bá thông tin, giảm thiểu độ trễ và chi phí di chuyển tác tử. Thời gian triển khai dự kiến trong vòng 6-12 tháng.

2. Tối ưu hóa thêm các bước di chuyển của tác tử: Nghiên cứu tiếp tục phát triển các kỹ thuật tối ưu hóa bước di chuyển, như giảm số lần di chuyển không cần thiết hoặc sử dụng các chiến lược định tuyến thông minh. Mục tiêu giảm thêm 20-30% chi phí di chuyển trong vòng 1 năm.

3. Mở rộng giải thuật cho các mô hình mạng phức tạp hơn: Nghiên cứu áp dụng giải thuật cho các mạng có tính chất động, mạng không đồng bộ hoặc mạng có lỗi, nhằm tăng tính bền vững và khả năng kháng lỗi. Chủ thể thực hiện là các nhóm nghiên cứu trong lĩnh vực mạng máy tính, thời gian nghiên cứu 1-2 năm.

4. Phát triển công cụ mô phỏng và đánh giá hiệu năng: Xây dựng phần mềm mô phỏng các giải thuật truyền bá thông tin phân tán để đánh giá hiệu quả trong các kịch bản thực tế, hỗ trợ các nhà phát triển và nhà nghiên cứu. Thời gian phát triển dự kiến 6 tháng.

Đối tượng nên tham khảo luận văn

1. Nhà nghiên cứu và sinh viên ngành Công nghệ Thông tin, Mạng máy tính: Luận văn cung cấp kiến thức sâu sắc về các giải thuật truyền thông phân tán, giúp nâng cao hiểu biết và phát triển các nghiên cứu tiếp theo.

2. Kỹ sư phát triển hệ thống phân tán và mạng: Các kỹ sư có thể áp dụng giải thuật đề xuất để tối ưu hóa hiệu suất truyền thông trong các hệ thống phân tán thực tế, đặc biệt trong các ứng dụng thu thập dữ liệu và quản trị mạng.

3. Chuyên gia quản trị mạng và bảo mật: Hiểu rõ cơ chế truyền bá thông tin giữa các tác tử di động giúp cải thiện các giải pháp giám sát, chẩn đoán lỗi và bảo mật trong mạng phân tán.

4. Doanh nghiệp phát triển ứng dụng phân tán và thương mại điện tử: Áp dụng các giải thuật truyền bá thông tin hiệu quả giúp nâng cao chất lượng dịch vụ, giảm chi phí vận hành và tăng tính linh hoạt trong các ứng dụng thương mại điện tử phân tán.

Câu hỏi thường gặp

1. MAGP là gì và tại sao nó quan trọng?
   MAGP (Mobile Agent Gossip Problem) là bài toán truyền bá thông tin phân tán giữa các tác tử di động, nhằm đảm bảo mỗi tác tử biết thông tin của tất cả các tác tử khác. Đây là nền tảng cho nhiều ứng dụng phân tán như quản trị mạng và thu thập dữ liệu.

2. Giải thuật bầu thủ lĩnh Villadangos có điểm gì nổi bật?
   Giải thuật này không yêu cầu mỗi nút biết toàn bộ các nút khác trong mạng mà chỉ cần biết nút kế tiếp trên vòng ảo, đạt độ phức tạp tuyến tính O(n) về thời gian và thông báo, phù hợp với mạng đầy đủ không cảm hướng.

3. Sự khác biệt chính giữa giải thuật GHS83 và SB95 là gì?
   GHS83 sử dụng số hiệu mức để kiểm soát sát nhập mảnh, dẫn đến độ phức tạp thời gian O(N log N). SB95 loại bỏ số hiệu mức, cho phép sát nhập ngay khi tìm được cạnh ngoài tối thiểu, tối ưu thời gian xuống O(N) nhưng có thể tăng độ phức tạp thông báo.

4. Giải thuật đề xuất cải thiện gì so với các giải thuật trước?
   Giải thuật đề xuất giảm độ phức tạp thời gian xuống O(N + |E|), tối ưu hóa bước di chuyển tác tử, không cần giả thiết cảm hướng trong mạng đầy đủ, và không yêu cầu mỗi nút biết toàn bộ mạng, giúp tăng hiệu quả và tính khả thi trong thực tế.

5. Làm thế nào để đánh giá hiệu quả của các giải thuật truyền bá thông tin?
   Hiệu quả được đánh giá qua độ phức tạp thời gian, độ phức tạp di chuyển (số bước di chuyển của tác tử), và số lượng thông báo gửi đi. Mô phỏng và phân tích lý thuyết giúp so sánh các giải thuật trong các kịch bản mạng khác nhau.

Kết luận

• Luận văn đã phát triển giải thuật truyền bá thông tin phân tán giữa các tác tử di động với độ phức tạp thời gian và di chuyển được tối ưu hóa rõ rệt so với các giải thuật truyền thống.
• Giải thuật đề xuất cho mạng bất kỳ dựa trên cải tiến từ giải thuật xây dựng cây khung SB95, đạt độ phức tạp thời gian O(N + |E|).
• Giải thuật cho mạng đầy đủ vận dụng ý tưởng bầu thủ lĩnh Villadangos, không cần giả thiết cảm hướng và giảm chi phí di chuyển tác tử.
• Nghiên cứu chứng minh tính đúng đắn và hiệu quả của giải thuật qua phân tích lý thuyết và mô phỏng, mở ra hướng phát triển cho các hệ thống phân tán hiện đại.
• Các bước tiếp theo bao gồm tối ưu hóa thêm bước di chuyển, mở rộng cho các mô hình mạng phức tạp hơn và phát triển công cụ mô phỏng hỗ trợ triển khai thực tế.

Hành động ngay hôm nay: Các nhà nghiên cứu và kỹ sư mạng nên áp dụng và thử nghiệm giải thuật đề xuất để nâng cao hiệu quả truyền thông trong hệ thống phân tán của mình.

Trích đoạn nội dung tài liệu

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.

z 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. 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.

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. z 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. Đặ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. 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ộ z 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  .