Kiểm tra sự tương đương giữa các tập phân tán

• Tôi có các yếu tố từ $\{0, 1\}^{n}$ (phạm vi của hàm băm)
• Sư phụ $A$ có thể có bất kỳ tập hợp con nào của phạm vi này.
• Có những khách hàng mà mỗi khách hàng cũng có một tập hợp con từ không gian.
• Tôi muốn đảm bảo rằng sự kết hợp của các bộ khách hàng bằng với bộ chính
• Việc giao tiếp nên càng ít càng tốt.
• Các yếu tố là bí mật. (yêu cầu này có thể được nới lỏng với một giải pháp có khả năng bị rò rỉ)

cảm ơn @kelalaka đã tinh chỉnh câu hỏi.

Một lựa chọn tiềm năng sẽ là sử dụng bộ lọc hoa để xác định tiềm năng trùng lặp theo xác suất, sau đó kiểm tra xem chúng có thực sự là trùng lặp hay không bằng cách gửi một số tiềm năng. Nếu bạn sử dụng các bộ lọc nở hoa đủ lớn thì điều này sẽ đủ cho mọi kích thước.

Ngoài ra, có thể không phù hợp lắm, bạn có thể sử dụng tiểu thư.

Từ phần đọc,

Các bản phác thảo do thư viện này tạo ra có thể được coi là "thiết lập tổng kiểm tra" với hai thuộc tính đặc biệt:

1. Bản phác thảo có dung lượng được xác định trước và khi số lượng phần tử trong bộ không cao hơn dung lượng, libminisketch sẽ luôn khôi phục toàn bộ bộ từ bản phác thảo. Một bản phác thảo của các phần tử b-bit với dung lượng c có thể được lưu trữ trong bc bit.
2. Các bản phác thảo của hai tập hợp có thể được kết hợp bằng cách cộng chúng (XOR) để có được một bản phác thảo về sự khác biệt đối xứng giữa hai tập hợp (nghĩa là tất cả các phần tử xuất hiện trong một chứ không phải cả hai tập hợp đầu vào).

Vì vậy, giả sử bạn sử dụng dung lượng đủ lớn, bạn chỉ cần XOR các bản phác thảo để xác định các phần tử duy nhất và loại bỏ phần còn lại.