Luận văn thạc sĩ gestion de groupe et détection de partition en environnement mobile

Luận văn thạc sĩ: Quản lý nhóm và phát hiện phân vùng trong môi trường di động. Nghiên cứu chuyên sâu về giải pháp hiệu quả cho bài toán này.

• Tác giả: Nguyen, Tuan Dung
• Người hướng dẫn: Denis, Conan
• Trường học: Institut National Des Télécommunications
• Chuyên ngành: Informatique
• Đề tài: Gestion De Groupe Et Détection De Partition En Environnement Mobile
• Loại tài liệu: Thèse
• Năm xuất bản: 2005
• Địa điểm: Évry

Tóm tắt

I. Giải mã luận văn Quản lý nhóm và phát hiện phân vùng di động

Luận văn "Gestion de groupe et détection de partition en environnement mobile" của tác giả Nguyễn Tuấn Dũng là một công trình nghiên cứu chuyên sâu, giải quyết các vấn đề cốt lõi trong lĩnh vực máy tính di động (mobile computing). Sự phát triển bùng nổ của các thiết bị di động như PDA, laptop và mạng không dây cục bộ (WLAN) đã tạo ra một mô hình tính toán mới, nơi người dùng có thể truy cập dữ liệu và dịch vụ ở bất kỳ đâu. Tuy nhiên, môi trường này cũng đặt ra những thách thức chưa từng có, đặc biệt là về tính ổn định của kết nối và khả năng chịu lỗi (fault tolerance). Luận văn tập trung vào hai khía cạnh quan trọng: quản lý nhóm trong mạng di động và phát hiện phân vùng mạng. Đây là các dịch vụ nền tảng để xây dựng những ứng dụng phân tán vững chắc, có tính sẵn sàng cao (high availability). Mục tiêu chính là đề xuất một dịch vụ quản lý nhóm mới, không chỉ xác định được các thành viên đang hoạt động trong nhóm mà còn phân loại rõ ràng các thành viên bị lỗi, ngắt kết nối hoặc bị cô lập do phân vùng mạng. Để làm được điều này, nghiên cứu đề xuất làm giàu các phần mềm trung gian (middleware) hiện có bằng cách tích hợp một hệ thống gồm bốn bộ phát hiện chuyên dụng: bộ phát hiện lỗi (failure), bộ phát hiện kết nối (connectivity), bộ phát hiện ngắt kết nối (disconnection) và bộ phát hiện phân vùng (partition). Cách tiếp cận này cho phép hệ thống có cái nhìn toàn diện và chính xác hơn về trạng thái của từng tiến trình trong môi trường hệ thống phân tán đầy biến động. Công trình này không chỉ có giá trị lý thuyết mà còn được hiện thực hóa thông qua một nguyên mẫu (prototype) để kiểm chứng tính hiệu quả và các thuộc tính mới đề xuất.

1.1. Bối cảnh Sự trỗi dậy của máy tính di động và các thách thức

Sự ra đời của máy tính di động vào những năm 90 đã định hình lại cách thức xây dựng các hệ thống phân tán. Môi trường này có bốn đặc điểm chính: (1) thiết bị di động có tài nguyên hạn chế; (2) tính di động làm tăng nguy cơ mất mát, hư hỏng; (3) kết nối mạng có hiệu năng và độ tin cậy thay đổi liên tục; (4) nguồn năng lượng của thiết bị bị giới hạn. Các đặc điểm này dẫn đến tình trạng ngắt kết nối thường xuyên, có thể là chủ động (tiết kiệm chi phí, năng lượng) hoặc bị động (mất sóng). Điều này đòi hỏi các cơ chế quản lý ngắt kết nối và khả năng chịu lỗi phải được thiết kế riêng. Đây chính là bối cảnh và động lực chính thúc đẩy nghiên cứu trong luận văn.

1.2. Mục tiêu nghiên cứu Xây dựng dịch vụ quản lý nhóm chịu lỗi

Mục tiêu cốt lõi của luận văn là xây dựng một dịch vụ quản lý nhóm trong mạng di động có khả năng chịu được sự phân vùng và ngắt kết nối. Dịch vụ này phải cung cấp các thuộc tính mới và hữu ích. Cụ thể, thay vì chỉ đồng thuận về tập hợp các tiến trình đang hoạt động, hệ thống cần đạt được sự đồng thuận về cả tập hợp các tiến trình bị lỗi, bị ngắt kết nối và bị phân vùng. Việc này giúp các ứng dụng tầng trên có đủ thông tin để đưa ra quyết định thích ứng một cách thông minh, thay vì hoạt động trong trạng thái không chắc chắn. Luận văn kế thừa và mở rộng các công trình trước đó về các bộ phát hiện trong môi trường di động để tạo ra một ứng dụng cụ thể và có tính thực tiễn cao.

II. Thách thức cốt lõi Phát hiện phân vùng mạng và tính nhất quán

Một trong những vấn đề nan giải nhất trong hệ thống phân tán di động là tình trạng phân vùng mạng. Phân vùng xảy ra khi một mạng bị chia thành hai hoặc nhiều phân đoạn (partition) không thể giao tiếp với nhau. Nguyên nhân có thể do lỗi liên kết, lỗi của một tiến trình trung gian, hoặc do một tiến trình chủ động ngắt kết nối. Trong bối cảnh đó, việc duy trì một cái nhìn nhất quán về thành viên nhóm trên toàn hệ thống trở nên cực kỳ khó khăn. Các hệ thống truyền thông nhóm (Group Communication Systems - GCSs) truyền thống thường gặp khó khăn trong việc phân biệt giữa một tiến trình bị lỗi (crash), một tiến trình bị ngắt kết nối tạm thời, và một tiến trình vẫn đang hoạt động nhưng nằm trong một phân vùng mạng khác. Sự nhầm lẫn này có thể dẫn đến các quyết định sai lầm, chẳng hạn như loại bỏ một thành viên còn hoạt động ra khỏi nhóm. Luận văn chỉ ra một thách thức lớn là sự không nhất quán (incohérence) trong thông tin mà các bộ phát hiện cục bộ cung cấp. Ví dụ, tại cùng một thời điểm, tiến trình p có thể cho rằng tiến trình q bị phân vùng, nhưng tiến trình r lại cho rằng q đã bị lỗi. Sự bất đồng này nếu không được giải quyết sẽ phá vỡ tính toàn vẹn của hệ thống. Do đó, việc thiết kế một cơ chế để đạt được thuật toán đồng thuận không chỉ về thành viên nhóm mà còn về trạng thái (lỗi, ngắt kết nối, phân vùng) của các tiến trình bên ngoài nhóm là yêu cầu cấp thiết, đặc biệt trong các mobile ad-hoc networks (MANETs).

2.1. Phân biệt các loại lỗi trong môi trường di động

Trong các hệ thống cố định, lỗi thường được hiểu là một tiến trình ngừng hoạt động (crash-failure). Tuy nhiên, trong môi trường di động, một tiến trình không thể truy cập có thể do nhiều nguyên nhân: nó thực sự bị lỗi, nó tự nguyện ngắt kết nối, hoặc nó đang nằm trong một vùng mất sóng gây ra phân vùng mạng. Việc phân biệt chính xác các trạng thái này là rất quan trọng. Ví dụ, một tiến trình ngắt kết nối có thể sẽ kết nối lại, trong khi một tiến trình bị lỗi thì không. Một giao thức định tuyến trong MANET cần thông tin này để tối ưu hóa đường đi. Luận văn nhấn mạnh sự cần thiết của các cơ chế phát hiện tinh vi hơn để cung cấp thông tin chi tiết này.

2.2. Vấn đề bất đồng bộ Thử thách của việc đạt được đồng thuận

Trong các hệ thống dị bộ (asynchronous), nơi không có giới hạn về tốc độ xử lý hay độ trễ mạng, bài toán đồng thuận là không thể giải quyết nếu có dù chỉ một tiến trình bị lỗi (kết quả của Fischer, Lynch, và Paterson). Môi trường di động về bản chất là dị bộ. Luận văn giải quyết vấn đề này bằng cách sử dụng mô hình bán đồng bộ (partially synchronous) được hỗ trợ bởi các bộ phát hiện lỗi không đáng tin cậy. Tuy nhiên, việc bổ sung thêm các trạng thái ngắt kết nối và phân vùng làm bài toán đồng thuận trở nên phức tạp hơn, đòi hỏi một thuật toán đồng thuận mới để đảm bảo tất cả các thành viên trong cùng một phân vùng có một cái nhìn nhất quán về toàn bộ hệ thống.

III. Phương pháp tiếp cận Hệ thống 4 bộ phát hiện chuyên dụng

Để giải quyết các thách thức đã nêu, luận văn đề xuất một giải pháp kiến trúc phân lớp, trong đó cốt lõi là việc tích hợp và phối hợp bốn loại bộ phát hiện (detector) khác nhau. Cách tiếp cận này cho phép hệ thống thu thập và tổng hợp thông tin từ nhiều khía cạnh để đưa ra một bức tranh toàn cảnh và chính xác hơn về trạng thái mạng. Bốn bộ phát hiện này hoạt động như những cảm biến cung cấp dữ liệu thô, sau đó được một dịch vụ quản lý nhóm cấp cao hơn xử lý để đạt được sự đồng thuận. Thứ nhất là bộ phát hiện lỗi (Failure Detector - FD), dựa trên khái niệm của Chandra và Toueg, dùng để nghi ngờ các tiến trình có thể đã bị lỗi. Thứ hai là bộ phát hiện kết nối (Connectivity Detector - CD), một cơ chế cục bộ giúp dự đoán các ngắt kết nối sắp xảy ra bằng cách theo dõi tài nguyên của thiết bị (như mức pin, cường độ tín hiệu). Thứ ba là bộ phát hiện ngắt kết nối (Disconnection Detector - DD), có nhiệm vụ chia sẻ thông tin từ CD cho các tiến trình khác trong mạng. Cuối cùng và quan trọng nhất là bộ phát hiện phân vùng mạng (Partition Detector - PD), tổng hợp thông tin từ ba bộ trên và kiến thức về topo mạng để xác định các nhóm tiến trình bị cô lập. Sự kết hợp này tạo ra một nền tảng vững chắc cho việc xây dựng các dịch vụ truyền thông nhóm có khả năng chịu lỗi cao trong môi trường di động.

3.1. Các bộ phát hiện lỗi kết nối và ngắt kết nối

Bộ phát hiện lỗi (FD) được sử dụng là loại "heartbeat" không đáng tin cậy, cung cấp một danh sách các tiến trình bị nghi ngờ là đã hỏng. Bộ phát hiện kết nối (CD) hoạt động ở cấp độ thiết bị, sử dụng kỹ thuật hysteresis (quán tính) để tránh hiệu ứng ping-pong khi trạng thái kết nối thay đổi liên tục quanh một ngưỡng nhất định. Thông tin từ CD sau đó được lan truyền bởi bộ phát hiện ngắt kết nối (DD) đến các thành viên khác. Sự phối hợp này cho phép hệ thống phân biệt giữa một lỗi vĩnh viễn và một ngắt kết nối tạm thời.

3.2. Bộ phát hiện phân vùng PDG Trụ cột của giải pháp

Bộ phát hiện phân vùng (PDG) là thành phần trung tâm, có nhiệm vụ phân tích dữ liệu từ FD, DD và topo mạng để xác định sự tồn tại của các phân vùng. Luận văn đề xuất thuật toán PDG, yêu cầu kiến thức về topo toàn cục của hệ thống. Nó xây dựng và duy trì một đồ thị kết nối của tất cả các tiến trình. Khi một tiến trình hoặc liên kết bị nghi ngờ là lỗi/ngắt kết nối, PDG sẽ kiểm tra xem đồ thị có bị chia cắt hay không. Kết quả đầu ra của PDG là một danh sách các tiến trình được cho là thuộc về một phân vùng khác. Đây là thông tin đầu vào quan trọng cho thuật toán gom cụm (clustering algorithms) của dịch vụ quản lý nhóm.

IV. Hướng dẫn xây dựng dịch vụ quản lý nhóm với khung nhìn mở rộng

Đóng góp quan trọng nhất của luận văn là định nghĩa và đặc tả một dịch vụ quản lý nhóm mới dựa trên khái niệm "khung nhìn mở rộng" (vue augmentée). Trong các hệ thống GCS truyền thống, một "khung nhìn" (view) chỉ đơn giản là danh sách các thành viên được cho là đang hoạt động trong nhóm. Cách tiếp cận này quá đơn giản cho môi trường di động. Khung nhìn mở rộng được đề xuất bao gồm bốn thành phần riêng biệt: (1) một tập hợp các thành viên đang hoạt động và có thể truy cập (khung nhìn nhóm cổ điển); (2) một tập hợp các thành viên bị xem là lỗi; (3) một tập hợp các thành viên bị xem là đã ngắt kết nối; và (4) một tập hợp các thành viên bị xem là nằm trong phân vùng khác. Để duy trì tính nhất quán cho cấu trúc dữ liệu phức tạp này, luận văn giới thiệu một khái niệm thuật toán mới gọi là "đồng thuận phân vùng" (partition agreement). Thay vì chỉ đạt được sự đồng thuận về ai đang "ở trong", các thành viên trong một phân vùng phải cùng nhau thống nhất về trạng thái của tất cả các tiến trình khác trong toàn hệ thống. Điều này giải quyết triệt để vấn đề không nhất quán của các bộ phát hiện cục bộ và cung cấp cho ứng dụng một ngữ cảnh hoạt động rõ ràng, đáng tin cậy. Dịch vụ này được đặc tả hình thức thông qua năm thuộc tính chính (AGM1-AGM5) để đảm bảo tính chính xác, đầy đủ, nhất quán, có thứ tự và toàn vẹn.

4.1. Khái niệm khung nhìn mở rộng và bốn thành phần chính

Một khung nhìn mở rộng Va(p, t) tại tiến trình p ở thời điểm t bao gồm: VC(p, t) là tập hợp các thành viên đúng và kết nối, VF(p, t) là tập hợp các tiến trình bị xem là lỗi, VD(p, t) là tập hợp các tiến trình bị xem là ngắt kết nối, và VP(p, t) là tập hợp các tiến trình bị xem là bị phân vùng. Một thuộc tính quan trọng (AGM5 - Integrity) đảm bảo rằng bốn tập hợp này phải rời nhau, nghĩa là một tiến trình không thể thuộc nhiều hơn một loại trạng thái tại cùng một thời điểm trong cùng một khung nhìn.

4.2. Thuật toán đồng thuận phân vùng Đảm bảo tính nhất quán

Để đạt được đồng thuận phân vùng, các tiến trình trong cùng một nhóm trao đổi các "ước tính" (estimate) của chúng về khung nhìn mở rộng. Thuật toán sử dụng các quy tắc hợp nhất để đảm bảo sự hội tụ. Ví dụ, tập hợp các thành viên hoạt động (VC) được tính bằng phép giao của các ước tính, trong khi các tập hợp lỗi, ngắt kết nối và phân vùng được tính bằng phép hợp. Các quy tắc bổ sung được đưa ra để giải quyết xung đột, chẳng hạn như ưu tiên trạng thái "ngắt kết nối" hoặc "phân vùng" hơn trạng thái "lỗi" nếu một tiến trình xuất hiện ở nhiều danh sách. Điều này phản ánh đúng bản chất của môi trường di động, nơi ngắt kết nối là phổ biến và không nên bị nhầm với lỗi vĩnh viễn.

V. Cách triển khai nguyên mẫu trên JGroups Kiến trúc và thuật toán

Để chứng minh tính khả thi của dịch vụ được đề xuất, một nguyên mẫu đã được phát triển dựa trên JGroups, một hệ thống truyền thông nhóm mã nguồn mở, dạng mô-đun và có khả năng xử lý phân vùng. Lựa chọn JGroups là hợp lý vì kiến trúc phân lớp của nó cho phép dễ dàng sửa đổi và chèn thêm các chức năng mới. Kiến trúc của nguyên mẫu chèn một lớp trung gian mới, được gọi là lớp PDG, vào giữa hai lớp hiện có của JGroups là MSL (Multi Send Layer) và VML (View Membership Layer). Lớp PDG này có nhiệm vụ chặn các thông điệp nghi ngờ (msuspect) từ lớp dưới, thực hiện logic của các bộ phát hiện (trong khuôn khổ luận văn là thông qua mô phỏng mạng), và sau đó tạo ra một thông điệp nghi ngờ mở rộng (msuspect*) chứa thông tin về các tiến trình lỗi, ngắt kết nối và phân vùng. Thông điệp này sau đó được gửi lên lớp VML. Thuật toán quản lý nhóm cốt lõi trong VML cũng được sửa đổi để có thể xử lý khung nhìn mở rộng và thực hiện thuật toán đồng thuận phân vùng. Quá trình này bao gồm các pha đồng bộ hóa (SynchronizationPhase) và trao đổi ước tính (EstimateExchangePhase) để đi đến một quyết định chung về khung nhìn mới, sau đó cài đặt và thông báo cho ứng dụng.

5.1. Kiến trúc hệ thống Tích hợp lớp PDG vào JGroups

Kiến trúc đề xuất giữ lại các lớp mạng cơ bản của JGroups. Lớp PDG mới đóng vai trò như một bộ lọc và bộ làm giàu thông tin. Nó nhận thông tin về các tiến trình không thể truy cập từ MSL. Thay vì chuyển thẳng lên, nó sử dụng một kịch bản định trước (mô phỏng) để phân loại các tiến trình này vào các nhóm lỗi, ngắt kết nối hoặc phân vùng. Kiến trúc này có tính mô-đun cao, cho phép trong tương lai có thể thay thế thành phần mô phỏng bằng một cài đặt thực sự của các bộ phát hiện mà không ảnh hưởng đến lớp VML ở trên. Đây là một cách tiếp cận thiết kế thông minh để đánh giá hiệu năng mạng và thuật toán.

5.2. Sửa đổi thuật toán VML để hỗ trợ giao tiếp nhóm mở rộng

Thuật toán trong VML của JGroups, vốn dựa trên một điều phối viên, đã được sửa đổi đáng kể. Các cấu trúc dữ liệu chính như view và các thông điệp trao đổi như ESTIMATE và VIEW đều được mở rộng để chứa bốn thành phần của khung nhìn mới. Các hàm xử lý và hợp nhất ước tính được cập nhật với các quy tắc hội tụ (R1-R4) như đã mô tả. Việc này đảm bảo rằng quá trình giao tiếp nhóm (group communication) vẫn duy trì được tính nhất quán và toàn vẹn ngay cả khi ngữ nghĩa của "khung nhìn" đã trở nên phức tạp hơn rất nhiều. Các công cụ mô phỏng như NS-3 simulator hay OMNeT++ có thể được dùng để kiểm chứng các sửa đổi này trong các nghiên cứu sâu hơn.

VI. Kết luận và định hướng tương lai cho quản lý nhóm di động

Luận văn "Gestion de groupe et détection de partition en environnement mobile" đã thành công trong việc đề xuất một dịch vụ quản lý nhóm mới, mạnh mẽ và phù hợp với các đặc thù của môi trường di động. Bằng cách giới thiệu khái niệm "khung nhìn mở rộng" và "đồng thuận phân vùng", nghiên cứu đã cung cấp một giải pháp hiệu quả cho vấn đề không nhất quán và mơ hồ về trạng thái của các tiến trình trong một mạng không ổn định. Việc xây dựng một nguyên mẫu trên nền tảng JGroups đã chứng minh tính khả thi của phương pháp tiếp cận. Đóng góp chính của công trình là cung cấp một đặc tả hình thức rõ ràng và một thuật toán cụ thể để hiện thực hóa một dịch vụ quản lý nhóm trong mạng di động có khả năng chịu lỗi cao. Hướng phát triển trong tương lai rất rộng mở. Đầu tiên, cần phải hiện thực hóa đầy đủ các bộ phát hiện thay vì sử dụng mô phỏng để có thể đánh giá hiệu năng mạng trong điều kiện thực tế. Thứ hai, có thể gỡ bỏ giả định về topo mạng không đổi và cho phép các nút di chuyển tự do, một đặc điểm của mobile ad-hoc networks (MANETs). Cuối cùng, các nguyên tắc và dịch vụ được phát triển trong luận văn này có thể được áp dụng và mở rộng cho các lĩnh vực mới nổi như mạng cảm biến không dây (WSN) và Internet of Things (IoT), nơi hàng tỷ thiết bị kết nối không liên tục và cần các cơ chế quản lý trạng thái hiệu quả.

6.1. Tóm tắt các đóng góp chính của luận văn nghiên cứu

Các đóng góp chính bao gồm: (1) Đặc tả hình thức một dịch vụ quản lý nhóm mới với khái niệm "khung nhìn mở rộng", phân loại rõ ràng các trạng thái lỗi, ngắt kết nối và phân vùng. (2) Đề xuất thuật toán "đồng thuận phân vùng" để giải quyết sự không nhất quán giữa các bộ phát hiện. (3) Thiết kế một kiến trúc khả thi và triển khai nguyên mẫu trên nền tảng JGroups, chứng minh tính đúng đắn của lý thuyết. Công trình này là một bước tiến quan trọng trong việc xây dựng các ứng dụng phân tán có tính sẵn sàng cao.

6.2. Hướng phát triển Ứng dụng vào Internet of Things IoT

Các hệ thống Internet of Things (IoT) và mạng cảm biến không dây (WSN) có nhiều điểm tương đồng với môi trường di động được mô tả trong luận văn: số lượng lớn thiết bị, tài nguyên hạn chế, kết nối không ổn định và dễ xảy ra phân vùng. Dịch vụ quản lý nhóm với khung nhìn mở rộng có thể là một thành phần nền tảng cực kỳ giá trị để quản lý các nhóm cảm biến, đảm bảo tính nhất quán dữ liệu và cho phép các ứng dụng IoT hoạt động một cách tin cậy ngay cả khi một phần của mạng bị cô lập tạm thời. Đây là một hướng nghiên cứu đầy hứa hẹn cho tương lai.

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

Institut de la Fran ophonie pour l'Informatique Institut National des Télé ommuni ations MÉMOIRE DE FIN D'ÉTUDES MASTER D'INFORMATIQUE Gestion de groupe et déte tion de partition en environnement mobile NGUYEN Tuan Dung Responsable de stage : Denis CONAN Ce stage a été réalisé au sein du laboratoire SAMOVAR, équipe MARGE du département Informatique de l'Institut National des Télé ommuni ations GET/INT CNRS UMR SAMOVAR Évry, 15 août 2005 TIEU LUAN MOI download : [e-mail] Remer iements Je voudrais tout d'abord remer ier le Professeur Guy Bernard pour m'avoir a ueilli dans son équipe de re her he de l'Institut National des Télé ommuni ations (INT). Je tiens à remer ier tout parti ulièrement Denis Conan pour avoir proposé e sujet de stage et m'avoir en adré pendant es inq mois. Je le remer ie de son onta t haleureux, ses onseils et en ouragements, son soutien permanent et la liberté de re her he qu'il a bien voulu me laisser. Qu'il trouve i i l'expression de ma profonde re onnaissan e.

Mes plus sin ères remer iements vont également à tous les professeurs et les personnels de l'Institut de la Fran ophonie pour l'Informatique (IFI) pour m'avoir donné des ours de très bonne qualité et pour leur soutien tout au long de mes études à l'IFI. Un grand mer i aux thésards et aux autres stagiaires dans l'équipe à l'INT pour une am- bian e de travail parti ulièrement favorable. Je remer ie haleureusement mes amarades de la promotion IX pour leur amitié sans faille et je leur souhaite bonne han e pour la soutenan e. Mer i enn à mes parents, mon frère et mes amis pour leur soutien et leur en ouragement à tout l'instant.

i TIEU LUAN MOI download : [e-mail] Résumé L'évolution des réseaux sans l et des équipements a abouti à un nouveau paradigme onnu sous le nom  informatique mobile . Il ore aux utilisateurs la apa ité de pouvoir se dépla- er tout en restant onne té aux appli ations répartis et d'être indépendant de la lo alisation géographique. Dans un environnement mobile, les terminaux mobiles sont sujets à des dé on- nexions. Ce i requiert des mé anismes spé iques de gestion de dé onnexions et de toléran e aux fautes.

La gestion de groupe est un servi e prin ipal des systèmes de ommuni ation de groupe, une brique importante pour onstruire des appli ations réparties. Les travaux dans la littérature ont montré omment et dans quelle mesure des intergi iels existant peuvent être enri his par quatre déte teurs : défaillan e, onne tivité, dé onnexions, plus un quatrième, partitions. En se basant sur es déte teurs, nous proposons un nouveau servi e de gestion de groupe ayant de nouvelles propriétés intéressantes. Ave e servi e, les pro essus se mettent d'a ord non seulement sur l'ensemble des pro essus orre ts onne tés du groupe mais aussi sur les ensembles des pro essus défaillants, dé onne tés ou partitionnés.

Un prototype est onstruit pour tester notre appro he. Mots- lefs : mobilité, toléran e aux fautes, algorithmique répartie, gestion de groupe et intergi iels. ii TIEU LUAN MOI download : [e-mail] Abstra t The advan es in wireless networking and portable applian es have engendered a new pa- radigm of omputing, alled  mobile omputing , in whi h users have a ess to data and information servi es regardless of their physi al lo ation or movement behavior. In mobile en- vironment, the mobile terminals ould frequently be dis onne ted.

This hara teristi requires the spe i and adapted me hanisms of dis onne tion management and fault toleran e. Group membership is a fundamental servi e of group ommuni ation systems, whi h are often used like the important bri ks to build distributed appli ations. Re ent resear h works have showed that the existed middleware an be augmented with four dete tors : failure, onne tivity, dis onne tion and partition. Based on these dete tors, we propose a new group membership servi e with new interesting properties.

With this servi e, the pro esses rea h an agreement not only about the set of orre t onne ted pro esses but also about the set of failure, dis onne ted and partitioned pro esses. A prototype is developped to test our approa h. Keywords : mobility, fault toleran e, distributed algorithm, group membership, middle- ware. iii TIEU LUAN MOI download : [e-mail] Table des matières Résumé ii Abstra t iii 1 Introdu tion 1 1.2 Motivation et obje tifs du stage .3 Environnement de travail .5 Plan du do ument.

5 2 Déte teurs en environnement mobile 6 2.2 Déte teur de défaillan es non able .3 Déte teur de onne tivité .4 Déte teur de dé onnexions .5 Déte teur de partitions. 12 3 Système de ommuni ation de groupe 13 3.4 Études de deux implantations existantes. 16 iv TIEU LUAN MOI download : skknchat@gmail.3 Choix de l'implantation. 18 4 Spé i ation d'un nouveau servi e de gestion de groupe 19 4.1 Modèle de système réparti .3 S héma de défaillan e .4 S héma de dé onnexion .5 S héma de partitionnement .6 Propriétés du servi e de gestion de groupe.

26 5 Ar hite ture, algorithmes et prototype 27 5.1 Ar hite ture .4 État d'avan ement du développement. 40 6 Con lusions et perspe tives 42 Bibliographie 46 A Preuves 47 v TIEU LUAN MOI download : [e-mail] Table des gures 1.1 Partitionnement dans le réseau .2 Stratégies de l'adaptation .1 Hystérésis du gestionnaire de onne tivité .2 Situations de partitionnement .3 Déte tion de partitions pour la gestion de groupe .1 Ar hite ture d'un système de ommuni ation de groupe .2 Ar hite ture de Javagroup .3 Ar hite ture de Jgroup .1 Ar hite ture du système proposé .2 Algorithme de gestion de groupe .3 Diagramme des lasses de la ou he PDG. 40 vi TIEU LUAN MOI download : [e-mail] Liste des tableaux 1.1 Quatre formes de toléran e aux fautes .1 Déte teurs de défaillan es .2 In ohéren e des déte teurs de partitions .1 Comparaison entre système de ommuni ation de groupe et autres proto oles. 13 vii TIEU LUAN MOI download : [e-mail] Liste des algorithmes 1 Algorithme prin ipal d'un pro essus p.

33 2 AgreementP hase et SynchronizationP hase. 37 4 Pro édures et fon tions supplémentaires. 39 viii TIEU LUAN MOI download : [e-mail] Chapitre 1 Introdu tion 1.1 Problématique L'apparition des ordinateurs portables, des assistants personnels numériques (PDA) puis- sants et des réseaux lo aux sans l (WLAN) dans les années 90s posent de nouveaux problèmes de onstru tion des systèmes répartis ave les lients mobiles [25℄. Ce i a engendré un nou- veau paradigme appelé  informatique mobile  qui sus ite des re her hes non seulement pour résoudre les problèmes existants dans les systèmes répartis (p.

la toléran e aux fautes) mais aussi pour traiter les problèmes spé iques en environnement mobile (p. la gestion de dé onnexions). La toléran e aux fautes est un sujet de re her he important pour les systèmes répartis. Ces systèmes disposent de deux propriétés importantes : la sûreté et la viva ité.

La première assure que les omportements mauvais n'apparaissent jamais dans le système et la se onde assure que les bons omportements doivent nalement apparaître lors de l'exé ution du système. Dans les systèmes réels, la prioritaire entre es deux propriétés dépend du type de l'appli ation. Les ombinaisons de es deux propriétés nous donnent les quatre formes de toléran e aux fautes présentées dans le tableau 1. viva e non viva e sûre masquant fail safe non sûre non masquant rien Tab.1  Quatre formes de toléran e aux fautes La redondan e est indispensable pour la toléran e aux fautes.

Chaque système réparti doit don être redondant dans l'espa e (p. ex serveurs primaires vs. se ondaires) ou dans le temps 1 TIEU LUAN MOI download : skknchat@gmail.1 Problématique 2 d'exé ution (p. ex le al ul d'une variable plusieurs fois).

Pour assurer la sûreté, il faut déte ter les défaillan es dans le système grâ e aux mé anismes de déte tion. Par ontre, la viva ité est plus di ile à garantir ar nous devons orriger les erreurs déte tés (la orre tion) [15℄. Dans les systèmes purement asyn hrones, 'est-à-dire dans lesquels il n'existe au une borne sur la vitesse de al ul de haque pro essus ou sur le temps de transmission des messages, [14℄ a montré qu'il est impossible de résoudre le problème du onsensus entre pro essus répartis dès qu'un seul d'entre eux est défaillant (p. par un arrêt fran ).

La raison est que nous ne pouvons pas dire si un pro essus est défaillant ou simplement très lent. Les systèmes de ommuni ation de groupe (GCSs pour Group Communi ation Systems en anglais) sont onsidérés omme des briques fondamentales pour onstruire les appli ations réparties. Ils fournissent aux appli ations la apa ité de ommuni ation de type multi ast able. Mais le prin ipe d'un GCS s'appuie sur un mé anisme de onsensus et don subit aussi un résultat d'impossibilité dans les systèmes asyn hrones [9℄.

Pourtant, le problème du onsensus peut être résolu dans un modèle partiellement syn hrone où nous ne onnaissons pas les délais de al ul ou de transmission mais dans lequel il existe un instant et une borne tels que, après et instant, les délais sont inférieurs à ette borne. Un exemple du onsensus dans e modèle est onstruit en utilisant le on ept de déte teur de défaillan es non able [10℄. D'autres appro hes utilisent les algorithmes probabilistes. Grâ e à e modèle, nous pouvons ensuite dénombrer plusieurs résultats de re her he sur les GCSs.

Mais, il est montré dans [3℄ que la plupart d'entre eux possèdent des faiblesses dans leur spé i ation : es systèmes peuvent autoriser des exé utions indésirables ou leur spé i ation peuvent être fa ilement satisfaites par des solutions triviales sans utilité (p. par les vues apri ieuses1 ). La grande di ulté est alors de trouver une spé i ation à la fois assez forte pour éviter tous es problèmes et assez faible pour qu'il soit faisable de trouver une solution. Nous présentons maintenant les ara téristiques de l'environnement mobile et la problé- matique de notre re her he.

Tout d'abord, l'informatique mobile est souvent ara térisée par quatre ontraintes [24℄ :  les entités mobiles ont des ressour es très limitées par rapport aux entités xes ;  la mobilité ontient elle-même plus de risques (p. perte ou vol) ; 1 La vue du pro essus p est le singleton {p}. TIEU LUAN MOI download : skknchat@gmail.1 Problématique 3  la onne tivité en environnement mobile est hautement variable en performan e et en abilité ;  les entités mobiles disposent d'une sour e limitée d'énergie. Dans les environnements mobiles, les terminaux mobiles sont sujets à des dé onnexions vo- lontaires ou involontaires.

Les premières, dé idées par l'utilisateur depuis son terminal mobile, sont justiées par les béné es attendus sur le oût nan ier des ommuni ations, l'énergie, la disponibilité du servi e appli atif, et la minimisation des désagréments induits par des dé- onnexions inopinées. Les se ondes sont le résultat de oupures intempestives des onnexions physiques du réseau, par exemple, lors du passage de l'utilisateur dans une zone d'ombre radio. Cette ara téristique donne naissan e à de nouveaux types de déte teurs omme les déte teurs de onne tivité et de dé onnexions [26℄.