# How to broadcast <br>in distributed system --- ## Traditional way Server - Client ```graphviz digraph{ Client->Server; Server->client_a; Server->client_b; Server->client_c; } ``` What if server is dead? --- P2P ```graphviz digraph{ a->b; a->c; a->d; a->e; } ``` May be fine within 10 peers. How about 1000? --- ## Divide loading/connections into small pieces --- Binary (out) tree ```graphviz digraph{ 1->2; 1->3; 2->4; 2->5; 3->6; 3->7; 4->8; 4->9; 5->10; 5->11; 6->12; 6->13; 7->14; 7->15; } ``` ---- * 1 in 2 out * Generated/Regenerated with PRNG. Quick indexing on root, parent, child and sibling * Propagation time: $$ log_2(N)\times 0.5AVG(RTT) $$ ---- * SPOF. Messy failure detection and recovery. Additional work load on nodes required. * detect child timeout * Parent/Sibling to take the job over * Sync with parent and take the job back when recovered --- Tight circular binary (out) tree ```graphviz digraph{ 1->4; 1->6; 2->4; 2->5; 3->5; 3->6; 4->7; 4->9; 5->7; 5->8; 6->8; 6->9; } ``` ---- <img height="600" src="https://i.imgur.com/tjJfuwM.png"></img> ---- * 2 in 2 out * Generated/Regenerated with PRNG. Quick indexing on root, parent, child and sibling * Propagation time: $$N/r \times 0.5AVG(RTT)$$ * Probability of failing (2 sibling nodes in same layer): $$p^2\times \frac{rk}{\binom{rk}{2}}= p^2\times \frac{2}{rk-1}$$ --- ## Hybrid approach ```graphviz digraph{ 1->TCBT1; 1->3; TCBT1->4; TCBT1->TCBT2; 3->6; 3->TCBT3; 4->8; 4->TCBT6; TCBT2->10; TCBT2->11; 6->12; 6->TCBT4; TCBT3->14; TCBT3->TCBT5; } ``` --- ## prerequisite * IP address of every node is known (public, local) * ~~If not, additional routing may be needed. (Steiner tree)~~ * ~~To find a core node group that can reach every other node: k-clique problem.~~ Note: IP address of every node is known to everyone and can be directly accessed. If not, additional routing is needed. Steiner tree problem. To find a core node group that can reach every other node: k-clique problem. --- ## More... * Can not only be used on broadcasting, but also on task distributing (actually still kind of broadcasting) * Haven't reach Consensus. Reordering * small scale BFT. Can try 3 in 3 out for more capability of FT