Apply Conflict-Free Replicate Data Type

[luhuimao]

In distributed computing, a conflict-free replicated data type (CRDT) is a data structure which can be replicated across multiple computers in a network, where the replicas can be updated independently and concurrently without coordination between the replicas, and where it is always mathematically possible to resolve inconsistencies which might result.
The CRDT concept was formally defined in 2011 by Marc Shapiro, Nuno Preguiça, Carlos Baquero and Marek Zawirski. Development was initially motivated by collaborative text editing and mobile computing.

[luhuimao]

These modules need to be included to the proposed package

• Serialization
• Module
• Spending Module
• Gossip Protocol Control Module
• Counter Module
• Hash Module
• Ledger Module
• Logging Module
• Net Utility Module
• Packet (UDP) Module
• Math Module (Including some random generator module)
• Standard Module

to be expaned upon requeste

[luhuimao]

Implemented Functionality

NodeInfo interface

A NodeInfo structure represents a client info consists of pubkey , current leader_id etc

Exposed interface:

- new_localhost(id: Pubkey): Create a NodeInfo structure with a PubKey
- 
- next_port(addr: &SocketAddr, nxt: u16): Modify addr's port by adding with nxt
- 
- new_with_pubkey_socketaddr(pubkey: Pubkey, bind_addr: &SocketAddr): Create a NodeInfo structure with pubkey and socketaddr
- 
- new_with_socketaddr(bind_addr: &SocketAddr): Create a NodeInfo structure with SocketAddr
- 
- new_entry_point(gossip_addr: &SocketAddr): Create a NodeInfo structure with passed in parameter gossip_addr and a "0.0.0.0:0" SocketAddr

Node interface

A Node structure consists of a NodeInfo structure and all kinds of UDP sockets

Exposed interface:

- new_localhost(): Create a Node structure with a new pubkey
- 
- new_localhost_with_pubkey(pubkey: Pubkey): Create a Node structure with passed in parameter pubkey
- 
- new_with_external_ip(pubkey: Pubkey, ncp: &SocketAddr): Create a Node structure with passed in parameters pubkey && ncp

Crdt interface

Crdt structure keeps a table of NodeInfo structs consists of a table that hold everyone in the network, pubkey etc.

- new(node_info: NodeInfo): Create a Crdt structure with a NodeInfo instance
- 
- my_data(&self): Return a NodeInfo instance by crdt.id
-  
- leader_data(&self): Return a leader NodeInfo
- 
-node_info_trace(&self) -> String : format return node info
-
-set_leader(&mut self, key: Pubkey): update the specified leader node
-
-get_scheduled_leader(&self, entry_height: u64) -> Option<Pubkey>: Return the leader id
-
-set_leader_rotation_interval(&mut self, leader_rotation_interval: u64): Set leader rotation interval
-
-get_leader_rotation_interval(&self) -> u64: Get leader rotation interval
-
-set_scheduled_leader(&mut self, entry_height: u64, new_leader_id: Pubkey) -> () : Insert new leader id in to the scheduled_leaders map
-
-get_valid_peers(&self) -> Vec<NodeInfo> : Get valid peers from table except local node
-
-get_external_liveness_entry(&self, key: &Pubkey) -> Option<&HashMap<Pubkey, u64>>: 
-
-insert_vote(&mut self, pubkey: &Pubkey, v: &Vote, last_id: Hash): update node by given pubkey and insert to the table
-
-insert_votes(&mut self, votes: &[(Pubkey, Vote, Hash)]): Calling insert_vote
-
- insert(&mut self, v: &NodeInfo): Insert a Node to the table
-
-update_liveness(&mut self, id: Pubkey): update node with current time in liveness table by given pubkey
-
-purge(&mut self, now: u64): Purge the old validators
-
-compute_broadcast_table(&self) -> Vec<NodeInfo>: compute broadcast table
-
-broadcast(): broadcast messages from the leader to layer 1 nodes
-
- retransmit(obj: &Arc<RwLock<Self>>, blob: &SharedBlob, s: &UdpSocket) -> Result<()>: retransmit messages from the leader to layer 1 nodes
-
-convergence(&self) -> u64 : Return the max number of nodes that we could be converged to
-
-get_updates_since(&self, v: u64) -> (Pubkey, u64, Vec<NodeInfo>): 
-
-valid_last_ids(&self) -> Vec<Hash>： Return the nodes's last_id whose tpu addr and tvu add is valid
- broadcast(): broadcast messages from the leader to layer 1 nodes
- 
-window_index_request(&self, ix: u64) -> Result<(SocketAddr, Vec<u8>)>: find valid peers and send RequestWindowIndex
- 
-gossip_request(&self) -> Result<(SocketAddr, Protocol)>: Create a random gossip request
-
-new_vote(&mut self, last_id: Hash) -> Result<(Vote, SocketAddr)>: Create new vote and insert in to table
-
-run_gossip(obj: &Arc<RwLock<Self>>, blob_sender: &BlobSender) -> Result<()>: At random pick a node and try to get updated changes from them
-
-top_leader(&self) -> Option<Pubkey>: Return the last node from the table sorted by pubkey
- retransmit(): retransmit messages from the leader to layer 1 nodes
- 
-update_leader(&mut self): 
- 
-apply_updates(): Apply updates that we received from the identity `from`
run_window_request()
-
- gossip(): randomly pick a node and ask them for updates asynchronously
-
-run_window_request():
-
-handle_blob(): calling handle_protocol
-
-handle_protocol(): Process request from the network
-
- run_listen():Process messages from the network
- 
-listen(): calling run_listen()
-
- is_valid_address(addr: &SocketAddr): Validate passed in parameter SocketAddr if valid
-
-spy_node() -> (NodeInfo, UdpSocket)

[luhuimao]

More information about CRDT:

//! The crdt module defines a data structure that is shared by all the nodes in the network over
//! a gossip control plane. The goal is to share small bits of off-chain information and detect and
//! repair partitions.
//!
//! This CRDT only supports a very limited set of types. A map of Pubkey -> Versioned Struct.
//! The last version is always picked during an update.
//!
//! The network is arranged in layers:
//!
//! * layer 0 - Leader.
//! * layer 1 - As many nodes as we can fit
//! * layer 2 - Everyone else, if layer 1 is 2^10, layer 2 should be able to fit 2^20 number of nodes.