Bầu thủ lĩnh

Trong kiến trúc đầy đủ, mỗi QT trong nhóm tham chiếu tới các QT khác trong cùng nhóm chỉ cần gửi một TĐ. TĐ bầu cử được gửi theo chế độ điểm-điểmtừ QT này đến QT khác. Giả thiết đầu tiên trong môi trường HĐH là tất cả chỉ số các QT phải duy nhất và mọi QT khác đều biết. Do tiến trình bầu thủ lĩnh được khởi xướng bằng phát hiện lỗi, giả thiết tiếp theo là về mô hình lỗi và cơ chế phát hiện lỗi. Để đơn giản, giả sử có mô hình lỗi ngây thơ. Giả thiết thứ hai là mạng truyền thông là tin cậy và chỉ có QT truyền thông có thể bị lỗi. Hệ mạng TT tin cậy có nghĩa là TĐ truyền đi không bao giờ bị thất lạc, thay đổi, bị trùng lặp và được phân phát đúng thứ tự trong thời gian hữu hạn đã biết. Giả thiết thứ ba liên quan đến lỗi của QT. Một QT nắm giữ TĐ trong một khoảng thời gian hữu hạn đã biết. Lỗi QT ngừng tính toán và không sinh ra TĐ báo lỗi làm hệ thống lẫn lộn. Hơn nữa, khi QT khôi phục, nó có kinh nghiệm về lỗi. Giả thiết thứ hai và thứ ba tạo hợp lý để nhận biết lỗi và gắn lại nút lỗi vào nhóm. Lỗi được phát hiện tin cậy bằng khởi tạo một khoảng quá hạn sẽ làm tăng chút ít tổng độ trễ TĐ khứ hồi và thời gian xử lý TĐ. QT bị lỗi được gắn vào nhóm bằng bầu cử bắt buộc trong khi khôi phục QT. Như một lựa chọn, QT bị lỗi tin tưởng việc cộng tác bằng việc bầu cử định kỳ đối với các QT được khôi phục sẽ được gắn với nhóm. Với những giả thiết trên đây, Garcia-Molina đầ xuất thuật toán bầu thủ lĩnh điển hình, được gọil à thuật toán kẻ mạnh (bully).

Thuật toán Bully là thuật toán tìm kiếm cực trị. Mỗi QT có độ ưu tiên toàn cục (có thể dùng chỉ số QT), QT nào có độ ưu tiên cao nhất là thủ lĩnh được bầu. Một QT bắt đầu bầu thủ lĩnh nếu nó nghi ngờ bộ phối hợp bị sự cố (ví dụ như, phát hiện bằng ngưỡng quá hạn) hoặc khi nó khôi phục sau sự cố. QT bắt đầu bằng việc gửi một TĐ dò hỏi are-you-uptới mọi nút có độ ưu tiên cao hơn để kiểm tra sự tồn tại của các QT đó.

Nếu ít nhất có một TĐ trả lời cho TĐ dò hỏi trên thì QT tự từ bỏ cố gắng ứng cử và chờ nút có độ ưu tiên cao hơn ứng cử.

Nếu không có TĐ trả lời nào từ các nút có độ ưu tiên cao hơn thì QT tự đặt mình làm thủ lĩnh bằng cách gửi TĐ yêu cầu enter-election tới mọi nút có độ ưu tiên thấp hơn. TĐ enter-election báo cho các QT có độ ưu tiên thấp hơn biết là tiến trình bầu cử đang xảy ra và các QT này nên chuẩn bị chấp nhận và giao tiếp với nó theo vai trò thủ lĩnh mới. Bầu cử chỉ hoàn thiện cho đến khi kết quả được gửi và nhận từ mọi nút đang hoạt động có độ ưu tiên thấp hơn.

Tại cùng thời điểm, có thể một vài QT cùng tự ứng cử vai trò thủ lĩnh. Chẳng hạn, QT có độ ưu tiên cao bị lỗi được khôi phục vào thời điểm đang diễn ra một cuộc bầu cử. Để đảm bảo tính nhất quán, QT chuyển vào trạng thái tạm thời khi nhận TĐ enter-election. QT ứng cử tự khai báo trở thành thủ lĩnh mới chỉ sau khi đã nhận được trả lời của mọi TĐ enter-electionhoặc quá hạn thời gian trả lời từ mọi QT có độ ưu tiên thấp hơn. Lúc này mọi QT hoặc bị lỗi, thực hiện thủ tục khôi phục, hoặc đang ở trạng thái tạm thời. Điều này đảm bảo QT khởi tạo khai báo tự là thủ lĩnh, do không còn QT nào khác nghĩ rằng còn có một thủ lĩnh khác.

Cuối cùng, QT khởi tạo phân bố trạng thái mới và thông báo cho mọi QT khác biết nó là thủ lĩnh trong tính toán mới.

Thuật toán bầu thủ lĩnh sẽ hết sức đơn giản nếu cho trước kiến trúc cố định kết nối mọi QT cộng tác. Do kiến trúc chỉ được dùng để thuận tiện truyền thông, giả thiết kiến trúc đơn giản nhất là kiến trúc vòng logic.

Vòng logic là dễ dàng xây dựng và cho một thuộc tính có một không hai là TĐ được gửi từ bất kì nút nào cũng có thể trở về nút đó, biểu diễn đủ một vòng thao tác hoặc quảng bá mà không cần thêm tri thức.

Để tìm QT có độ ưu tiên cao nhất trong vòng logic, QT khởi tạo bắt đầu tuần hoàn TĐ nhờ gắn vào TĐ độ ưu tiên (hoặc định danh id) của mỗi nút dọc theo vòng. Khi TĐ quay trở lại nút khởi tạo, nó chọn QT có độ ưu tiên cao nhất trong TĐ và quảng bá định danh thủ lĩnh mới tới mọi nút, một vòng nữa gọc theo vòng. Thuật toán có thể được cải tiến theo hai hướng. Thứ nhất, không cần thiết phải thu thập mọi định danh vào TĐ đơn. Để tìm định danh lớn nhất, mỗi nút đơn giản chỉ chuyển tiếp giá trị lớn hơn giữa định danh của nó và giá trị nhận được trên đường truyền tới nút tiếp theo. Theo cách này, định danh cực đại được được nổi lên dọc theo vòng và cuối cùng thu được nút thủ lĩnh. Thứ hai, nút rơi vào tiến trình bầu cử không cần quan tâm đến TĐ ngoại trừ TĐ chứa giá trị cao hơn so với định danh của bản thân nó.

Thuật toán vòng lôgic cải tiến do Chang và Robertsphát triển, được trình bày trong hình 4.22.

Nút khởi tạo khởi động participant = true và send (id) tới nút tiếp theo ;

For mỗi nút_QT,

receive(value);

case

value > id: participant := true, send (value);

value < id and participant == false: participant := true, send (id);

value = id: công bố thủ lĩnh

end case

Hình 4.22. Thuật toán bầu cử vòng của Chang và Robert

Mỗi QT đều có biến cục bộ là participant (được khởi tạo là false) cho biết QT này đã tham gia vào tiến trình bầu cử hay chưa. QT khởi tạo dị bộ bắt đầu bầu cử bằng việc gửi TĐ chứa định danh của nó. Mỗi QT nhận TĐ so sánh định danh của nó với giá trị tại TĐ. Giá trị lớn hơn được chuyển tiếp tới nút tiếp theo và QT đặt giá trị cho biến participant=True.

Một QT đã tham gia tiến trình bầu cử, nhận được TĐ bầu cử có giá trị định danh nhỏ hơn của nó thì nó không chuyển tiếp TĐ nữa. Thủ lĩnh tìm được khi TĐ mang giá trị cực đại đi đủ một vòng và trở về nút nút có định danh lớn nhất. Khi đó, thủ lĩnh gửi định danh của nó lên toàn bộ vòng, thông báo tới mọi nút về bộ phối hợp mới và đăth giá trị biến participantcủa các nút đó là False.

Tình huống bình thường, khi chỉ có một bộ khởi tạo, thuật toán của Changvà Robertmất trung bình N/2 TĐ để đạt được nút định danh lớn nhất và mất khoảng N TĐ khác để quay trở về. Như vậy, độ phức tạp thời gian và TĐ của thuật toán là O(N). Độ phức tạp cao hơn trong trường hợp đặc biệt khi mọi nút đều khởi phát việc bầu cử cùng lúc. Nếu không tối ưu, N khởi tạo bầu cử chiếm mỗi cái 0(N) TĐ, và tổng cộng có 0(N2). được gửi. Như vậy, trường hợp tốt nhất và tồi nhất của thuật toán vòng lôgic tương ứng là O(N) và O(N2), phụ thuộc vào định danh các nút trên vòng đã được xếp tăng dần hoặc giảm dần.

Một số thuật toán bầu thủ lĩnh vòng với độ phức tạp TĐ trong khoảng O(NlogN) đã được đề xuất. Tư tưỏng của các thuật toán này là giảm khởi tạo bầu cứ từ nút độ ưu tiên thấp càng nhiều càng tốt, bất luận thứ tự kiến trúc của các nút. Điều này thực hiện bằng cách so sánh định danh một nút với định danh hai nút kề cận của nó. Nút khởi tạo ở trạng thái chủ động nếu có định danh lớn hơn định danh của hai nút kề cận. Ngược lại nó trở thành bị động và chỉ được quyền nhận TĐ. Cách này loại bỏ hiệu quả ít nhất một nửa các nút mỗi vòng chuyển TĐ và kết quả chỉ còn log(N).

Hướng tiếp cận này đòi hỏi vòng hai chiều. Với vòng một chiều, có hiệu quả tương đương với so sánh ba nút khi dùng bộ đệm lưu hai TĐ liên tiếp, trước khi một nút được xác định là chủ động hoặc bị động.

Trong thuật toán bầu thủ lĩnh theo vòng logic, chưa tính đến vấn đề quản lí vòng logic. Nói riêng, xây dựng vòng như thế nào và làm cách nào duy trì hình trạng vòng khi đối phó với sự cố nút. Xây dựng và quản lí kiến trúc vòng logic là dễ dàng hơn nếu hạ tầng mạng có các kênh truyền thông chia xẻ, sẵn có các phương tiện phần cứng quảng bá. Vòng lỗi được phát hiện và cấu hình lại một cách hiệu quả nhờ việc giám sát và quảng bá TĐ trên kênh. Trong các mạng phổ dụng hớn với với kiến trúc mạng bất quy tắc, quảng bá được mô phỏng bằng đơn phát điểm-điểm phức. Một số phương pháp xây dựng vòng logic trong mạng bất quy tắc được đề xuất. ích lợi của việc có kiến trúc lôgic là rõ ràng. Nó xác định và kết nối nhóm QT, thuận tiện trong việc bầu thủ lĩnh và được dùng một cách hiệu quả để truyền thông giữa thủ lĩnh và các nút con.

Cây bao trùm được dùng như cấu trúc kiến trúc biểu diễn việc việc liên kết giữa các nút thành viên trong nhóm QT. Mạng có N nút được biểu diễn bằng một đồ thị với E cung nối các nút. Mỗi nút được coi là một thực thể tự trị có trao đổi TĐ với các nút kề cận nó. Giá truyền thông từ một nút tới nút kề cận của nó được biểu thị bằng trọng số của cung ra và được nút đó biết. Cây bao trùm cấp N là một cây biểu diễn mạng N nút với N-1 cạnh. Cây bao trùm tối thiểu (MST) là cây bao trùm với tổng trọng số các cung là nhỏ nhất. Cây bao trùm là một đồ thị phi chu trình. Nút bất kỳ của cây đều có thể được coi là gốc, hay cũng thế là thủ lĩnh của cây. Mỗi nút có duy nhất một đường tới gốc để đưa ra yêu cầu tới thủ lĩnh. Hệ quả là, cấu trúc cây cũng được dùng trong việc bầu cử thủ lĩnh mới. Thuật toán phân tán xây dựng cây bao trùm tối thiểu trong một mạng là một trong những vấn đề nghiên cứu mạnh mẽ trong tính toán phân tán. Bài toán bầu thủ lĩnh và cũng như xây dựng cây bao trùm tối thiểu đễ dàng được thu gọn về nhau. Một thuật toán phân tán hiệu quả giải bài toán này được chuyển đổi thành thuật toán giả bài toán kia với chỉ những biến đổi nhỏ.

Gallager, Humbelt và Spira tiên phong trong việc đề xuất thuật toán tìm cây bao trùm tối thiểu phân tán.Thuật toán của họ dựa trên các bước tìm kiếm và kết hợp. Thuật toán hợp nhất các đoạn, đi ra từ mỗi nút hiện là đoạn mức 0. Các đoạn đó được hợp nhất lại từng mức theo thuật toán Bottom-up cho đến khi được đoạn kết quả bao gồm các cung của cây bao trùm tối thiểu. Các đoạn là các cây con trọng số tối thiểu trong cây bao trùm tối thiểu. Mỗi đoạn, một cách dị bộ và độc lập, tìm cung ra với trọng số nhỏ nhất của nó và dùng cung này để nối với một nút trong một đoạn khác đẻ hình thành một đoạn lớn hơn của MST. Cây thu được nhờ hợp nhất hai cây con có trọng số nhỏ nhất khi sử dụng cạnh có trọng số nhỏ nhất cho kết quả là cây có trọng số nhỏ nhất.

Theo mục đích bầu thủ lĩnh, bất cứ cây bao trùm nào cũng đều đáp ứng được mọi nhu cầu. Trọng số các cung không mang theo trong việc tìm thủ lĩnh tốt nhất, vì vậy cây có giá tối thiểu hay không là không liên quan. Tuy nhiên thuật toán là phân tán và vì vậy cây bao trùm cuối cùng buộc là duy nhất phù hợp khi kết thúc thuật toán. Nếu không, thuật toán có thể không kết thúc hoặc có thể bị bế tắc. Đây là lý do phải tìm một cây bao trùm tối thiểu và thuật toán hoạt động được chỉ khi cây bao trùm tối thiểu là duy nhất. Điều này biểu thị rằng mọi cung trong đồ thị liên thông có trọng số duy nhất và cây MST tồn tại duy nhất. Với bài toán bầu thủ lĩnh, giả thiết rằng cung ra từ một nút được gắn nhãn duy nhất và gắn kết các định danh nút. Nếu định danh nút là duy nhất trong toàn bộ hệ thống thì trọng số cung cũng duy nhất.

Thủ lĩnh được chỉ định như nút cuối cùng được hợp nhất khi sinh ra cây bao trùm tối thiểu. Có thể bầu thủ lĩnh sau khi cây bao trùm tối thiểu đã được xây dựng. Nút khởi tạo quảng bá TĐ Campaign-For-Leader (CFL: tham gia bầu thủ lĩnh) chứa tem thời gian lôgic, tới tất cả các nút dọc theo cây bao trùm. Khi TĐ CFL tới một nút lá, nút lá đó trả lời bằng cách gửi lại TĐ bầu (Voting, V) tới nút cha của nó. TĐ V đơn thuần xác nhận ngắn cho CFL. Nhu cầu TĐ xác nhận là điểm khác nhau căn bản giữa kiến trúc vòng logic và kiến trúc cây. Nút cha tiếp tục gửi TĐ bầu tới cha của nó sau khi đã nhận được TĐ bầu từ mọi nút con. Một nút con không bao giờ bầu trực tiếp tới CFL mà phải thông qua nút cha của nó. Một nút kết thúc trả lời của nó là hoàn thiện việc tham gia bầu thủ lĩnh. Sau đó các nút chờ công bố của thủ lĩnh mới và không tiếp nhận CFL tiếp theo khác. Nguyên nhân có thể một vài nút khởi tạo trong giai đoạn này, hai hoặc nhiều hơn TĐ CFL cùng tới một nút. Trong trường hợp này, nút nhận sẽ chọn như cha của nó nút gửi với CFL có tem thời gian bé nhất. Ràng buộc được phá vỡ theo định danh của các nút khởi tạo. Lưu ý, cha của nút có thể được thay đổi một số lần trước khi nó ủy thác cuối cùng bằng việc gửi TĐ bầu cử V mang phiếu bầu của mọi cây con của nó. Thuật toán này cho phép nút khởi tạo bầu cử đầu tiên (có tem thời gian nhỏ nhất) trở thành thủ lĩnh. Một nút thành công khi nhận được tất cả phiếu bầu từ các nút con của nó.

Trong mạng với lỗi hoặc thay đổi cấu hình thường xuyên, giả thiết kiến trúc luôn tồn tại cho bầu thủ lĩnh là điều không khả thi. Tuy nhiên, cây bao trùm có thể được thiết kế cho bất cứ mạng bất quy tắc nào bằng loang TĐ. Loang TĐ là cơ chế quảng bá trong đó mỗi nút lặp lại TĐ nhận được tới mọi kề cận của nó, ngoại trừ nút đã gửi TĐ. Cuối cùng, mọi nút trong mạng nhận được TĐ và và cây bao trùm sẽ được hình thành. Dùng cơ chế này, các nút khởi tạo loang khắp hệ thống TĐ CFL. Theo sự loang TĐ, rừng bao trùm với mỗi cây có gốc ở một nút khởi tạo được hình thành. Các TĐ tra lời V được gửi quay lui từ nút lá tới gốc. Trong tiến trình này, mỗi nút tự thay đổi cha của nó tới nút gửi CFL có tem thời gian nhỏ nhất. Nút thắng lợi khi loang là TĐ CFL với tem thời gian nhỏ nhất và nó được phép truyền bá. TĐ loang thắng lợi tiếp quản không gian của nút thua và ngay lúc đó đi tìm các nút con chưa trả lời. Khi nút khởi tạo nhận được một tem thời gian nhỏ hơn, nút khởi tạo này bị chinh phục và trở thành một nút bình thường với một nút cha. Cuối cùng, chỉ cây bao trùm với tem thời gian nỏ nhất thắng thế. Do thuật toán dùng loang và coi như không cần một kiến trúc cây cố định trước khi khởi tạo việc bầu thủ lĩnh, thuật toán loang mạnh mẽ trong các mạng nhiều lỗi.

4.1. Các phương pháp định danh thực thể truyền thông trong dịch vụ nguyên thuỷ gửi và nhận.

4.2. Các phương án đồng bộ trong truyền thông CTĐ.

4.3. Sự chuyển đổi từ khái niệm ống dẫn sang khái niệm ống dẫn có tên mang ý nghĩa gì ?

4.4. Hãy mô tả truyền thông socket client/server hướng kết nối.

4.5. Trình bày giao thức bắt tay Handshake trong truyền thông Socket an toàn.

4.6. Truyền thông nhóm theo thứ tự tổng hai pha và so sánh với thứ tự FIFO và thứ tự nhân quả.

4.7. Khái niệm nền trong truyền thông RPC. Thi hành RPC.

4.8. Phương pháp truyền tham số và biến đổi dữ liệu trong thực hiện lời gọi RPC.

4.9. Xác thực nhau của khách và phục vụ trong truyền thông RPC.

4.10. Nội dung RPC an toàn của SUN.

4.11. Các tính chất ACID và giao thức cam kết hai pha trong truyền thông giao dịch.

4.12. Phân biệt giải pháp tên và địa chỉ. Việc chia tách thành hai giải pháp như thế có lợi điểm gì ?

4.13. Thi hành giải pháp tên.

4.14. Loại trừ ràng buộc theo cạnh tranh (sơ đồ tem - thuật toán Lamport và sơ đồ phiếu bầu)

4.15. Loại trừ ràng buộc theo thẻ bài (cấu trúc vòng, cấu trúc cây và cấu trúc quảng bá - thuật toán Suzuli/Kasami).

4.16. Bài toán bầu thủ lĩnh và thuật toán theo kiến trúc vòng lôgic.