Giao thức tin đồn đơn giản cho định tuyến hàng đợi ICMP

trên cấu trúc cây mới (lá) B

Khai báo tiêu đề khối chuỗi mới của nút (ngang hàng) k

k từ mô-đun t đang ở trong Hàng đợi tin nhắn m

Định nghĩa nút lớp ngang hàng (ngang hàng) k trên 〖được phép〗_k (m)

• Định kỳ

• cải tiến trong tương lai

Trong mạng Polkadot, chúng ta cần gửi thông tin cho một số thực thể (entity), trước tiên chúng ta hãy phân loại ngắn gọn các loại thực thể này: (1) người dùng, (2) người thu thập, (3) người xác minh

Tất cả thông tin về parachain trong thời gian chạy đều đến từ

Nguồn ứng cử viên này được tạo bằng cách xác thực các khối ứng cử viên parachain và được đưa vào các khối chuỗi chuyển tiếp. Thí sinh có nhiều lĩnh vực. Dưới đây là một số cái có liên quan:

Rễ đi ra:

Khi khối chuỗi chuyển tiếp B được bao gồm trong parachain p, mỗi giá trị băm được ghép nối với parachain y duy nhất là R(E_(p,y)^B)

Khi dữ liệu nhận được dành cho parachain p, một

giá trị. Bộ thực thi coi giá trị mà nó nhận được từ chuỗi ứng cử viên của parachain gần nhất là giá trị hiện tại. Giá trị ban đầu của B trong bất kỳ khối nào chứa ứng cử viên ít nhất phải cao bằng giá trị trước đó của hình mờ p.

(cướp: lối ra đang chờ xử lý không trống trong danh sách trống không được phép)

Cả người xác minh và người thu thập đều cố gắng thu thập thông tin hàng đợi khối trên khối B hoặc người xác minh chỉ gọi 〖Ingress〗_(B,P) và tìm kiếm các tin nhắn có liên quan trong nhóm lan truyền, chờ đợi các tin nhắn chưa được phát hành. Mục tiêu của bộ đối chiếu trên P là xây dựng trên chuỗi chuyển tiếp gốc B, để có được tiền tố của P_INGRESS (B,P) càng nhiều càng tốt.

R(P_INGRESS (B,Cách dễ nhất là sử dụng . Tin nhắn được chuyển từ mạng parachain này sang mạng parachain khác. Nếu có một nút chung giữa hai mạng này đang phát tin nhắn, thì tin nhắn sẽ khiến liên kết song song đang nhận tin nhắn nhận được tin nhắn của nó. Tuy nhiên, nếu người xác thực của parachain mục tiêu nhận ra rằng thông báo không được truyền đến người nhận của parachain, thì họ sẽ yêu cầu lại thông báo từ nút trình xác nhận của parachain đã gửi tin nhắn, sau đó họ sẽ nhận được thông báo đó trên bản thân parachain.thiết bị để nhân giống.

P)) có sẵn ở mọi khối B và parachain p khi chạy.

Tính khả dụng của parachain p và khối B là do p và B là danh sách đầu vào của các gốc đầu vào đang chờ xử lý cho khối đó và mỗi danh sách và gốc được ghép nối đầu tiên với số khối được định tuyến. Bỏ qua R(∅) khỏi danh sách xâm nhập và bỏ qua danh sách trống và sắp xếp theo số khối tăng dần. trong đó tất cả các số khối đều nhỏ hơn num(B) và đề cập đến các khối trong cùng một chuỗi.

Mã giả trong RUST (TODO: Transcribe to LaTeX)

Dữ liệu từ hàng đợi đi ra cho một B và p nhất định vẫn có sẵn trong thời gian chạy, tuân theo các ràng buộc giống như danh sách vào w.r.t. sắp xếp thứ tự và bỏ qua các danh sách trống. ParaId ở đây là chuỗi nhận và trong hàm nhập (ingress) là chuỗi gửi.

Giả sử rằng cấu trúc cây rời khỏi khối là khối parachain mới nhất trong chuỗi chuyển tiếp.

Chúng tôi đưa ra các giả định sau về các nút:

1. Trạng thái khối của các lá ở cuối cấu trúc cây có sẵn, nhưng không thể đảm bảo trạng thái của khối cũ

2. Có thể mong đợi rằng các bộ đối chiếu và các nút đầy đủ trên parachain sẽ giữ lại tất cả các khối đã được thực thi trên parachain.

3. Trình xác thực không cần giữ bất kỳ khối nào. Cũng xin lưu ý rằng thông tin có thể được khôi phục từ các đoạn mã xóa được lưu bởi trình xác thực

Chương này mô tả một giao thức tin đồn giới hạn để truyền các hàng đợi của các bản tin ICMP (xem phần Tổng quan để biết định nghĩa).

Và

Và

Vì lối vào đã được gọi trên khối B, chúng ta có thể dễ dàng đặt

để chuyển đổi

Tin nhắn bắt đầu ở trạng thái không định tuyến và kết thúc ở trạng thái định tuyến

Chúng tôi đề xuất xác định một hệ thống lan truyền tin đồn

Thông báo về mô-đun này có dạng

Chúng tôi giữ thông tin địa phương như:

1. 〖leaves〗_k là danh sách hàm băm tốt nhất cho các điểm cuối (lá) của cấu trúc cây khối DAG của chúng tôi cần thực thi mã

2. 〖leaves〗_k, đối với mỗi peer k, danh sách mới nhất tốt nhất cần thực thi mã MAX_CHAIN_HEADSDAG giá trị băm của khối (dựa trên những gì họ đã gửi cho chúng tôi)

3. leafTopics(l)→{queueTopic(h)} có nghĩa là gốc h chưa được mở rộng trên chuỗi song song trên nút cây l trên tất cả các cấu trúc cây (lá)

4.expectedQueues(t)→H chỉ ra quá trình dẫn xuất của hàm băm tương ứng của tất cả các mô-đun gọi và t∈∪l_(∈leaves)leafTopics(l) trong tất cả các mục

trên cấu trúc cây mới (lá) B

1. Nâng cấp cấu trúc cây (lá), mô-đun cây (leafTopics) và hàng đợi dự kiến ​​(thử nghiệm điểm chuẩn chưa được thực hiện nhưng ước tính thận trọng sẽ có thời gian chạy là 100 mili giây)

2. Gửi cấu trúc cây (lá) mới của cùng một lớp

3. Nếu bộ thu của chuỗi song song p thực thi mã egress(B,p) trực tuyến. Đối với bất kỳ gốc hàng đợi tin nhắn đã biết nào chưa được truyền bá, chúng tôi sẽ đặt thông báo Hàng đợi tương ứng vào nhóm truyền bá.

Khai báo tiêu đề khối chuỗi mới của nút (ngang hàng) k

1. Nâng cấp cấu trúc cây (lá) 〖lá〗_k

2. Để đáp ứng yêu cầu của ∀H∈leaves ∩ 〖leaves〗_k, mỗi t trong BroadcastTopic(k,t) được ánh xạ trên leafTopics(H)

k từ mô-đun t đang ở trong Hàng đợi tin nhắn m

chúng tôi xác định chức năng

Là một tiêu chuẩn tự tin cục bộ cục bộ (local Acceptance criteria).

gốc băm của tin nhắn

Trên chức năngexpectedQueues(t) được xác định, gốc thực của thông báo đã cho bằng gốc

Nếu hàm good(m) chứng minh rằng k dương, hãy đặt m vào nhóm lan truyền, nếu không, hãy chứng minh rằng m không khả dụng, điều này hữu ích cho việc canh tác tập hợp ngang hàng.

Định nghĩa nút lớp ngang hàng (ngang hàng) k trên 〖được phép〗_k (m) và Thông báo xếp hàng m trên mô-đun t

Nếu tin nhắn k được gửi cho chúng tôi trước khi chúng tôi gửi xong tin nhắn, tin nhắn k sẽ bị từ chối. Ngược lại, nếu sau

∃l∈leaves∩〖〖leaves〗_k|t∈leafTopics(l)∃l∈leaves∩〖leaves〗_k | t∈leafTopics(l), thì tin nhắn k được cho phép và các phương thức khác bị cấm.

Định kỳ

Ngoại trừ các hàng đợi mong đợi, chúng ta cần đánh dấu tất cả các mô-đun là các mô-đun đã hết hạn và xóa chúng trong vùng lan truyền. Trên thực tế, các thao tác như vậy được thực hiện cứ sau vài giây. Điều này ngăn nhóm nhân giống của chúng tôi phát triển vô thời hạn.

Quyết định chỉ truyền bá các tin nhắn chưa được định tuyến tới những người có cùng quan điểm về bản mod hiện tại có thể gây tranh cãi, nhưng một số điều kiện tiên quyết mà chúng tôi đưa ra đã thể hiện khá rõ quan điểm này.

Đầu tiên, chúng tôi không muốn nút phải xử lý vô số thông báo, điều đó có nghĩa là nút H trong queueTopic(H) không xác định được vì có vô số H như vậy. Thứ hai, các nút không phải thực hiện nhiều công việc để quyết định có truyền một thông điệp tới một đồng nghiệp cụ thể hay không. Giả sử lá∩〖lá〗_k=∅, nhưng một số mục của 〖lá〗_k là mã nguồn của lá

(tổ tiên). Ta phải chạy mọi l ∈ 〖lá〗_k trong O(n) để chứng minh. Sau đó, chúng tôi phải tìm hiểu xem một tin nhắn đã cho có bị hủy định tuyến trên khối trước đó hay không. Chúng tôi ngây thơ nghĩ rằng nếu một tin nhắn vẫn chưa được định tuyến trên một số khối sau này trong cùng một chuỗi, thay vì được định tuyến trong một chuỗi trước đó, thì điều đó khó có thể xảy ra nhưng trạng thái của chuỗi có thể là khôi phục lừa đảo tại nút của con người.

Vì trạng thái chuỗi giả định không có sẵn từ các khối trước đó, nên chúng tôi không có cách nào tốt để xác định xem có thực sự gửi một đầu ra đến một ngang hàng của khối trước đó hay không. Trong phần cải tiến trong tương lai, chúng tôi sẽ thảo luận về việc nới lỏng giới hạn này bằng cách mở rộng quy mô thành một số nguồn gốc (tổ tiên) cố định.

Tuy nhiên, chỉ hợp lý khi truyền tới các nút (ngang hàng) đã được đồng bộ hóa với cùng một chuỗi, giả sử như sau (một số kinh nghiệm nhưng hợp lý, nhưng cũng có khả năng được đánh giá quá cao):

1. Các khối hợp lệ mới được phát hành trong khoảng thời gian trung bình ít nhất là 5 giây (mục tiêu của chúng tôi thực tế là 10-15 giây)

2. Thời gian lan truyền của khối trong phần "hữu ích" của cấu trúc lan truyền tin đồn là trong vòng 2 giây.

3. Các đối tượng liền kề trong cấu trúc lan truyền tin đồn có độ trễ nhỏ hơn hoặc bằng 500ms

4. Tuyên truyền thông điệp có ý nghĩa trước khi đồng bộ với người đứng đầu DAG có thể không đáng

Giá trị thực tế gần như chắc chắn sẽ tốt hơn. Tin tốt là không phải tất cả các khối đều phải được lan truyền trong một thời gian khối - khi thời gian trôi qua, người tham gia ngày càng có thể nhận được các tin nhắn sớm hơn. Đây là một chương trình mà tất cả những người tham gia đều nhìn thấy tất cả các tin nhắn. Nó gần như chắc chắn sẽ không mở rộng ra ngoài một số chuỗi ban đầu, mà thay vào đó sẽ hoạt động đúng chức năng như một giao thức khởi động.

tiêu đề phụ

Tổng quan về Định tuyến XCMP

Để gửi tin nhắn từ một parachain (parachain gửi) đến một parachain khác (parachain nhận) theo thiết lập, các bước sau đây sẽ được thực hiện.

Tin nhắn là đủ khi nút đầy đủ của parachain gửi cũng là một phần của miền của parachain nhận

Trình xác thực parachain của parachain nhận không phát hiện ra rằng thông báo được lan truyền và sau đó nó trực tiếp yêu cầu thông báo từ trình xác thực parachain của parachain gửi (gửi PV thời gian thực). PV của parachain gửi chịu trách nhiệm giữ cho tin nhắn có sẵn. Trình xác minh parachain gửi parachain trực tiếp gửi tin nhắn đến PoV của parachain nhận, và cuối cùng PV của parachain nhận phát tán tin đồn (tin đồn) về tin nhắn trong mạng parachain nhận.

tiêu đề phụ

cải tiến trong tương lai

1. Phần trên mô tả lý do tại sao không nên truyền hàng đợi đầu ra một cách tùy tiện vào lớp ngang hàng, nhưng một khi chúng tôi đồng bộ hóa và tuân theo quy trình sản xuất khối thông thường, chúng tôi có thể theo dõi hợp lý tất cả các cây Mã nguồn cuối cùng (tổ tiên) α của trúc (lá). Giá trị hợp lý ban đầu của α phải nhất quán với giá trị gốc và lấy 1. Điều này có thể mang lại cho chúng tôi 90% mức tăng mà chúng tôi cần, đơn giản vì có hiện tượng "nói lắp" khi yêu cầu giao điểm của bộ cây và hai đồng nghiệp cần Cập nhật cho nhau thông tin về các khóa con mới.

2. Mở rộng định nghĩa của E_(x,y)^B có thể cho phép kiểm tra lẫn nhau giữa các chuỗi. Ví dụ: parachain y có thể yêu cầu chuỗi chuyển tiếp không định tuyến tin nhắn từ x tại khối B (và sau đó yêu cầu nó bắt đầu định tuyến lại tại khối B'). Đối với bất kỳ khối nào giữa B và B', chúng tôi sẽ có thời gian chạy là E_(x,y)^b=∅ khi bỏ qua x của b trên Biên nhận Ứng viên. Trên thực tế, vì bộ thực thi chỉ xử lý hàm băm gốc của hàm băm, nên nó thực sự chỉ bỏ qua R(E_(x,y)^b) khỏi biên nhận ứng viên và đặt nó thành R(∅)

3. Mở rộng quy mô để hỗ trợ các cấu trúc liên kết thông minh hơn, nơi không phải ai cũng có thể nhìn thấy mọi thứ. Có lẽ việc có hai loại mảng chủ đề (Topics), (B, (B,〖chuỗi〗_từ)) dựa trên mảng chủ đề (Topics) và mod dựa trên (B,〖chuỗi〗_to) sẽ cải thiện khả năng sử dụng của bản mod này.https://github.com/sipa/minisketch4. Sử dụng một số loại đối chiếu thiết lập thông minh (ví dụ: