Tài liệu Nghiên cứu vấn đề truyền bá thông tin giữa các tác tử di động trong mạng động

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ PHAN ĐA PHÚC NGHIÊN CỨU VẤN ĐỀ TRUYỀN BÁ THÔNG TIN GIỮA CÁC TÁC TỬ DI ĐỘNG TRONG MẠNG ĐỘNG LUẬN VĂN THẠC SĨ Hà Nội - 2010 ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ PHAN ĐA PHÚC NGHIÊN CỨU VẤN ĐỀ TRUYỀN BÁ THÔNG TIN GIỮA CÁC TÁC TỬ DI ĐỘNG TRONG MẠNG ĐỘNG Ngành: Chuyên ngành: Mã số: Công nghệ thông tin Truyền dữ liệu và mạng máy tính 60.48.15 LUẬN VĂN THẠC SĨ NGƯỜI HƯỚNG DẤN KHOA HỌC: TS. Nguyễn Đại Thọ Hà Nội - 2010 1 MỤC LỤC MỞ ĐẦU ..........................................................................................................................................2 CHƯƠNG 1. GIỚI THIỆU MÔ HÌNH TÁC TỬ DI ĐỘNG TRONG HỆ PHÂN TÁN ................5 1.1. Hệ phân tán........................................................................................................................... 5 1.1.1. Khái niệm hệ phân tán. .................................................................................................. 5 1.1.2. Ưu, nhược ñiểm của hệ phân tán ................................................................................... 6 1.1.3. Đặc trưng hệ phân tán.................................................................................................... 7 1.1.4. Ứng dụng hệ phân tán.................................................................................................... 7 1.2. Các mô hình xử lý trong hệ phân tán.................................................................................... 8 1.2.1. Mô hình truyền thông báo ............................................................................................. 8 1.2.2. Mô hình tác tử di ñộng ................................................................................................ 11 1.2.3. Giải thuật chuyển ñổi từ mô hình thông báo sang mô hình tác tử............................... 13 1.3. Phân loại mô hình tác tử di ñộng........................................................................................ 17 CHƯƠNG 2. TRUYỀN BÁ THÔNG TIN GIỮA CÁC TÁC TỬ TRONG MẠNG ĐỘNG........20 2.1. Bài toán truyền bá thông tin giữa các tác tử ....................................................................... 20 2.2. Một số giải thuật cho bài toán truyền bá thông tin ............................................................. 22 2.2.1. Giải thuật hẹn gặp (rendezvous algorithm) ................................................................. 22 2.2.2. Giải thuật bầu thủ lĩnh ................................................................................................. 23 2.3. Vấn ñề truyền bá thông tin trong mạng ñộng ..................................................................... 26 2.3.1. Sự khác nhau giữa mạng tĩnh và mạng ñộng............................................................... 26 2.3.2. Đánh giá ñộ phức tạp của các thuật toán trong mạng ñộng......................................... 29 CHƯƠNG 3. XÂY DỰNG CÂY KHUNG TỐI THIỂU TRONG HỆ PHÂN TÁN.....................35 3.1. Mô tả bài toán ..................................................................................................................... 35 3.2. Giải thuật GHS-83 .............................................................................................................. 36 3.2.1. Tư tưởng của giải thuật................................................................................................ 36 3.2.2. Giải thuật chi tiết ......................................................................................................... 38 3.3. Giải thuật bảo toàn cây khung trong mạng ñộng (OMST) ................................................. 44 3.3.1. Khái quát về giải thuật................................................................................................. 44 3.3.2. Tư tưởng của giải thuật OMST. .................................................................................. 45 3.3.3. Chi tiết giải thuật OMST ............................................................................................. 49 3.3.4. Tính ñúng ñắn của giải thuật ....................................................................................... 55 CHƯƠNG 4. ĐỀ XUẤT MỘT SỐ GIẢI THUẬT GIẢI QUYẾT BÀI TOÁN ............................57 4.1. Cấu trúc dữ liệu .................................................................................................................. 57 4.2. Giải thuật duyệt toàn mạng................................................................................................. 58 4.2.1. Tư tưởng của giải thuật: .............................................................................................. 58 4.2.2. Đánh giá giải thuật....................................................................................................... 62 4.3. Giải thuật dựa trên bài toán xây dựng cây khung tĩnh........................................................ 62 4.3.1. Tư tưởng của giải thuật................................................................................................ 62 4.3.2. Đánh giá giải thuật....................................................................................................... 66 4.4. Giải thuật dựa trên mô hình cây khung ñộng ..................................................................... 68 4.4.1. Tư tưởng của giải thuật................................................................................................ 68 4.4.2. Đánh giá giải thuật....................................................................................................... 72 KẾT LUẬN ....................................................................................................................................74 TÀI LIỆU THAM KHẢO ..............................................................................................................76 2 MỞ ĐẦU Công nghệ thông tin và viễn thông ngày càng phát triển, dẫn ñến những ñòi hỏi về vấn ñề xử lí thông tin ngày càng cao. Các hệ thống xử lý thông tin hiện nay cần phải ñáp ứng nhu cầu ngày càng lớn về việc tăng tốc ñộ tính toán. Tốc ñộ phát triển của phần cứng và phần mềm không ñáp ứng ñược, khiến nhiều hệ thống tập trung thông thường không còn phù hợp với các nhu cầu xử lý thực tế nữa. Vì vậy, những hệ thống phân tán có khả năng sử dụng ñồng thời nhiều máy tính cho việc giải quyết một bài toán hiện ñang là một hướng phát triển mới nhiều tiềm năng. Nhờ sự kết hợp các máy tính thông thường, ñơn lẻ lại, hệ thống phân tán không những tăng ñược tốc ñộ xử lý lên nhiều lần, mà còn giảm ñược chi phí ñầu tư so với các hệ thống tập trung truyền thống. Các hệ thống phân tán hiện nay có khả năng ứng dụng trong rất nhiều lĩnh vực khác nhau, từ y tế, giáo dục ñến thiên văn học, ... Bằng cách tận dụng tốt sức mạnh và tài nguyên của tất cả các máy tính trong hệ thống, hệ phân tán hứa hẹn mang lại những thành tựu ñột phá hơn nữa trong tương lai. Các ứng dụng phân tán hiện nay có thể cài ñặt thông qua nhiều mô hình khác nhau. Một trong những mô hình tốt, phù hợp và có nhiều ưu ñiểm là mô hình tác tử di ñộng. Tác tử di ñộng là các chương trình tự trị có thể di cư từ một nút sang một nút khác trong mạng, duyệt hệ thống ñể thực hiện nhiệm vụ trên các nút mà nó di chuyển tới. Mô hình này ñang ñược phát triển nhằm thay thế mô hình truyền thông báo trong tương lai. Với tính thích nghi và tính linh ñộng của mình, các tác tử di ñộng có thể làm ñơn giản hóa việc thiết kế các hệ thống phân tán. Các nút trong hệ thống giờ ñây không cần phải cài ñặt các phần mềm phân tán phức tạp nữa, do các tác tử khi di chuyển ñã mang theo cả mã nguồn của mình ñến nút ñích. Mô hình tác tử hiện nay ñã ñược sử dụng trong một số hệ phân tán cụ thể. Ví dụ như trong hệ thống quản lý mạng, các tác tử di ñộng ñược sử dụng ñể cải tiến hiệu năng hệ thống. Mỗi tác tử sẽ thực hiện việc duyệt trên mạng, thu thập thông tin tải của các nút, các liên kết và thông báo cho mỗi nút về thông tin này. Trong mô hình tác tử di ñộng, mỗi tác tử là một thực thể ñộc lập, vì vậy việc giao tiếp với nhau giữa các tác tử luôn là một vấn ñề quan trọng. Các tác tử trong quá trình thực hiện các tác vụ của mình, có thể phải cần thông tin từ những tác tử khác. Ví dụ như trong các mạng sensor, khi các tác tử thu thập ñược thông tin từ môi trường, cần phải trao ñổi thông tin với những tác tử lân cận nhằm tăng tính chính xác trong việc xử lý. Để giải quyết vấn ñề này, cần phải nghiên cứu những bài toán tương tác giữa các tác tử trong hệ thông. Và một trong những bài toán quan trong nhất là bài toán truyền bá thông tin giữa các tác tử. Trong bài toán này, mỗi tác tử ñược giả ñịnh có một thông tin riêng. Và yêu 3 cầu sau một số thực hiện, mỗi tác tử phải thu thập ñược thông tin của tất cả các tác tử khác trong hệ thống. Bài toán truyền bá thông tin giữa các tác tử trong mạng tĩnh ñã ñược nghiên cứu bởi khá nhiều các tác giả. Mạng tĩnh là mạng tối ưu trên lý thuyết, trên mạng này không có sự thay ñổi về hình trạng theo thời gian. Đây là loại mạng thường ñược sử dụng trong việc nghiên cứu giải thuật, do tính ñơn giản của nó. Một số giải thuật tương ñối hiệu quả cho bài toán truyền thông tin ñã ñược ñưa ra cho dạng mạng tĩnh này như giải thuật hẹn gặp hoặc giải thuật bầu thủ lĩnh [22]. Độ phức tạp của những giải thuật này cũng ñã ñược tối ưu hóa, và gần như không thể cải tiến thêm ñược nữa. Tuy nhiên, các hệ thống trên thực tế không phải lúc nào cũng ñạt ñược sự ổn ñịnh như mô hình lý thuyết. Sự thay ñổi topo mạng thực tế diễn ra thường xuyên, khi có những nút rời bỏ hoặc tham gia vào hệ thống. Vì vậy, các thuật toán trên mạng tĩnh tương ñối khó sử dụng trong các hệ thống thực. Do ñó, trong luận văn này, tôi xin tập trung vào nghiên cứu một vấn ñề khá mới, ñó là bài toán truyền bá thông tin giữa các tác tử trong mạng ñộng. Hiện nay, chỉ mới có nhóm tác giả T. Masuzawa và S. Tixeuil là tiến hành nghiên cứu một mô hình chung về vấn ñề này [21]. Các tác giả ñã ñưa ra những ñánh giá về ñộ phức tạp của bài toán trong những mô hình mạng ñộng khác nhau. Tuy nhiên, bài báo chưa ñánh giá ñược hết các ñộ phức tạp khác trong mô hình tác tử trong mạng ñộng, ñồng thời chưa có những giải thuật cụ thể trong mô hình này. Luận văn này sẽ trình bày một số nghiên cứu về vấn ñề truyền bá thông tin giữa các tác tử trong mạng ñộng, và ñề xuất hai giải thuật cải tiến cho vấn ñề này. Hai giải thuật này sẽ ñược chứng minh cụ thể cũng như ñưa ra những ñánh giá về ñộ phức tạp theo những tiêu chí khác nhau. Luận văn ñược chia làm 4 chương như sau: Chương 1: Các thông tin tổng quan về hệ phân tán, và mô hình tác tử trong hệ phân tán. Chương này giúp người ñọc có khái niệm chung về mô hình lý thuyết ñược sử dụng trong các chương sau. Chương 2: Giới thiệu về bài toán truyền bá thông tin trong mạng tĩnh và mạng ñộng. Trong chương này sẽ ñề cập ñến một số giải thuật trong mạng tĩnh cũng như phân tích sự khác biệt của bài toán trong hai dạng mạng này. Chương 3: Đề cập ñến bài toán xây dựng cây khung tối thiệu trong hệ phân tán. Chương này cũng ñưa ra hai giải thuật xây dựng cây khung, 1 giải thuật cho mạng tĩnh và một cho mạng ñộng. Đây là hai giải thuật rất quan trọng, liên quan trực tiếp ñến các giải thuật sẽ ñược ñề xuất trong chương 4. 4 Chương 4: Giới thiệu về giải thuật ñơn giản nhất cho bài toán trong mạng ñộng, ñồng thời ñề xuất hai giải thuật cải tiến. Hai giải thuật này có thể giảm ñược ñộ phức tạp di chuyển của tác tử nhờ vào việc xây dựng cây khung trong mạng. Các chứng minh về tính ñúng ñắn cũng như ñộ phức tạp của giải thuật cũng ñược ñưa ra một cách chi tiết. 5 CHƯƠNG 1. GIỚI THIỆU MÔ HÌNH TÁC TỬ DI ĐỘNG TRONG HỆ PHÂN TÁN 1.1. Hệ phân tán 1.1.1. Khái niệm hệ phân tán. Hiện nay, trên thế giới có khá nhiều những ñịnh nghĩa khác nhau về hệ phân tán. Ví dụ: một ñịnh nghĩa về hệ phân tán là “tập hợp các máy tính tự trị, ñược kết nối với nhau bởi một mạng máy tính và ñược cài ñặt phần mềm hệ phân tán”. Hoặc chúng ta có thể coi hệ phân tán là “một tập các máy tính ñộc lập, giao tiếp với người dùng như một hệ thống thống nhất toàn vẹn”. Tuy nhiên, khái niệm chính xác và tổng quá nhất về hệ phân tán là: “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”. Như vậy, các ñối tượng trong hệ phân tán không nhất thiết phải là máy tính, mà có thể chỉ là các chíp xử lý, các thành phần trong một bộ ña xử lý, các mạng cục bộ và Internet. Như vậy, mục ñích chính của hệ phân tán là phối hợp hoạt ñộng của nhiều loại thiết bị ñộc lập hoặc bán ñộc lập nhằm chia sẻ tài nguyên, ñảm bảo tính kháng lỗi và tính sẵn sàng cho hệ thống. Bộ nhớ cục bộ Bộ xử lý Bộ nhớ cục bộ Bộ xử lý Bộ nhớ cục bộ Bộ xử lý network Hình 1. Hệ phân tán Ngày nay, hệ phân tán ñược ứng dụng trong rất nhiều lĩnh vực khác nhau, như giáo dục, y tế, quốc phòng... Nhờ ưu ñiểm là khả năng phối hợp các bộ xử lý ñộc lập, hệ phân 6 tán có thể ñược sử dụng ñể giải quyết các bài toán phức tạp, mà nếu chỉ sử dụng một máy tính thì không thể thực hiện ñược. Trên thế giới hiện có khá nhiều dự án ñã sử dụng mô hình tính toán phân tán này. Ví dụ, như dự án SETI@home, với ý tưởng sử dụng thời gian rỗi của các máy tính cá nhân kết nối vào mạng Internet ñể tìm kiếm các nền văn minh ngoài Trái Đất. Đây là một phần của dự án SERENDIP (Search for Extraterrestrial Radio Emissions from Nearby Developed Intelligent Populations) của ñại học California, Berkeley (UC Berkeley), phân tích các kết quả quan sát của ñài thiên văn vô tuyến Arecibo. 1.1.2. Ưu, nhược ñiểm của hệ phân tán Hệ phân tán có rất nhiều ưu ñiểm so với các hệ thống tập trung: • Tiết kiệm chi phí: Do có thể sử dụng kết hợp nhiều máy tính trong quá trình lưu trữ và xử lý dữ liệu, nên trong các hệ phân tán không cần phải sử dụng những máy chủ mạnh và tốn kém. • Tăng tốc ñộ xử lý: Hiệu suất xử lý của hệ phân tán ñược nâng cao nhờ việc kết hợp sức mạnh xử lý của nhiều máy tính lại với nhau, vì vậy thường hệ phân tán có sức mạnh bằng nhiều máy tính cộng lại. • Độ tin cậy cao: Các bộ xử lý trong hệ phân tán làm việc hoàn toàn ñộc lập. Khi có một bộ xử lý bị lỗi hoặc ngừng làm việc, các bộ xử lý khác trong hệ thống vẫn hoạt ñộng bình thường • Khả năng mở rộng: Dễ dàng mở rộng hệ thống chỉ bằng cách thêm các bộ xử lý mới vào. • Khả năng chia sẻ tài nguyên: Các tài nguyên như dữ liệu hoặc các thiết bị ñắt tiền ñược dùng chung, dễ dàng cho nhiều người dùng trong hệ thống cùng truy nhập. • Khả năng truyền thông tin: Việc trao ñổi thông tin giữa nhiều người dùng trong hệ thống rất dễ dàng. Tuy nhiên, hệ phân tán cũng có một số nhược ñiểm. Các nhược ñiểm này liên quan ñến vấn ñề kỹ thuật, vì vậy có thể khắc phục ñược bằng những công nghệ và thuật toán mới • Nhược ñiểm về phần mềm: Việc thiết kế, xây dựng và cài ñặt phần mềm trong hệ phân tán khá phức tạp. • Nhược ñiểm về truyền thông mạng: Độ trễ hay việc mất mát dữ liệu trong ñường truyền mạng cũng là vấn ñề cần xử lý trong hệ phân tán 7 • Tính bảo mật: Nhiều người dùng và bộ xử lý tham gia vào hệ thống nên tính bảo mật không cao 1.1.3. Đặc trưng hệ phân tán Đặc ñiểm của hệ phân tán là phối hợp hoạt ñộng giữa các bộ xử lý bằng việc truyền thông tin (thường là truyền tin qua mạng). Vì vậy, hệ phân tán có một số các ñặng trưng sau ñây: • Có ñộ trễ truyền thông: Phải mất một khoảng thời gian ñể một sự kiện xảy ra trong hệ ảnh hưởng ñến toàn bộ hệ thống • Không có ñồng hồ chung: Do ñộ trễ truyền thông, nên không thể ñồng bộ hóa ñồng hồ của các bộ xử lý khác nhau. Vì vậy, người ta thường dùng khái niệm nhân quả thay cho ñồng hồ vật lý. • Không có bộ nhớ toàn cục: Các bộ xử lý có bộ nhớ cục bộ, nhưng không biết ñược trạng thái toàn cục của hệ thống. Vì vậy cần có 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. • 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.1.4. Ứng dụng hệ phân tán Hệ phân tán có rất nhiều ứng dụng trong thực tế: • Chia sẻ tải nguyên: Hệ phân tán kết nối các máy tính lại với nhau, vì vậy việc chia sẻ tài nguyên phần cứng và phần mềm trở nên rất dễ dàng. Người sử dụng có thể ngồi ở máy tính này, truy nhập và xử lý dữ liệu trong một máy tính khác cách hàng nghìn cây số. Hiện nay, hệ phân tán còn có thể kết nối các thiết bị ñiện tử di ñộng lại với nhau, tăng khả năng tương tác của người sử dụng. Các hệ cở sở dữ liệu phân tán ra ñời dựa trên ứng dụng này. Thông tin có thể ñược lưu trữ ở nhiều vị trí khác nhau, tăng ñộ an toàn của thông tin cũng như giảm hiện tượng thắt nút cổ chai trong quá trình truy nhập • Tính toán phân tán: Điển hình của ứng dụng này là mô hình tính toán lưới (Grid Computing). Nhờ sự kết hợp tốc ñộ xử lý của nhiều máy tính với nhau, mô hình 8 tính toán phân tán sẽ giúp tăng hiệu suất cũng như giảm chi phí ñầu tư cho toàn bộ hệ thống. 1.2. Các mô hình xử lý trong hệ phân tán Trong các hệ phân tán hiện nay, tồn tại hai mô hình xử lý và truyền thông tin giữa các bộ xử lý. Đó là “mô hình truyền thông báo” và “mô hình tác tử di ñộng” Mô hình truyền thông báo là mô hình truyền thống. Trong ñó, mỗi bộ xử lý sẽ cài ñặt một phần mềm phân tác cụ thể. Phần mềm này có trách nhiệm xử lý các sự kiện và giao tiếp với các bộ xử lý khác bằng việc gửi các thông báo qua kênh truyền. Đây chính là mô hình trao ñổi thông tin truyền thống trong các mạng máy tính. Ngoài ra, hiện nay còn một mô hình mới ñược sử dụng trong các hệ phân tán, “mô hình tác tử di ñộng (mobile agent)”. Điểm ñặc trưng của mô hình này là việc xử lý cũng như trao ñổi thông tin hoàn toàn do các tác tử ñảm nhiệm. Trong ñó, các tác tử là các chương trình tự trị, có khả năng di chuyển giữa các nút ñể tìm kiếm và xử lý thông tin. Như vậy, trong mô hình này các nút chỉ là những “ñiểm dừng” của các tác tử, hoàn toàn không ñóng vai trò gì trong vấn ñề xử lý. Mô hình tác tử di ñộng có một số ưu ñiểm khác so với mô hình truyền thông báo. Chúng ta sẽ lần lượt nghiên cứu cụ thể về từng mô hình ở phần tiếp theo. 1.2.1. Mô hình truyền thông báo Một hệ phân tán có thể ñược mô tả dưới dạng một ñồ thị vô hướng. Trong ñó, các bộ xử lý ñóng vai trò là các nút. Các kênh truyền giữa các bộ xử lý chính là các liên kết trong ñồ thị [1][22]. 1 p0 3 2 2 p3 1 p1 1 1 2 p2 Hình 2. Mô hình hệ phân tán 9 Như mô hình trên, hệ thống bao gồm 4 bộ xử lý ñược ký hiệu bởi 4 nút p0 ñến p3, và một số liên kết giữa các nút ñóng vai trò là kênh truyền dữ liệu. Lưu ý rằng trong hệ phân tán, các nút không biết ñược cấu hình cũng như trạng thái của toàn hệ thống. Mỗi nút chỉ biết ñược các liên kết kề nó và thường gán nhãn các liên kết theo thứ tự ñể phân biệt. Bậc của một nút p chính là số liên kết kề với nút ñó, thường ký hiệu là degp Trong mô hình truyền thông báo, các bộ xử lý có nhiệm vụ thực thi các chương trình (theo một giải thuật nào ñó) và 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. Giải thuật cho mô hình truyền thông báo bao gồm một chương trình cục bộ 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ừ các hàng xóm của nó. Tại mỗi bước trong quá trình thực hiện giải thuật phân tán, các bộ xử lý ñều có một trạng thái nhất ñịnh, là trạng thái của các biến trong bộ nhớ mỗi bộ xử lý. Mỗi trạng thái của bộ xử lý pi chứa 2 tập biến ñặc biệt, outbufi( l ) và inbufi( l ), với mọi l thỏa mãn 1 ≤ l ≤ degpi. Trong ñó, outbufi( l ) chứa các thông báo mà pi ñã gửi tới hàng xóm của nó qua kênh l , nhưng chưa ñến nơi, và inbufi( l ) chứa các thông báo nhận ñược trên kênh l , nhưng chưa xử lý. Tại trạng thái ban ñầu của mỗi bộ xử lý, inbufi( l ) là rỗng. Một số khái niệm thường ñược xử dụng trong mô hình truyền thông báo • Hàm chuyển (Transition function): có thể coi như một bước tính toán tại mỗi bộ xử lý. Hàm chuyển nhận ñầu vào là trạng thái (của bộ xử lý) không bao gồm các outbuf( l ), và ñầu ra là một trạng thái có inbuf( l ) rỗng. Như vậy các thông báo ñang chờ ñược chuyển ñi không ảnh hưởng ñến quá trình xử lý hiện tại. • 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 bộ xử lý pi. Các trạng thái của các biến outbuf trong một cấu hình thể hiện các thông báo ñang di chuyển qua các kênh truyền. Cấu hình ban ñầu là một vec tơ (q0 ,…, qn-1) với qi là trạng thái ban ñầu của bộ xử lý pi. Cấu hình chính là trạng thái của toàn bộ hệ thống • Sự kiện: với các hệ thống chuyể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 ñặc trưng của hệ thống bao gồm ñiều kiện an toàn và ñiều kiện sống ñộng. Trong ñó, ñ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. 10 Đ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. Để thuận tiện cho việc nghiên cứu các giải thuật trong mô hình truyền thông báo, người ta thường chia mô hình này sang làm 2 mô hình con, dựa trên ñặc trưng của hệ thống mạng: • Mô hình 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 trong các sự kiện, tức là không có giới hạn về thời gian từ lúc thông báo gửi ñi ñến lúc nhận ñược, hoặc giới hạn về thời gian thực hiện của bộ xử lý. 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. Trên thực tế, nếu hệ thống có cận thời gian cho mỗi sự kiện là lớn và không cố ñịnh thì chúng ta có thể coi là hệ thống không ñồng bộ, ví dụ mạng Internet. • 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. Hay nói cách khác, các bộ xử lý trong hệ thông thực hiện sự kiện tính và sự kiện giao trong một cận thời gian cố ñịnh, ñồng bộ với các bộ xử lý khác. 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. Mô hình này không thực tế nhưng khá thuận tiện trong việc thiết kế giải thuật vì loại bỏ ñược nhiều ñiểu không chắc chắn. Để ñánh giá hiệu suất của một giải thuật trong mô hình truyền thông báo, thông thường chúng ta sử dụng 2 ñộ ño là: ñộ phức tạp thông báo và ñộ phức tạp thời gian • Độ phức tạp thông báo (message complexity) là số tối ña các thông báo gửi ñi trong thực hiện thỏa ñáng. Một thuật toán có ñộ phức tạp thông báo thấp rất phù hợp với những mạng có băng thông nhỏ. Độ phức tạp thông báo áp dụng chung cho cả hệ thống ñồng bộ và không ñồng bộ • Độ phức tạp thời gian (time complexity) 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à 11 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.2.2. Mô hình tác tử di ñộng Mô tả một hệ thống phân tán dưới dạng một ñồ thị vô hướng G = (V, E), trong ñó V và E tương ứng là tập các nút và tập các cạnh của G, với các nút là các bộ xử lý, mỗi cạnh là một kênh truyền mà ở trên ñó hai bộ xử lý trong mạng có thể liên lạc trực tiếp với nhau. Liên kết giữa nút u và nút v ñược ký hiệu bởi euv hoặc evu. [1][22] Trong mô hình tác tử di ñộng, các bộ xử lý cũng như các liên kết chỉ ñóng vai trò như một bộ khung. Đối tượng thực sự làm nhiệm vụ xử lý cũng như truyền thông tin ñược gọi là các tác tử di ñộng (mobile agent). Mỗi tác tử là một chương trình tự trị có thể di cư từ một nút sang một nút khác trong mạng ñể xử lý cũng như thu thập và trao ñổi thông tin với nhau. Như vậy trong mô hình tác tử di ñộng, các bộ xử lý hoàn toàn ñộc lập so với các phần mềm phân tán. Để một bộ xử lý tham gia vào hệ thống, ta chỉ cần kết nối bộ xử lý ñó vào mạng, hoàn toàn không cần cài ñặt thêm phần mềm gì cả. Hình 3. Mô hình tác tử di ñộng Một tác tử tại nút u chỉ có thể di cư sang nút v nếu có liên kết giữa 2 nút u và v. Số lượng các nút và các tác tử tương ứng ký hiệu là N và k. Đối với ña số các hệ thống, các tác tử và các nút ñược gán một ñịnh danh phân biệt. Tại thời ñiểm ban ñầu, các tác tử không biết số lượng nút N, số lượng tác tử k cũng như ñịnh danh của các tác tử khác. Một 12 tác tử ñược khởi tạo tại một nút nào ñó trong mạng, và một nút có thể chứa nhiều tác tử. Nut má tác tử ñược khởi tạo ban ñầu ñược gọi là nút nhà của tác tử. Các tác tử có thể di cư từ nút này sang nút khác, bằng cách thực hiện thao tác sau ñây: • move(v, λv(e)): thực hiện việc di cư từ nút v sang nút lân cận theo liên kết λv(e) Mỗi nút v có một bảng trắng (whiteboard), là vùng bộ nhớ cục bộ mà ở ñó các tác tử trên v có thể ghi, ñọc và xóa thông tin. Mỗi tác tử có thể thực hiện những thao tác sau ñây trên bảng trắng của mỗi nút: • write(v, infos): một tác tử ghi thông tin infos lên bảng trắng của nút v. • read(v): một tác tử ñọc thông tin trên bảng trắng của nút v. • delete(v): một tác tử xóa thông tin trên bảng trắng của v. Việc truy cập bảng trắng của nút ñược thực hiện theo quy tắc loại trừ: khi có nhiều tác tử trên một nút thực hiện các thao tác của chúng, các thao tác ñược thực hiện một cách tuần tự theo một thứ tự tùy ý. Các tác tử có thể sử dụng bảng trắng ñể liên lạc với nhau hoặc chứa các thông tin ñiều khiển. Tùy vào từng cách thức lưu trữ trong bảng trắng, chúng ta có thể phân loại mô hình tác tử thành nhiều mô hình con khác nhau. Vấn ñề này sẽ ñược ñề cập chi tiết trong phần tiếp theo. Một số khái niệm trong mô hình tác tử: • Trạng thái của một tác tử là trạng thái của các biến cục bộ của tác tử, bao gồm các thông tin ñiều khiển và các thông tin mà tác tử ñã thu thập từ các tác tử khác. • Trạng thái của một nút ñược biểu diễn bởi trạng thái bảng trắng của nó. • Cấu hình hệ thống C bao gồm trạng thái của tất cả các nút, tất cả các tác tử, và vị trí của mỗi tác tử trong mạng. Mỗi một cấu hình hệ thống ñược thay ñổi bởi các sự kiện của các tác tử (sự kiện ñọc, ghi, và di cư). Kí hiệu C0 là cấu hình ban ñầu của hệ thống và Evi là một tập các sự kiện xuất hiện ñồng thời tại cấu hình Ci. • Một thực hiện là một chuỗi xen kẽ các cấu hình và các tập sự kiện: EX = C0, Ev0, C1, Ev1, C2, … sao cho sự xuất hiện các sự kiện Evi-1 thay ñổi cấu hình từ Ci-1 sang Ci . Tác tử pj kết thúc tại cấu hình Ci nếu pj không thực hiện bất cứ một thao tác nào sau cấu hình Ci. 13 Độ dài ñường ñi của một tác tử là tổng số bước di chuyển của một tác tử trong một thực hiện. Thông thường, trong các giải thuật cho mô hình tác tử di ñộng, chúng ta tập chung vào ñộ phức tạp di chuyển. Do mỗi bước di cư của tác tử sẽ làm giảm ñáng kể hiệu suất của giải thuật. Độ phức tạp di chuyển của giải thuật là tổng số bước di chuyển lớn nhất có thể của tất cả các tác tử trong hệ tác tử di ñộng từ lúc bắt ñầu cho ñến khi kết thúc giải thuật. Trong một số hệ thống phân tán có trạng thái khác nhau, như hệ thống với mạng ñộng (dynamic network). Thì ñộ phức tạp di chuyển không còn là yếu tố hàng ñầu ñể ñánh giá hiệu suất của thuật toán nữa. Chúng ta thường sử dụng một số yếu tố khác như ñộ yên tĩnh (quiescene). Vấn ñề này sẽ ñược ñề cập chi tiết ở chương 3. 1.2.3. Giải thuật chuyển ñổi từ mô hình thông báo sang mô hình tác tử Mô hình truyền thông báo là mô hình quen thuộc trên thực tế, ñược sử dụng chủ yếu trong các hệ phân tán từ trước tới nay. Các nghiên cứu về giải thuật phân tán ñều chủ yếu tập trung vào mô hình truyền thông báo này. Nhiều giải thuật ñã ñược nghiên cứu rất sâu, trở thành những giải thuật kinh ñiển, ví dụ như giải thuật bầu thủ lĩnh, loại trừ lẫn nhau hay một số giải thuật xây dựng cây khung tối thiểu. Để xây dựng các giải thuật cho mô hình tác tử, chúng ta hay xuất phát từ các giải thuật trong mô hình truyền thông báo. Thậm chí, nếu có thể chuyển trực tiếp giải thuật trong mô hình truyền thông báo sang mô hình tác tử mà vẫn giữ nguyên ñược ñộ phức tạp của giải thuật là tốt nhất. Sử dụng những phương pháp chuyển ñổi này, ta có thể tận dụng ñược hết những nghiên cứu về giải thuật phân tán ñã có, mà không phải băn khoăn về vấn ñề giải thuật ñó thuộc mô hình nào. Đã có nhiều nghiên cứu chi tiết về vấn ñề này. Các giải thuật chuyển ñổi từ mô hình truyền thông báo sang mô hình tác tử ñã ñược nghiên cứu và ñề cập chi tiết trong nhiều tài liệu tham khảo [10]. Tuy nhiên, hầu hết các giải thuật ñều có ñộ phức tạp chuyển ñổi lớn với O(N) bước di chuyển của tác tử cho việc truyền một thông báo. Tức là một giải thuật có ñộ phức tạp O(N) trong mô hình thông báo, sẽ phải cần ñộ phức tạp O(N2) trong mô hình tác tử. Độ phức tạp lớn như vậy là vì các giải thuật này còn ñảm bảo thêm yếu tố kháng lỗi, ñề phòng trường hợp tác tử bị hỏng hoặc mất mát trong quá trình di chuyển. Yếu tố này không thực sự cần thiết ñối với những nghiên cứu ñề cập trong luận văn này. Tại chương 4, chúng ta sẽ xem xét kỹ lưỡng những biện pháp khắc phục trong quá trình chuyển ñổi giải thuật. Vì vậy ở ñây, tôi chỉ giới thiệu một giải thuật ñơn giản ñể chuyển ñổi giữa hai mô hình, với ñộ phức tạp O(1) bước di chuyển của tác tử cho việc truyền một thông báo. 14 Giải thuật này có tên gọi là giải thuật MSA, ñược ñề cập chi tiết trong bài báo [22]. Đây là một giải thuật khá hiệu quả trong việc chuyển ñổi từ mô hình truyền thông báo sang mô hình tác tử. Tư tưởng của giải thuật tương ñối ñơn giản ñơn giản: mỗi sự kiên tính tại một nút v sẽ ñược thực hiện bởi một tác tử nào ñó khi nó di chuyển ñến v. Các thông báo tạo ra cũng như các ñích ñến của chúng ñược lưu trong một hàng ñợi gửi Squeuev trên bảng trắng. Mỗi tác tử khi di cư ñến một nút, sẽ thực hiện các tính toán cần thiết, và lấy một thông báo từ hàng ñợi gửi, di cư ñến nút ñích ñể truyền thông báo cho nút ñó. Nếu không có thông báo nào trong hàng ñợi gửi S-queueu, thì tác tử pi quay trở lại nút liền kề trước khi di chuyển (còn gọi là bước quay lui – backtracking). Để làm ñược ñiều này, mỗi tác tử pi lưu trữ một tập biến visiti, trong ñó lưu trữ thông tin những nút mà tác tử pi ñã ñến thăm. Các tác tử trong mạng liên tục thực hiện việc tính toán, di chuyển và quay lui như vậy cho ñến khi toàn bộ các hàng ñợi gửi tại các nút rỗng, và các tác tử quay lại nút nhà của mình. Khi ñó, giải thuật MSA kết thúc. Dữ liệu ghi trên bảng trắng của mỗi nút v A: giải thuật truyển thông báo sv: lưu trạng thái của nút v trong A S-queuev: một hàng ñợi các thông báo sẽ ñược gửi (khởi tạo S-queue = φ) /* một cặp (m,w) trong hàng ñợi S-queue có nghĩa là thông báo m sẽ ñược gửi tới hàng xóm w */ Các biến của một tác tử pi visiti: một ngăn xếp chứa các nút mà pi ñã ñi qua (khởi tạo visiti = φ) msgi: một không gian nhớ lưu nội dung của một thông báo. + Khi một tác tử pi ñược ñịnh vị ban ñầu trên nút bắt ñầu v: khởi tạo giải thuật A Process(φ) + Với tác tử pi từ nút u ñến nút v If (msgi ≠ φ) Then /* pi gửi một thông báo tới nút v */ Đẩy u vào hàng ñợi visiti Process((msgi, u)) Else Send /* pi quay lui trở lại v */ Produce Process((m,u)) /* tác tử thực hiện tính toán với thông báo vừa nhận*/ Thực hiện tính toán cục bộ (sv, (m, u)) | (sv′, M′) 15 sv = sv′ và add ∀(m′, u′) ∈ M′ vào hàng ñợi S-queuev. /* các thông báo phát sinh ñược lưu vào hàng ñợi chuyển */ Send Produce Send /* Lấy thông báo trong hàng ñợi và chuyển ñi */ If ( S-queuev ≠ φ ) Then Xóa thực thể ñầu tiên (m, u) từ S-queuev msgi = m di chuyển tới u /* pi thực hiện một bước chuyển m sang nút u */ Else Return /* nếu hàng ñợi rỗng thì quay lui */ Produce Return If visiti = φ Then terminate Else lấy u từ ngăn xếp visiti msgi = φ di chuyển tới u /* pi thực hiện bước chuyển quay lui * / Hình 4. Giải thuật MSA [22] Tính ñúng ñắn của giải thuật MSA: [22] Để chứng minh giải thuật MSA thực sự mô phỏng ñược một giải thuật từ mô hình truyền thông báo sang mô hình tác tử di ñộng. Ta chứng minh một số ñịnh lý sau ñây: Định lý 1.1. Cho A là một giải thuật chuyển thông báo có hữu hạn các thông báo trao ñổi của bất kỳ thực hiện nào trong một hệ thống không ñồng bộ. Mọi thực hiện có thể của giải thuật MSA mô phỏng một số thực hiện của A. Chứng minh: Do các thông báo cần chuyển ñều lưu trong hàng ñợi chuyển S-queueu, nên mỗi thông báo chỉ ñược chuyển một lần duy nhất. Vì vậy thuật toán MSA ñảm bảo tính toàn vẹn (các thông báo không bị lặp). Để chứng minh rằng một thực hiện của MSA thỏa mãn thuộc tính sống ñộng, chúng ta chỉ ra rằng hàng ñợi gửi S-queue ở tất cả các nút cuối cùng sẽ rỗng. Chứng minh phản chứng, một thông báo m là thông báo ñầu tiên trong hàng ñợi S-queuev không bao giờ ñược giao bởi bất cứ tác tử nào. Cho pi là tác tử lấy chuyển thông báo trước m từ hàng ñợi. Vì S-queuev ≠ φ, tác tử pi thực hiện bước chuyển giao từ nút v và ñưa nút v vào hàng 16 ñợi visiti của nó. Nếu tác tử pi cuối cùng cũng trở về nút v trong hàng ñợi visiti của nó, pi tiếp tục bước chuyển giao từ v cho ñến khi S-queuev trở nên rỗng. Kết quả, thông báo m cuối cùng cũng ñược giao bởi một tác tử. Trong trường hợp tác tử pi không trở về nút v trong ngăn xếp visiti của nó. Có nghĩa tác tử pi thực hiện các bước chuyển giao vô hạn lần trên nút khác v vì cuối cùng pi sẽ trở về nút v bởi các bước chuyển quay lui nếu như số bước chuyển giao hữu hạn. Một tác tử thực hiện bước chuyển giao tại một nút u chỉ khi Squeue khác rỗng, và một thông báo ñược lấy từ S-queueu bởi một bước chuyển giao. Vì vậy, một số vô hạn các thông báo ñược thêm vào các hàng ñợi S-queue vì tác tử pi thực hiện các bước chuyển giao vô hạn lần. Điều này suy ra rằng một thực hiện của giải thuật gốc A bao gồm một số vô hạn các sự kiện gửi. Điều này mâu thuẫn với số thông báo trao ñổi trong bất cứ thực hiện nào của A là hữu hạn. Như vậy, trong cả hai trường hợp, các tác tử chỉ dừng lại khi tất cả các hàng ñợi gửi là rỗng. Bổ ñề 1.1: Tất cả các tác tử kết thúc giải thuật MSA trong thời gian hữu hạn trong mọi thực hiện có thể. Mỗi giải thuật MSA mô phỏng giải thuật truyền thông báo A. Nếu mọi thực hiện của giải thuật A có một số hữu hạn các bước truyền thông báo, thì sau khi mô phỏng, mọi thực hiện của giải thuật MSA cũng có một số hữu hạn các bước di chuyển của tác tử. Định lý 1.2: Giả sử tổng số các thông báo trao ñổi trong mọi thực hiện của giải thuật chuyển thông báo A không quá MA. Thì, giải thuật MSA mô phỏng giải thuật A với không quá 2. MA bước di chuyển trong hệ tác tử di ñộng. Chứng minh. Một tác tử thực hiện truyền thông báo bằng 2 bước di chuyển, một bước giao và một bước quay lui. Với mỗi thông báo, tác tử sẽ thực hiện một bước di chuyển ñể gửi thông báo ñó, và xóa nó trong hàng ñợi gửi. Vì vậy, một thông báo chỉ tương ứng với một bước chuyển giao. Với mỗi bước giao, tác tử sẽ ñưa nút ñó vào biến visit ñể thực hiện quay lui. Mỗi lần quay lui, nút trong biến visit sẽ bị xóa. Vì vậy, mỗi bước chuyển giao chỉ tương ứng với một bước quay lui. Như vậy một giải thuật A có không quá MA thông báo cần chuyển, thì sau khi mô phỏng sẽ có không quá 2. MA các bước di chuyển của tác tử. Chú ý: giải thuật MSA chỉ chuyển ñối chính xác với những giải thuật truyền thông báo không tự ñộng phát sinh thông báo tại mỗi nút. Hay những giải thuật mà thông báo ñầu ra tại một nút chỉ xuất hiện khi nút ñó có thông báo tại ñầu vào. Vì vậy, khi áp dụng giải thuật MSA tại thuật toán thứ 3 trong chương 4, chúng ta sẽ phải có những thay ñổi cho phù hợp. 17 1.3. Phân loại mô hình tác tử di ñộng Để tiện cho việc nghiên cứu giải thuật, tùy vào ñặc ñiểm của mạng cũng như ñặc ñiểm của các nút, chúng ta có thể phân loại mô hình tác tử ra thành một số loại con sau ñây [21]: • Dựa vào ñịnh danh của tác tử, ta có thể chia mô hình tác tử ra làm 2 loại con: mô hình tác tử có ñịnh danh và mô hình tác tử vô danh.
Trong mô hình tác tử có ñịnh danh, mỗi tác tử cũng như mỗi nút ñược gán một ñịnh danh duy nhất và phân biệt. Nhờ ñó, các tác tử có thể phân biệt lẫn nhau cũng như biết ñược vị trí nút mà mình ñang ñứng. Các giải thuật thiết kế cho mô hình tác tử có ñịnh danh thường ñơn giản hơn. Vì vậy, mô hình này hay ñược sử dụng ñể nghiên cứu giải thuật. Hiện nay, các giải thuật cho mô hình tác tử nếu không có ñiều kiện gì, thì mặc nhiên là thiết kế cho mô hình tác tử có ñịnh danh.
Trong mô hình tác tử không ñịnh danh, các tác tử khi mới khởi tạo cũng như các nút hoàn toàn không ñược gán một ñịnh danh nào cả. Vì vậy, các giải thuật thiết kế cho mô hình này rất khó khăn, trong nhiều trường hợp không thể thực hiện ñược. • Dựa vào tính ñồng bộ trong mạng, giống như trong mô hình thông báo, mô hình tác tử cũng có thể ñược chia ra làm 2 dạng: mô hình tác tử ñồng bộ và mô hình tác tử không ñồng bộ.
Mô hình tác tử ñồng bộ là mô hình mà tác tử mà các hoạt ñộng bao gồm xử lý và di chuyển theo từng nhịp thời gian. Trong mỗi nhịp, tác tử sẽ thực hiện một loạt các công việc, bao gồm di cư ñến một nút, truy cập vào bảng trắng và thực hiện các tính toán cục bộ trên nút ñó. và tiến hành rời khỏi nút này di cư ñến một nút khác. Nhịp thời gian kết thúc khi tác tử ñến ñược nút ñích. Hay nói cách khác, mô hình tác tử ñồng bộ là mô hình có cận trên của thời gian ñối với mỗi bước di chuyển và xử lý của tác tử. Khi nhiều hơn một tác tử cùng ñến một nút, các tác tử vẫn xử lý trong cùng một nhịp, nhưng theo thứ tự tùy ý. Mô hình tác tử ñồng bộ thường ký hiệu là Synch.
Mô hình tác tử không ñồng bộ là mô hình mà không có giới hạn thời gian ñối với các hành ñộng của tác tử. Thời gian di cư và xử lý của tác tử là không xác ñịnh, nhưng hữu hạn. Khi một tác tử ñã rời khỏi một nút, chắc chắn tại một thời ñiểm nào ñó, nó sẽ ñến nút ñích. Các hệ thống trên thực tế có thời gian truyền dữ liệu lớn và không cố ñịnh thường ñược coi là mô hình không ñồng bộ. Đối với mô hình không ñồng bộ, các giải thuật thường phức tạp hơn vì phải không 18 phụ thuộc vào ñộ trễ cũng như thứ tự truyền của các thông báo. Điều này nhiều lúc không thực hiện ñược, ví dụ như các thuật toán trong mạng ñộng sẽ ñề cập ñến ở các chương sau. Mô hình tác tử không ñồng bộ thường ký hiệu là Asynch. • Dựa vào giới hạn của bảng trắng, mô hình tác tử có thể chia làm 3 loại con sau ñây:
Mô hình bảng trắng ñầy ñủ (full-whiteboard): Trong mô hình này, bảng trắng có thể lưu tất cả các thông tin cần thiết, bao gồm cả các thông tin ñiều khiển phát sinh trong quá trình xử lý cũng như các thông tin riêng của tác tử. Một tác tử có thể lưu trữ thông tin cần trao ñổi tại các nút, các tác tử khác khi ñến nút ñó, có thể lấy ñược thông tin của những tác tử ñã ghé thăm nút ñó. Vì vậy 2 tác tử không cần gặp nhau vẫn có thể trao ñổi ñược thông tin với nhau. Tuy nhiên, phương pháp này có nhược ñiểm về giới hạn của bảng trắng phải có ñộ lớn thích hợp, và ñộ an toàn của thông tin trao ñổi không ñược ñảm bảo. Đối với các hệ thống phân tán hoạt ñộng trên những mạng chung, người ta thường ít khi sử dụng mô hình này. Mô hình bảng trắng ñầy ñủ thường ñược ký hiệu là FW
Mô hình bảng trắng ñiều khiển (control_whiteboard): Đây là mô hình thông dụng nhất, thường ñược sử dụng trong những nghiên cứu thuật toán về mô hình tác tử. Trong mô hình này, bảng trắng chỉ lưu các thông tin ñiều khiển phát sinh trong quá trình xử lý tại mỗi nút. Các thông tin này ñóng vai trong ñịnh hướng về giải thuật cũng như ñường ñi của các tác tử. Vì vậy, ñộ lớn của bảng trắng trong mô hình này không cần nhiều. Do các tác tử không lưu trữ thông tin riêng của mình lên bảng trắng, nên thông tin sẽ ñược bảo mật cẩn thận hơn. Nhưng ñể trao ñổi thông tin, hai tác tử cần phải cũng gặp mặt nhau tại một nút. Mô hình bảng trắng ñiều khiển thường ký hiệu là CW
Mô hình không bảng trắng (none_whiteboard): Trong mô hình này, các nút hoàn toàn không có bảng trắng. Vì vậy các tác tử hầu như không thể ñịnh hướng ñược trong quá trình di chuyển và thực hiện giải thuật. Mô hình không bảng trắng rất khó thiết kế giải thuật và không phù hợp với thực tế. Vì vậy có rất ít những nghiên cứu về mô hình này. Mô hình không bảng trắng ký hiệu là NW. • Dựa vào trạng thái các liên kết, có thể chia làm 2 loại con là mô hình mạng song công và mô hình mạng ñơn công.
Mô hình mạng song công (full-duplex): Trong mô hình này, các tác tử có thể cùng di chuyển theo cả hai hướng trong các liên kết trên mạng. Chú ý, khi hai tác tử di chuyển trên cùng một liên kết theo 2 hướng ngược nhau, chúng vẫn