Cho một tập hợp các bản sao không đồng bộ M, làm sao chúng ta tìm thấy tập hợp con của kích thước N cho phép giảm thiểu số lần truyền lại thông điệp cần thiết để đồng bộ hóa trạng thái tin nhắn của chúng trong một môi trường multicast đáng tin cậy (tức là - tất cả các bản sao đều nhận được tất cả các bản sao khác)?Làm cách nào để giảm thiểu số lần truyền lại để đồng bộ hóa bản sao N?
Trạng thái tin nhắn của các bản sao bao gồm các thông điệp mà chúng có từ cùng một nguồn D (D> = M). Đối với mỗi nguồn, một bản sao có tất cả các thông điệp từ nguồn đó đến một số thứ tự cao nhất (tức là - FIFO, không có lỗ, bắt đầu từ số không). Vì vậy, trạng thái thông điệp của một bản sao có thể được biểu diễn dưới dạng vectơ của các số thứ tự, với mỗi phần tử tương ứng với một nguồn. Ngoài ra, bạn có thể nghĩ trạng thái thông điệp của bản sao là một điểm trong không gian D-chiều, nếu bạn muốn.
Giả sử rằng tất cả các bản sao M đã trao đổi các vectơ trạng thái tin nhắn của chúng, vì vậy tất cả chúng đều có ma trận M hàng x D cột của tất cả trạng thái tin nhắn của chúng. Vì vậy, đây hoàn toàn là một vấn đề tính toán tập trung cho ma trận đó.
Phương pháp tiếp cận vũ lực cung cấp câu trả lời tối ưu là kiểm tra tất cả các tập con (M select N) và chọn một yêu cầu số lượng truyền lại tối thiểu cần thiết để đồng bộ hóa tập hợp con đó. Vấn đề là cách tiếp cận này dường như có độ phức tạp tiệm cận ít nhất trong M.
Tôi muốn xem liệu có ai biết hoặc có thể nghĩ ra một thuật toán tối ưu với giới hạn tiệm cận tốt hơn không?
Ban đầu, tôi đã nghĩ đến việc giải quyết vấn đề lý thuyết đồ thị với thông điệp của bản sao là đỉnh trong biểu đồ được kết nối hoàn toàn với trọng số cạnh là khoảng cách Manhattan giữa vectơ trạng thái thông báo của hai thiết bị đầu cuối. Sau đó, thực hiện một số thứ như phân cụm kết hợp phân cấp tối thiểu bằng thuật toán của Prim, theo sau là thuật toán của Kruskal, nơi chúng ta dừng lại khi kích thước của bất kỳ cụm nào bằng hoặc lớn hơn N.
Điều đó có thể chạy trong thời gian O (M^2). ví dụ mà nó không ngay lập tức mang lại câu trả lời tối ưu. Ví dụ, với D = 1 vì mục đích đơn giản, cho phép các bản sao M = 7 bản sao là {0, 2, 4, 14, 15, 16, 19} và N = 5. Thuật toán của Kruskal sẽ cluster {14, 15, 16 , 19} và {0, 2, 4} và sau đó kết hợp hai cụm đó lại với nhau trong bước cuối cùng. Nhưng câu trả lời thực sự chúng tôi muốn là đồng bộ hóa các bản sao với các trạng thái {2, 4, 14, 15, 16} với nhau. Có lẽ chúng ta có thể dừng lại khi cụm được hợp nhất đầu tiên vượt quá N và sau đó cố gắng cắt bớt nó? Nhưng trong ví dụ này, sau đó chúng tôi quay trở lại để hỏi lại câu hỏi ban đầu là cụm mà trên đó chúng tôi đã dừng thực sự chứa tất cả các bản sao M! Và, tất nhiên, vấn đề này không đơn giản như khi D> 1, mà nó sẽ luôn luôn là (D> = M). Một vấn đề khác với cách tiếp cận trên là nếu thuật toán chọn đồng bộ hóa hai cụm bản sao thành một cụm lớn hơn, thì điều này không chỉ ảnh hưởng đến khoảng cách giữa các cụm khác và cụm mới được kết hợp (ví dụ như trong cụm kết tụ thông thường). phân nhóm phân cấp) nhưng cũng là khoảng cách giữa tất cả các cụm khác vì tất cả chúng đều nghe và có thể hưởng lợi từ mọi lần truyền lại được gửi đi. Vì vậy, tất cả khoảng cách giữa tất cả các cụm đều có thể thay đổi sau mỗi bước hợp nhất và theo cách không đơn giản nếu bạn cho phép bản sao hưởng lợi từ các thư nhận được ở đây không phải trong FIFO, thứ tự không có lỗ. Ví dụ, một bản sao A có thông điệp từ nguồn D1 đến thứ tự X. Thuật toán chọn đồng bộ hóa hai cụm bản sao, không bao gồm A, yêu cầu truyền lại thông điệp từ nguồn D1 của X + 5 đến X + 10. Một thuật toán tối ưu sẽ nhận ra rằng A có khả năng mang lại lợi ích từ các truyền lại này mặc dù chúng vượt quá FIFO của mình, không có lỗ thứ tự cho nguồn D1 với khoảng cách thông điệp của X + 1 đến X + 4.
Một cách khác mà tôi nghĩ về giải quyết nó là xem xét nó là một vấn đề hình học mà các trạng thái bản sao M đại diện cho các điểm trong không gian D-chiều L1. Sau đó, chúng tôi muốn tìm vỏ nhỏ nhất "khối lượng" có chứa ít nhất N điểm. Điều này có thể không thực sự là một cách tiếp cận tốt nhưng suy nghĩ về nó một cách tự nhiên về mặt hình học nắm bắt ý tưởng rằng tất cả các bản sao có thể được hưởng lợi từ bất kỳ hai bộ sao chép đồng bộ. Hầu hết khoảng cách của chúng sẽ được giảm xuống bề mặt của đối tượng mới (không phải đỉnh!) Được tạo ra bởi sự hợp nhất của hai trạng thái bộ.
EDIT - Một cách khác tôi nghĩ về nó đến từ ví dụ tôi đưa ra. Đối với mỗi nguồn DX tìm tập con của N bản sao yêu cầu số lượng truyền lại tối thiểu để đồng bộ hóa trên nguồn đó. Điều đó thật dễ dàng. Vấn đề sau đó là sau đó bạn phải so sánh và sửa đổi các tập con D để có được tất cả chúng để trang trải cùng một bản sao N. Nó không phải là một ý tưởng hoàn chỉnh bởi vì N tối thiểu trong mỗi kích thước DX là mức tối thiểu cục bộ trong không gian toàn cầu có thể ở sai khu vực như câu trả lời tối ưu toàn cầu cho thứ nguyên đó. Dù sao, đó là một ý tưởng khác để suy nghĩ.
EDIT2 - Quay lại thuật toán của Prim + Kruskal và bỏ qua mỗi lần hợp nhất cập nhật khoảng cách tương đối giữa tất cả các cụm, đúng là khi chúng ta phát hiện cụm đầu tiên có kích thước bằng hoặc lớn hơn N, thì câu trả lời tối ưu là một số tập con của cụm đó? Nếu kích thước của cụm bằng N, thì chúng ta đã xong. Nếu kích thước của cụm vượt quá N, thì chúng ta có thể làm một cái gì đó như tính toán trọng tâm của cụm sao và chọn N bản sao gần nhất với centroid? Điều đó có mang lại câu trả lời tối ưu không? Điều đó vẫn không có vẻ đúng bởi vì nó không xem xét "hướng" của các khoảng cách khác nhau từ trung tâm. Đó là, nó không phân biệt giữa hai bản sao gần nhau trong không gian D-chiều (mà nó nên ưu tiên) như trái ngược với hai bản sao theo hướng "ngược lại" với nhau đối với trọng tâm. Có lẽ chúng ta có thể thay vào đó nhìn vào cây bao trùm tối thiểu của các bản sao trong cụm và bằng cách nào đó cắt tỉa nó một cách hiệu quả để tìm tập con trọng lượng tối thiểu vẫn còn kết nối?
Bất kỳ ý tưởng hoặc chỉ dẫn nào cho các thuật toán có liên quan sẽ được đánh giá rất nhiều!
Bạn định nghĩa "truyền lại thông điệp" trong vấn đề này như thế nào? Những gì được chứa trong một "thông điệp"? Việc truyền một thông điệp tới tất cả các bản sao có cùng chi phí như truyền tới một bản sao duy nhất không? Tôi cũng không hiểu tại sao {2, 4, 14, 15, 16} là "câu trả lời thực tế" trong ví dụ của bạn. – mhum
@mhum Việc truyền lại thông báo là khi một tin nhắn, đã được biết đến với một hoặc nhiều bản sao hiện tại, được phát đa hướng bởi một trong số chúng tới toàn bộ nhóm. Điều này được thực hiện để giúp các bản sao không biết thông điệp đó để đưa tất cả thông điệp của bản sao tuyên bố gần hơn để được đồng bộ hóa (tức là - bằng nhau). Một thông điệp bao gồm một số byte dữ liệu. Vì lợi ích của sự đơn giản, hãy xem xét từng thông điệp truyền lại với mức chi phí cao như nhau. Có, tất cả các lần truyền đều phát đa hướng và đáng tin cậy với mọi người trong nhóm. – jschultz410
{2, 4, 14, 15, 16} là câu trả lời vì đó là tập hợp con của kích thước N = 5 yêu cầu truyền lại ít nhất để đưa tất cả trạng thái của chúng bằng 16 Tin nhắn từ 3 đến 16 sẽ phải là truyền lại, vì vậy 14 tin nhắn. Các bộ gần tối ưu khác sẽ là {4, 14, 15, 16, 19}, nhưng yêu cầu 5 đến 19 = 15 truyền lại và {0, 2, 4, 14, 15} yêu cầu 1 đến 15 = 15 lần truyền lại. Trong một khía cạnh duy nhất vấn đề này khá dễ dàng, nhưng hãy tưởng tượng nếu có thay vì 7 hoặc 10 kích thước và mỗi bản sao sẽ ở vị trí tùy ý trong mỗi chiều. – jschultz410