Objective

The purpose of this lab is to

• learn about conflict-free replicated data types
• build an eventually consistent distributed system on top of gossip-based messaging

Reading and Reference

Read the following:

• CRDTs explained - supercharge your serverless with CRDTs at the edge
• A Look at Conflict-Free Replicated Data Types (CRDT)

The following optional, additional resources may be helpful:

• CRDTs and the Quest for Distributed Consistency

Prerequisites

You should have completed:

• Lab 8: Gossip Protocols

Implementation Notes

• This lab should be more straightforward than the last one since you're mostly utilizing the gossip infrastructure you created in that lab. 
• The primary work is two-fold: 
  • Generalizing the gossip message system you have already built to handle multiple message types. 
  • Implementing a new temperature threshold violation "operation" message (more below). 
• One implementation detail we can conveniently ignore for an assignment like this is storage. Don't try to conserve storage for this assignment. Never optimize pre-maturely. 

Conflict-Free Replicated Data Types (CRDTs)

If you have used Google Docs, then you're familiar with the idea of eventual consistency. Even though multiple people are editing the same document, sometimes even the same sentence, everyone's copy of the document eventually converges to a single view. Conflict-Free Replicated Data Types (CRDTs) provide a general-purpose way to provide eventually consistent data structures among decentralized participants. In this lab, you will use the gossip network you created in Lab 8 to create a shared global counter of the total number of nodes in the temperature network with a threshold violation despite not have a fully connected network, a central hub (other than for convenience in operating the network), or a distinguished leader. 

You have already implemented one simple state-oriented CRDT in Lab 8 to share state for each sensors temperature. There wasn't really any room for conflict however since every node was merely updating its own state and gossiping about the temperatures. Nevertheless, the algorithm was designed to achieve consistency among all nodes about the state of temperatures in the system. 

In this lab, you will extend the gossip network so that rumors can include threshold counter messages in addition to temperatures. You will be implementing an operation-oriented CRDT that uses an increment message. The message will carry a payload of 1, 0, or -1 depending on whether the node is reporting that it is experiencing, is still experiencing, or no longer experiencing a threshold violation. Each node will use these messages to update its threshold violation counter. 

Do This

1. Implement the the threshold violation counter described above using a incrementing/decrementing CRDT.
   • The increment/decrement messages can just be another message type that you propagate as a rumor. 
   • You will need to update your message infrastructure to support multiple types of rumor messages. 
2. Test it by running using the gossip network you created for Lab 9.
   • Create a network of picos using subscriptions. You can use the Wovyn sensor emulator for this lab. You do not need to connect to picos from other students. 
   • You'll need to a large enough network for the test to be interesting.
   • Set the range in the sensor emulator so that you occasionally get threshold violations.
3. Watch the network, you should observe counters for different nodes in different states. If you stop all the emulators from emitting temperatures (or set the period to a very long time), you should notice that the node come into consistency about how many threshold violations there were. 
4. Use this to method you devised for Lab 9 to enable or disable gossiping to turn off one pico. After a time, turn the stopped pico back on. Did it catch up?

Deliverables

Turn in the following:

1. URLs for the rulesets you created
2. Short screencast (< 5 min with sound) showing how your system works, message propagation, and how nodes come into consistency. 
3. Answers to the following questions:

Questions

1. Did you use a single message identifier for all message types in your system, or different one for each type of message? Why?  
2. Did you have to change how your seen messages worked? Why or why not? 
3. How did the state-oriented CRDT we used for Lab 9 differ from the operation-oriented CRDT we used in this lab? 
4. Is it possible for a node to issue two positive threshold violation messages (i.e. value = 1) without an intervening negative threshold violation messages (i.e. value = -1)? Justify your analysis. What are the consequences of such a scenario?  
5. How does gossip messaging combined with CRDT compare with Paxos? Consider the threshold counter we implemented for this lab. How would it be different if you tried to use Paxos to implement it? 
6. How does gossip messaging combined with CRDT compare with Byzantine consensus (like in a blockchain)? 

Hint: for the last two questions, consider whether consensus, consistency, and convergence are the same thing. Also, consider the goals of different algorithms.