From bd0ca41936a724619e31d6930b554bc12697768d Mon Sep 17 00:00:00 2001
From: Aviral Goel <goel.aviral@gmail.com>
Date: Sat, 17 Dec 2016 01:03:30 -0500
Subject: Added images for counter example, need to work on text

---
 chapter/6/counters.md                              | 122 +++++++++++++++++++++
 ...ation-based-increment-and-decrement-counter.png | Bin 0 -> 259325 bytes
 .../operation-based-increment-only-counter.png     | Bin 0 -> 236423 bytes
 ...sed-increment-and-decrement-counter-correct.png | Bin 0 -> 250168 bytes
 ...d-increment-and-decrement-counter-incorrect.png | Bin 0 -> 247402 bytes
 .../state-based-increment-only-counter-correct.png | Bin 0 -> 240649 bytes
 ...tate-based-increment-only-counter-incorrect.png | Bin 0 -> 241905 bytes
 7 files changed, 122 insertions(+)
 create mode 100644 chapter/6/counters.md
 create mode 100644 chapter/6/images/counters/operation-based-increment-and-decrement-counter.png
 create mode 100644 chapter/6/images/counters/operation-based-increment-only-counter.png
 create mode 100644 chapter/6/images/counters/state-based-increment-and-decrement-counter-correct.png
 create mode 100644 chapter/6/images/counters/state-based-increment-and-decrement-counter-incorrect.png
 create mode 100644 chapter/6/images/counters/state-based-increment-only-counter-correct.png
 create mode 100644 chapter/6/images/counters/state-based-increment-only-counter-incorrect.png

(limited to 'chapter')

diff --git a/chapter/6/counters.md b/chapter/6/counters.md
new file mode 100644
index 0000000..c441e6e
--- /dev/null
+++ b/chapter/6/counters.md
@@ -0,0 +1,122 @@
+---
+layout: page
+title:  "Counters"
+by: "Aviral Goel"
+---
+
+Counters are replicated integers. They are the most basic distributed object. This chapter describes the different variations of counter CRDT in both state based and operation based form.
+
+## G-counter - Increment only counter
+
+As the name suggests, these counters only support increment operation. They can be used to implement the `like` button functionality of social media websites.
+
+### CmRDT: Operation based G-counter
+
+In the operation based implementation, the increment operation is transmitted to all other replicas. 
+This is straightforward to implement as there is only one update operation. 
+
+#### Specification
+
+
+#### Figure
+
+![Operation based increment only counter][operation-based-increment-only-counter]
+
+
+### CvRDT: State based specification
+
+In the state based implementation, the counter state is transmitted to all other replicas.
+But how do we model the state? Of course, the counter's count is its state. 
+Since the count always increases, modeling the state as count automatically makes it a monotonic semilattice.
+
+#### Specification
+
+
+#### Figure
+
+![State based increment only counter (incorrect)][state-based-increment-only-counter-incorrect]
+As it can be seen from the figure, the clients issue a total of 4 increment requests. However, the replicas finally converge to 2.
+Something is clearly amiss! When two replicas are incremented, they should together converge to 2. But the `merge` function computes the maximum of two states. 
+
+
+#### Specification
+
+
+#### Figure
+
+![State based increment only counter (correct)][state-based-increment-only-counter-correct]
+
+As it can be seen from the figure, the clients issue a total of 4 increment requests. However, the replicas finally converge to 2.
+Something is clearly amiss! When two replicas are incremented, they should together converge to 2. But the `merge` function computes the maximum of two states. 
+
+
+
+
+
+## PN-counter - Increment and Decrement counter
+
+### CmRDT: Operation based specification
+
+#### Specification
+
+#### Figure
+
+![Operation based increment and decrement counter][operation-based-increment-and-decrement-counter]
+
+### CvRDT: State based specification
+
+#### Specification
+
+
+
+#### Figure
+
+![State based increment and decrement counter (incorrect)][state-based-increment-and-decrement-counter-incorrect]
+
+
+
+#### Specification
+
+
+
+#### Figure
+
+![State based increment and decrement counter (correct)][state-based-increment-and-decrement-counter-correct]
+
+## Non-negative Counter
+
+
+
+
+
+### State based specification (CmRDT)
+
+```javascript
+class 
+    counts = [0, 0, ..., 0]
+    
+    update increment()
+        g <- getId()
+        counts[g] <- counts[g] + 1
+    
+    // query function
+    function value():
+        sum = 0
+        for count in counts:
+            sum <- sum + count
+        return sum
+    
+    function compare(other):
+        for i in 0 : length(replicas()):
+            if counts[i] > other.counts[i]:
+                return False
+        return True
+    
+```
+
+[operation-based-increment-only-counter]: images/counters/operation-based-increment-only-counter.png
+[state-based-increment-only-counter-incorrect]: images/counters/state-based-increment-only-counter-incorrect.png
+[state-based-increment-only-counter-correct]: images/counters/state-based-increment-only-counter-correct.png
+[operation-based-increment-and-decrement-counter]: images/counters/operation-based-increment-and-decrement-counter.png
+[state-based-increment-and-decrement-counter-incorrect]: images/counters/state-based-increment-and-decrement-counter-incorrect.png
+[state-based-increment-and-decrement-counter-correct]: images/counters/state-based-increment-and-decrement-counter-correct.png
diff --git a/chapter/6/images/counters/operation-based-increment-and-decrement-counter.png b/chapter/6/images/counters/operation-based-increment-and-decrement-counter.png
new file mode 100644
index 0000000..f046c0b
Binary files /dev/null and b/chapter/6/images/counters/operation-based-increment-and-decrement-counter.png differ
diff --git a/chapter/6/images/counters/operation-based-increment-only-counter.png b/chapter/6/images/counters/operation-based-increment-only-counter.png
new file mode 100644
index 0000000..398c562
Binary files /dev/null and b/chapter/6/images/counters/operation-based-increment-only-counter.png differ
diff --git a/chapter/6/images/counters/state-based-increment-and-decrement-counter-correct.png b/chapter/6/images/counters/state-based-increment-and-decrement-counter-correct.png
new file mode 100644
index 0000000..0d6468b
Binary files /dev/null and b/chapter/6/images/counters/state-based-increment-and-decrement-counter-correct.png differ
diff --git a/chapter/6/images/counters/state-based-increment-and-decrement-counter-incorrect.png b/chapter/6/images/counters/state-based-increment-and-decrement-counter-incorrect.png
new file mode 100644
index 0000000..3f7f1b9
Binary files /dev/null and b/chapter/6/images/counters/state-based-increment-and-decrement-counter-incorrect.png differ
diff --git a/chapter/6/images/counters/state-based-increment-only-counter-correct.png b/chapter/6/images/counters/state-based-increment-only-counter-correct.png
new file mode 100644
index 0000000..4ca2843
Binary files /dev/null and b/chapter/6/images/counters/state-based-increment-only-counter-correct.png differ
diff --git a/chapter/6/images/counters/state-based-increment-only-counter-incorrect.png b/chapter/6/images/counters/state-based-increment-only-counter-incorrect.png
new file mode 100644
index 0000000..3f95e59
Binary files /dev/null and b/chapter/6/images/counters/state-based-increment-only-counter-incorrect.png differ
-- 
cgit v1.2.3


From 8956b27b29637a452d0603658f9646b324d904ed Mon Sep 17 00:00:00 2001
From: Aviral Goel <goel.aviral@gmail.com>
Date: Sat, 17 Dec 2016 16:31:29 -0500
Subject: Added specification of counters, moved images to resources

---
 chapter/6/counters.md                              | 215 ++++++++++++++++++---
 ...ation-based-increment-and-decrement-counter.png | Bin 259325 -> 0 bytes
 .../operation-based-increment-only-counter.png     | Bin 236423 -> 0 bytes
 ...sed-increment-and-decrement-counter-correct.png | Bin 250168 -> 0 bytes
 ...d-increment-and-decrement-counter-incorrect.png | Bin 247402 -> 0 bytes
 .../state-based-increment-only-counter-correct.png | Bin 240649 -> 0 bytes
 ...tate-based-increment-only-counter-incorrect.png | Bin 241905 -> 0 bytes
 ...ration-based-increment-and-decrement-counter.py |  20 ++
 .../operation-based-increment-only-counter.py      |  15 ++
 ...ased-increment-and-decrement-counter-correct.py |  47 +++++
 ...ed-increment-and-decrement-counter-incorrect.py |  31 +++
 .../state-based-increment-only-counter-correct.py  |  28 +++
 ...state-based-increment-only-counter-incorrect.py |  19 ++
 ...ation-based-increment-and-decrement-counter.png | Bin 0 -> 259325 bytes
 .../operation-based-increment-only-counter.png     | Bin 0 -> 236423 bytes
 ...sed-increment-and-decrement-counter-correct.png | Bin 0 -> 250168 bytes
 ...d-increment-and-decrement-counter-incorrect.png | Bin 0 -> 247402 bytes
 .../state-based-increment-only-counter-correct.png | Bin 0 -> 240649 bytes
 ...tate-based-increment-only-counter-incorrect.png | Bin 0 -> 241905 bytes
 chapter/6/resources/images/partitioned-network.jpg | Bin 0 -> 24303 bytes
 chapter/6/resources/partitioned-network.jpg        | Bin 24303 -> 0 bytes
 21 files changed, 344 insertions(+), 31 deletions(-)
 delete mode 100644 chapter/6/images/counters/operation-based-increment-and-decrement-counter.png
 delete mode 100644 chapter/6/images/counters/operation-based-increment-only-counter.png
 delete mode 100644 chapter/6/images/counters/state-based-increment-and-decrement-counter-correct.png
 delete mode 100644 chapter/6/images/counters/state-based-increment-and-decrement-counter-incorrect.png
 delete mode 100644 chapter/6/images/counters/state-based-increment-only-counter-correct.png
 delete mode 100644 chapter/6/images/counters/state-based-increment-only-counter-incorrect.png
 create mode 100644 chapter/6/resources/code/counters/python/operation-based-increment-and-decrement-counter.py
 create mode 100644 chapter/6/resources/code/counters/python/operation-based-increment-only-counter.py
 create mode 100644 chapter/6/resources/code/counters/python/state-based-increment-and-decrement-counter-correct.py
 create mode 100644 chapter/6/resources/code/counters/python/state-based-increment-and-decrement-counter-incorrect.py
 create mode 100644 chapter/6/resources/code/counters/python/state-based-increment-only-counter-correct.py
 create mode 100644 chapter/6/resources/code/counters/python/state-based-increment-only-counter-incorrect.py
 create mode 100644 chapter/6/resources/images/counters/operation-based-increment-and-decrement-counter.png
 create mode 100644 chapter/6/resources/images/counters/operation-based-increment-only-counter.png
 create mode 100644 chapter/6/resources/images/counters/state-based-increment-and-decrement-counter-correct.png
 create mode 100644 chapter/6/resources/images/counters/state-based-increment-and-decrement-counter-incorrect.png
 create mode 100644 chapter/6/resources/images/counters/state-based-increment-only-counter-correct.png
 create mode 100644 chapter/6/resources/images/counters/state-based-increment-only-counter-incorrect.png
 create mode 100644 chapter/6/resources/images/partitioned-network.jpg
 delete mode 100644 chapter/6/resources/partitioned-network.jpg

(limited to 'chapter')

diff --git a/chapter/6/counters.md b/chapter/6/counters.md
index c441e6e..523e717 100644
--- a/chapter/6/counters.md
+++ b/chapter/6/counters.md
@@ -17,6 +17,25 @@ This is straightforward to implement as there is only one update operation.
 
 #### Specification
 
+```python
+
+class CmRDT:
+    pass
+
+class Counter(CmRDT):
+
+    def __init__(self):         # constructor function
+        self._count = 0
+
+    def value(self):            # query function
+        return self._count
+
+    def increment(self):        # update function
+        self._count += 1
+        for replica in self.replicas():
+            self.transmit("increment", replica)
+
+```
 
 #### Figure
 
@@ -31,6 +50,29 @@ Since the count always increases, modeling the state as count automatically make
 
 #### Specification
 
+```python
+
+class CvRDT:
+    pass
+
+class Counter(CvRDT):
+
+    def __init__(self, count = 0):  # constructor function
+        self._count = count
+
+    def value(self):                # query function
+        return self._count
+
+    def increment(self):            # update function
+        self._count += 1
+
+    def compare(self, other):       # comparison function
+        return self.value() <= other.value()
+
+    def merge(self, other):         # merge function
+        return Counter(max(self.value(), other.value()))
+
+```
 
 #### Figure
 
@@ -41,6 +83,38 @@ Something is clearly amiss! When two replicas are incremented, they should toget
 
 #### Specification
 
+```python
+
+class CvRDT:
+    pass
+
+class Counter(CvRDT):
+
+    def __init__(self, counts = None):  # constructor function
+        if counts is None:
+            self._counts = [0] * length(self.replicas())
+        else:
+            self._counts = counts
+
+    def value(self):                    # query function
+        return sum(self._counts)
+
+    def counts(self):                   # query function
+        return list(self._counts)       # return a clone
+
+    def increment(self):                # update function
+        self._counts[self.replicaId()] += 1
+
+    def compare(self, other):           # comparison function
+        return all(v1 <= v2 for (v1, v2) in
+                   zip(self.counts(),
+                       other.counts()))
+
+    def merge(self, other):             # merge function
+        return Counter(map(max, zip(self.counts(),
+                                    other.counts())))
+
+```
 
 #### Figure
 
@@ -59,6 +133,31 @@ Something is clearly amiss! When two replicas are incremented, they should toget
 
 #### Specification
 
+```python
+
+class CmRDT:
+    pass
+
+class Counter(CmRDT):
+
+    def __init__(self):         # constructor function
+        self._count = 0
+
+    def value(self):            # query function
+        return self._count
+
+    def increment(self):        # update function
+        self._count += 1
+        for replica in self.replicas():
+            self.transmit("increment", replica)
+
+    def decrement(self):        # update function
+        self._count -= 1
+        for replica in self.replicas():
+            self.transmit("decrement", replica)
+
+```
+
 #### Figure
 
 ![Operation based increment and decrement counter][operation-based-increment-and-decrement-counter]
@@ -67,7 +166,41 @@ Something is clearly amiss! When two replicas are incremented, they should toget
 
 #### Specification
 
+```python
+
+class CvRDT:
+    pass
+
+class Counter(CvRDT):
+
+    def __init__(self, counts = None):  # constructor function
+        if counts is None:
+            self._counts = [0] * length(self.replicas())
+        else:
+            self._counts = counts
+
+    def value(self):                    # query function
+        return sum(self._counts)
+
+    def counts(self):                   # query function
+        return list(self._counts)       # return a clone
 
+    def increment(self):                # update function
+        self._counts[self.replicaId()] += 1
+
+    def decrement(self):                # update function
+        self._counts[self.replicaId()] -= 1
+
+    def compare(self, other):           # comparison function
+        return all(v1 <= v2 for (v1, v2) in
+                   zip(self.counts(),
+                       other.counts()))
+
+    def merge(self, other):             # merge function
+        return Counter(map(max, zip(self.counts(),
+                                    other.counts())))
+
+```
 
 #### Figure
 
@@ -77,46 +210,66 @@ Something is clearly amiss! When two replicas are incremented, they should toget
 
 #### Specification
 
+```python
 
+class CvRDT:
+    pass
 
-#### Figure
+class Counter(CvRDT):
 
-![State based increment and decrement counter (correct)][state-based-increment-and-decrement-counter-correct]
+    def __init__(self,
+                 increments = None,
+                 decrements = None):   # constructor function
+        if increments is None:
+            self._increments = [0] * length(replicas())
+        else:
+            self._increments = increments
+        if decrements is None:
+            self._decrements = [0] * length(replicas())
+        else:
+            self._decrements = decrements
 
-## Non-negative Counter
+    def increments(self):               # query function
+        return list(self._increments)   # return a clone
 
+    def decrements(self):               # query function
+        return list(self._decrements)   # return a clone
 
+    def value(self):                    # query function
+        return (sum(self.increments()) -
+                sum(self.decrements()))
 
+    def increment(self):                # update function
+        self._increments[self.replicaId()] += 1
 
+    def decrement(self):                # update function
+        self._decrements[self.replicaId()] += 1
 
-### State based specification (CmRDT)
+    def compare(self, other):           # comparison function
+        return (all(v1 <= v2 for (v1, v2) in
+                    zip(self.increments(),
+                        other.increments()))
+                and
+                all(v1 <= v2 for (v1, v2) in
+                    zip(self.decrements(),
+                        other.decrements())))
+
+    def merge(self, other):             # merge function
+        return Counter(increments = map(max, zip(self.increments(),
+                                                 other.increments())),
+                       decrements = map(max, zip(self.decrements(),
+                                                 other.decrements())))
 
-```javascript
-class 
-    counts = [0, 0, ..., 0]
-    
-    update increment()
-        g <- getId()
-        counts[g] <- counts[g] + 1
-    
-    // query function
-    function value():
-        sum = 0
-        for count in counts:
-            sum <- sum + count
-        return sum
-    
-    function compare(other):
-        for i in 0 : length(replicas()):
-            if counts[i] > other.counts[i]:
-                return False
-        return True
-    
 ```
 
-[operation-based-increment-only-counter]: images/counters/operation-based-increment-only-counter.png
-[state-based-increment-only-counter-incorrect]: images/counters/state-based-increment-only-counter-incorrect.png
-[state-based-increment-only-counter-correct]: images/counters/state-based-increment-only-counter-correct.png
-[operation-based-increment-and-decrement-counter]: images/counters/operation-based-increment-and-decrement-counter.png
-[state-based-increment-and-decrement-counter-incorrect]: images/counters/state-based-increment-and-decrement-counter-incorrect.png
-[state-based-increment-and-decrement-counter-correct]: images/counters/state-based-increment-and-decrement-counter-correct.png
+#### Figure
+
+![State based increment and decrement counter (correct)][state-based-increment-and-decrement-counter-correct]
+
+
+[operation-based-increment-only-counter]: resources/images/counters/operation-based-increment-only-counter.png
+[state-based-increment-only-counter-incorrect]: resources/images/counters/state-based-increment-only-counter-incorrect.png
+[state-based-increment-only-counter-correct]: resources/images/counters/state-based-increment-only-counter-correct.png
+[operation-based-increment-and-decrement-counter]: resources/images/counters/operation-based-increment-and-decrement-counter.png
+[state-based-increment-and-decrement-counter-incorrect]: resources/images/counters/state-based-increment-and-decrement-counter-incorrect.png
+[state-based-increment-and-decrement-counter-correct]: resources/images/counters/state-based-increment-and-decrement-counter-correct.png
diff --git a/chapter/6/images/counters/operation-based-increment-and-decrement-counter.png b/chapter/6/images/counters/operation-based-increment-and-decrement-counter.png
deleted file mode 100644
index f046c0b..0000000
Binary files a/chapter/6/images/counters/operation-based-increment-and-decrement-counter.png and /dev/null differ
diff --git a/chapter/6/images/counters/operation-based-increment-only-counter.png b/chapter/6/images/counters/operation-based-increment-only-counter.png
deleted file mode 100644
index 398c562..0000000
Binary files a/chapter/6/images/counters/operation-based-increment-only-counter.png and /dev/null differ
diff --git a/chapter/6/images/counters/state-based-increment-and-decrement-counter-correct.png b/chapter/6/images/counters/state-based-increment-and-decrement-counter-correct.png
deleted file mode 100644
index 0d6468b..0000000
Binary files a/chapter/6/images/counters/state-based-increment-and-decrement-counter-correct.png and /dev/null differ
diff --git a/chapter/6/images/counters/state-based-increment-and-decrement-counter-incorrect.png b/chapter/6/images/counters/state-based-increment-and-decrement-counter-incorrect.png
deleted file mode 100644
index 3f7f1b9..0000000
Binary files a/chapter/6/images/counters/state-based-increment-and-decrement-counter-incorrect.png and /dev/null differ
diff --git a/chapter/6/images/counters/state-based-increment-only-counter-correct.png b/chapter/6/images/counters/state-based-increment-only-counter-correct.png
deleted file mode 100644
index 4ca2843..0000000
Binary files a/chapter/6/images/counters/state-based-increment-only-counter-correct.png and /dev/null differ
diff --git a/chapter/6/images/counters/state-based-increment-only-counter-incorrect.png b/chapter/6/images/counters/state-based-increment-only-counter-incorrect.png
deleted file mode 100644
index 3f95e59..0000000
Binary files a/chapter/6/images/counters/state-based-increment-only-counter-incorrect.png and /dev/null differ
diff --git a/chapter/6/resources/code/counters/python/operation-based-increment-and-decrement-counter.py b/chapter/6/resources/code/counters/python/operation-based-increment-and-decrement-counter.py
new file mode 100644
index 0000000..5182ab1
--- /dev/null
+++ b/chapter/6/resources/code/counters/python/operation-based-increment-and-decrement-counter.py
@@ -0,0 +1,20 @@
+class CmRDT:
+    pass
+
+class Counter(CmRDT):
+
+    def __init__(self):         # constructor function
+        self._count = 0
+
+    def value(self):            # query function
+        return self._count
+
+    def increment(self):        # update function
+        self._count += 1
+        for replica in self.replicas():
+            self.transmit("increment", replica)
+
+    def decrement(self):        # update function
+        self._count -= 1
+        for replica in self.replicas():
+            self.transmit("decrement", replica)
diff --git a/chapter/6/resources/code/counters/python/operation-based-increment-only-counter.py b/chapter/6/resources/code/counters/python/operation-based-increment-only-counter.py
new file mode 100644
index 0000000..b10cd98
--- /dev/null
+++ b/chapter/6/resources/code/counters/python/operation-based-increment-only-counter.py
@@ -0,0 +1,15 @@
+class CmRDT:
+    pass
+
+class Counter(CmRDT):
+
+    def __init__(self):         # constructor function
+        self._count = 0
+
+    def value(self):            # query function
+        return self._count
+
+    def increment(self):        # update function
+        self._count += 1
+        for replica in self.replicas():
+            self.transmit("increment", replica)
diff --git a/chapter/6/resources/code/counters/python/state-based-increment-and-decrement-counter-correct.py b/chapter/6/resources/code/counters/python/state-based-increment-and-decrement-counter-correct.py
new file mode 100644
index 0000000..1ea726d
--- /dev/null
+++ b/chapter/6/resources/code/counters/python/state-based-increment-and-decrement-counter-correct.py
@@ -0,0 +1,47 @@
+class CvRDT:
+    pass
+
+class Counter(CvRDT):
+
+    def __init__(self,
+                 increments = None,
+                 decrements = None):   # constructor function
+        if increments is None:
+            self._increments = [0] * length(replicas())
+        else:
+            self._increments = increments
+        if decrements is None:
+            self._decrements = [0] * length(replicas())
+        else:
+            self._decrements = decrements
+
+    def increments(self):               # query function
+        return list(self._increments)   # return a clone
+
+    def decrements(self):               # query function
+        return list(self._decrements)   # return a clone
+
+    def value(self):                    # query function
+        return (sum(self.increments()) -
+                sum(self.decrements()))
+
+    def increment(self):                # update function
+        self._increments[self.replicaId()] += 1
+
+    def decrement(self):                # update function
+        self._decrements[self.replicaId()] += 1
+
+    def compare(self, other):           # comparison function
+        return (all(v1 <= v2 for (v1, v2) in
+                    zip(self.increments(),
+                        other.increments()))
+                and
+                all(v1 <= v2 for (v1, v2) in
+                    zip(self.decrements(),
+                        other.decrements())))
+
+    def merge(self, other):             # merge function
+        return Counter(increments = map(max, zip(self.increments(),
+                                                 other.increments())),
+                       decrements = map(max, zip(self.decrements(),
+                                                 other.decrements())))
diff --git a/chapter/6/resources/code/counters/python/state-based-increment-and-decrement-counter-incorrect.py b/chapter/6/resources/code/counters/python/state-based-increment-and-decrement-counter-incorrect.py
new file mode 100644
index 0000000..6f0cbde
--- /dev/null
+++ b/chapter/6/resources/code/counters/python/state-based-increment-and-decrement-counter-incorrect.py
@@ -0,0 +1,31 @@
+class CvRDT:
+    pass
+
+class Counter(CvRDT):
+
+    def __init__(self, counts = None):  # constructor function
+        if counts is None:
+            self._counts = [0] * length(self.replicas())
+        else:
+            self._counts = counts
+
+    def value(self):                    # query function
+        return sum(self._counts)
+
+    def counts(self):                   # query function
+        return list(self._counts)       # return a clone
+
+    def increment(self):                # update function
+        self._counts[self.replicaId()] += 1
+
+    def decrement(self):                # update function
+        self._counts[self.replicaId()] -= 1
+
+    def compare(self, other):           # comparison function
+        return all(v1 <= v2 for (v1, v2) in
+                   zip(self.counts(),
+                       other.counts()))
+
+    def merge(self, other):             # merge function
+        return Counter(map(max, zip(self.counts(),
+                                    other.counts())))
diff --git a/chapter/6/resources/code/counters/python/state-based-increment-only-counter-correct.py b/chapter/6/resources/code/counters/python/state-based-increment-only-counter-correct.py
new file mode 100644
index 0000000..a3d9069
--- /dev/null
+++ b/chapter/6/resources/code/counters/python/state-based-increment-only-counter-correct.py
@@ -0,0 +1,28 @@
+class CvRDT:
+    pass
+
+class Counter(CvRDT):
+
+    def __init__(self, counts = None):  # constructor function
+        if counts is None:
+            self._counts = [0] * length(self.replicas())
+        else:
+            self._counts = counts
+
+    def value(self):                    # query function
+        return sum(self._counts)
+
+    def counts(self):                   # query function
+        return list(self._counts)       # return a clone
+
+    def increment(self):                # update function
+        self._counts[self.replicaId()] += 1
+
+    def compare(self, other):           # comparison function
+        return all(v1 <= v2 for (v1, v2) in
+                   zip(self.counts(),
+                       other.counts()))
+
+    def merge(self, other):             # merge function
+        return Counter(map(max, zip(self.counts(),
+                                    other.counts())))
diff --git a/chapter/6/resources/code/counters/python/state-based-increment-only-counter-incorrect.py b/chapter/6/resources/code/counters/python/state-based-increment-only-counter-incorrect.py
new file mode 100644
index 0000000..9971c65
--- /dev/null
+++ b/chapter/6/resources/code/counters/python/state-based-increment-only-counter-incorrect.py
@@ -0,0 +1,19 @@
+class CvRDT:
+    pass
+
+class Counter(CvRDT):
+
+    def __init__(self, count = 0):  # constructor function
+        self._count = count
+
+    def value(self):                # query function
+        return self._count
+
+    def increment(self):            # update function
+        self._count += 1
+
+    def compare(self, other):       # comparison function
+        return self.value() <= other.value()
+
+    def merge(self, other):         # merge function
+        return Counter(max(self.value(), other.value()))
diff --git a/chapter/6/resources/images/counters/operation-based-increment-and-decrement-counter.png b/chapter/6/resources/images/counters/operation-based-increment-and-decrement-counter.png
new file mode 100644
index 0000000..f046c0b
Binary files /dev/null and b/chapter/6/resources/images/counters/operation-based-increment-and-decrement-counter.png differ
diff --git a/chapter/6/resources/images/counters/operation-based-increment-only-counter.png b/chapter/6/resources/images/counters/operation-based-increment-only-counter.png
new file mode 100644
index 0000000..398c562
Binary files /dev/null and b/chapter/6/resources/images/counters/operation-based-increment-only-counter.png differ
diff --git a/chapter/6/resources/images/counters/state-based-increment-and-decrement-counter-correct.png b/chapter/6/resources/images/counters/state-based-increment-and-decrement-counter-correct.png
new file mode 100644
index 0000000..0d6468b
Binary files /dev/null and b/chapter/6/resources/images/counters/state-based-increment-and-decrement-counter-correct.png differ
diff --git a/chapter/6/resources/images/counters/state-based-increment-and-decrement-counter-incorrect.png b/chapter/6/resources/images/counters/state-based-increment-and-decrement-counter-incorrect.png
new file mode 100644
index 0000000..3f7f1b9
Binary files /dev/null and b/chapter/6/resources/images/counters/state-based-increment-and-decrement-counter-incorrect.png differ
diff --git a/chapter/6/resources/images/counters/state-based-increment-only-counter-correct.png b/chapter/6/resources/images/counters/state-based-increment-only-counter-correct.png
new file mode 100644
index 0000000..4ca2843
Binary files /dev/null and b/chapter/6/resources/images/counters/state-based-increment-only-counter-correct.png differ
diff --git a/chapter/6/resources/images/counters/state-based-increment-only-counter-incorrect.png b/chapter/6/resources/images/counters/state-based-increment-only-counter-incorrect.png
new file mode 100644
index 0000000..3f95e59
Binary files /dev/null and b/chapter/6/resources/images/counters/state-based-increment-only-counter-incorrect.png differ
diff --git a/chapter/6/resources/images/partitioned-network.jpg b/chapter/6/resources/images/partitioned-network.jpg
new file mode 100644
index 0000000..513fc13
Binary files /dev/null and b/chapter/6/resources/images/partitioned-network.jpg differ
diff --git a/chapter/6/resources/partitioned-network.jpg b/chapter/6/resources/partitioned-network.jpg
deleted file mode 100644
index 513fc13..0000000
Binary files a/chapter/6/resources/partitioned-network.jpg and /dev/null differ
-- 
cgit v1.2.3


From 71d608e799f4f5674c8961e304719743d26066fc Mon Sep 17 00:00:00 2001
From: Aviral Goel <goel.aviral@gmail.com>
Date: Sun, 18 Dec 2016 01:35:23 -0500
Subject: Wrote up description for PN Counter

---
 chapter/6/counters.md                              | 230 +++++++++++++--------
 .../images/counters/decrement-operation.png        | Bin 0 -> 1775 bytes
 .../images/counters/increment-operation.png        | Bin 0 -> 1649 bytes
 3 files changed, 140 insertions(+), 90 deletions(-)
 create mode 100644 chapter/6/resources/images/counters/decrement-operation.png
 create mode 100644 chapter/6/resources/images/counters/increment-operation.png

(limited to 'chapter')

diff --git a/chapter/6/counters.md b/chapter/6/counters.md
index 523e717..faa7eb0 100644
--- a/chapter/6/counters.md
+++ b/chapter/6/counters.md
@@ -41,6 +41,15 @@ class Counter(CmRDT):
 
 ![Operation based increment only counter][operation-based-increment-only-counter]
 
+The figure above shows three replicas (<b>c<sub>1</sub></b>, <b>c<sub>2</sub></b> and <b>c<sub>3</sub></b>) of an operation based increment only counter <b>C<sub>operation</sub></b>. The clients issue increment requests depicted as <increment-request>. In accordance with the specification, each increment request increments the counter by 1 unit and the operation is transmitted by the replica to all other replicas of the system. 
+There are a few interesting observations:
+
+* **Eventually consistent** - At *t<sub>16</sub>*, the replicas are inconsistent. Eventually, they all attain consistency. This is because the increment operation happens immediately at one replica but takes time to be transmitted over the network to other replicas. Within this duration, the replicas may be inconsistent.
+
+* **Reliable broadcast** - The increment operation has to be transmitted to all replicas. If the network fails to deliver the operation, the system will never be able to achieve consistency.
+
+* **Concurrent operations** - A replica may have to handle concurrent operations. For example, at *t<sub>19</sub>*, <b>c<sub>1</sub></b> encounters two increment operations. Since the increment operation commutes with itself, the order does not matter. The replica can decide to handle the increments in arbitrary order.
+
 
 ### CvRDT: State based specification
 
@@ -77,6 +86,19 @@ class Counter(CvRDT):
 #### Figure
 
 ![State based increment only counter (incorrect)][state-based-increment-only-counter-incorrect]
+The figure above shows three replicas (<b>c<sub>1</sub></b>, <b>c<sub>2</sub></b> and <b>c<sub>3</sub></b>) of a state based increment only counter <b>C<sub>state</sub></b>. The clients issue increment requests depicted as <increment-request>. In accordance with the specification, each increment request increments the counter by 1 unit.  and the operation is transmitted by the replica to all other replicas of the system. 
+There are a few interesting observations:
+
+* **Eventual convergence** - At *t<sub>26</sub>*, the replicas are inconsistent. Eventually, they all converge. This is because the increment operation happens immediately at one replica but takes time to be transmitted over the network to other replicas. Within this duration, the replicas may be inconsistent.
+
+> Eventual convergence does not guarantee correctness.
+
+> Incorrect design may still converge eventually.
+
+* **Unreliable broadcast** - Messages may be lost increment operation has to be transmitted to all replicas. If the network fails to deliver the operation, the system will never be able to achieve consistency.
+
+* **Concurrent operations** - A replica may have to handle concurrent operations. For example, at *t<sub>19</sub>*, <b>c<sub>1</sub></b> encounters two increment operations. Since the increment operation commutes with itself, the order does not matter. The replica can decide to handle the increments in arbitrary order.
+
 As it can be seen from the figure, the clients issue a total of 4 increment requests. However, the replicas finally converge to 2.
 Something is clearly amiss! When two replicas are incremented, they should together converge to 2. But the `merge` function computes the maximum of two states. 
 
@@ -123,150 +145,178 @@ class Counter(CvRDT):
 As it can be seen from the figure, the clients issue a total of 4 increment requests. However, the replicas finally converge to 2.
 Something is clearly amiss! When two replicas are incremented, they should together converge to 2. But the `merge` function computes the maximum of two states. 
 
-
-
-
-
 ## PN-counter - Increment and Decrement counter
 
+A PN-counter can be incremented and decremented.
+
 ### CmRDT: Operation based specification
 
-#### Specification
+The code below provides the specification of an operation based increment and decrement counter.
 
-```python
+<pre style="background:#fff;color:#000">
 
-class CmRDT:
-    pass
+<span style="color:#ff5600">class</span> <span style="color:#21439c">Counter</span>(CmRDT):
 
-class Counter(CmRDT):
+    <span style="color:#ff5600">def</span> <span style="color:#21439c"><span style="color:#a535ae">__init__</span></span>(self):         <span style="color:#919191"># constructor function</span>
+        self._count <span style="color:#ff5600">=</span> 0
 
-    def __init__(self):         # constructor function
-        self._count = 0
+    <span style="color:#ff5600">def</span> <span style="color:#21439c">value</span>(self):            <span style="color:#919191"># query function</span>
+        <span style="color:#ff5600">return</span> self._count
 
-    def value(self):            # query function
-        return self._count
+    <span style="color:#ff5600">def</span> <span style="color:#21439c">increment</span>(self):        <span style="color:#919191"># update function</span>
+        self._count <span style="color:#ff5600">+=</span> 1
+        <span style="color:#ff5600">for</span> replica <span style="color:#ff5600">in</span> self.replicas():
+            self.transmit(<span style="color:#00a33f">"increment"</span>, replica)
 
-    def increment(self):        # update function
-        self._count += 1
-        for replica in self.replicas():
-            self.transmit("increment", replica)
+    <span style="color:#ff5600">def</span> <span style="color:#21439c">decrement</span>(self):        <span style="color:#919191"># update function</span>
+        self._count <span style="color:#ff5600">-=</span> 1
+        <span style="color:#ff5600">for</span> replica <span style="color:#ff5600">in</span> self.replicas():
+            self.transmit(<span style="color:#00a33f">"decrement"</span>, replica)
+</pre>
 
-    def decrement(self):        # update function
-        self._count -= 1
-        for replica in self.replicas():
-            self.transmit("decrement", replica)
+Let's try to understand how it works through an example. The figure below shows three replicas (<b>c<sub>1</sub></b>, <b>c<sub>2</sub></b> and <b>c<sub>3</sub></b>) of an operation based increment and decrement counter <b>C<sub>operation</sub></b>. 
 
-```
+* ![increment operation][increment-operation] depicts increment request issued by the client.
+* ![decrement operation][decrement-operation] depicts decrement request issued by the client.
 
-#### Figure
+In accordance with the specification, each increment request increments the counter locally by one unit and each decrement request decrements the counter locally by one unit. The corresponding operation is transmitted by the replica to all other replicas of the system. 
 
-![Operation based increment and decrement counter][operation-based-increment-and-decrement-counter]
+<figure class="fullwidth">
+    <img src="{{ site.baseurl }}/chapter/6/resources/images/counters/operation-based-increment-and-decrement-counter.png" alt="Operation based increment and decrement counter"/>
+</figure>
 
-### CvRDT: State based specification
+One can make the the following observations:
 
-#### Specification
+* **Eventually consistent** - At *t<sub>26</sub>*, the replicas are inconsistent. Eventually, they all achieve consistency. This is because the operations happen immediately at one replica but take time to be transmitted over the network to other replicas. Within this duration, the replicas may be inconsistent.
+* **Reliable broadcast** - The operations have to be transmitted to all replicas. If the network fails to deliver an operation, the system will never be able to achieve consistency.
+* **Concurrent operations** - A replica may have to handle concurrent operations. For example, at *t<sub>30</sub>*, <b>c<sub>1</sub></b> and <b>c<sub>2</sub></b> encounter increment and decrement operations concurrently. Since the increment and decrement  operations commute, the order in which they are executed by the replicas does not matter. Both replicas perform them in different orders and still achieve consistency, eventually.
 
-```python
+### CvRDT: State based specification
 
-class CvRDT:
-    pass
+The code below provides the specification of a state based increment and decrement counter.
 
-class Counter(CvRDT):
+<pre style="background:#fff;color:#000"><span style="color:#ff5600">class</span> <span style="color:#21439c">Counter</span>(CvRDT):
 
-    def __init__(self, counts = None):  # constructor function
-        if counts is None:
-            self._counts = [0] * length(self.replicas())
-        else:
-            self._counts = counts
+    <span style="color:#ff5600">def</span> <span style="color:#21439c"><span style="color:#a535ae">__init__</span></span>(self, counts <span style="color:#ff5600">=</span> <span style="color:#a535ae">None</span>):  <span style="color:#919191"># constructor function</span>
+        <span style="color:#ff5600">if</span> counts <span style="color:#ff5600">is</span> <span style="color:#a535ae">None</span>:
+            self._counts <span style="color:#ff5600">=</span> [0] <span style="color:#ff5600">*</span> length(self.replicas())
+        <span style="color:#ff5600">else</span>:
+            self._counts <span style="color:#ff5600">=</span> counts
 
-    def value(self):                    # query function
-        return sum(self._counts)
+    <span style="color:#ff5600">def</span> <span style="color:#21439c">value</span>(self):                    <span style="color:#919191"># query function</span>
+        <span style="color:#ff5600">return</span> <span style="color:#a535ae">sum</span>(self._counts)
 
-    def counts(self):                   # query function
-        return list(self._counts)       # return a clone
+    <span style="color:#ff5600">def</span> <span style="color:#21439c">counts</span>(self):                   <span style="color:#919191"># query function</span>
+        <span style="color:#ff5600">return</span> <span style="color:#a535ae">list</span>(self._counts)       <span style="color:#919191"># return a clone</span>
 
-    def increment(self):                # update function
-        self._counts[self.replicaId()] += 1
+    <span style="color:#ff5600">def</span> <span style="color:#21439c">increment</span>(self):                <span style="color:#919191"># update function</span>
+        self._counts[self.replicaId()] <span style="color:#ff5600">+=</span> 1
 
-    def decrement(self):                # update function
-        self._counts[self.replicaId()] -= 1
+    <span style="color:#ff5600">def</span> <span style="color:#21439c">decrement</span>(self):                <span style="color:#919191"># update function</span>
+        self._counts[self.replicaId()] <span style="color:#ff5600">-=</span> 1
 
-    def compare(self, other):           # comparison function
-        return all(v1 <= v2 for (v1, v2) in
-                   zip(self.counts(),
+    <span style="color:#ff5600">def</span> <span style="color:#21439c">compare</span>(self, other):           <span style="color:#919191"># comparison function</span>
+        <span style="color:#ff5600">return</span> <span style="color:#a535ae">all</span>(v1 <span style="color:#ff5600">&lt;=</span> v2 <span style="color:#ff5600">for</span> (v1, v2) <span style="color:#ff5600">in</span>
+                   <span style="color:#a535ae">zip</span>(self.counts(),
                        other.counts()))
 
-    def merge(self, other):             # merge function
-        return Counter(map(max, zip(self.counts(),
+    <span style="color:#ff5600">def</span> <span style="color:#21439c">merge</span>(self, other):             <span style="color:#919191"># merge function</span>
+        <span style="color:#ff5600">return</span> Counter(<span style="color:#a535ae">map</span>(<span style="color:#a535ae">max</span>, <span style="color:#a535ae">zip</span>(self.counts(),
                                     other.counts())))
 
-```
+</pre>
 
-#### Figure
+Let's try to understand how it works through an example. The figure below shows three replicas (<b>c<sub>1</sub></b>, <b>c<sub>2</sub></b> and <b>c<sub>3</sub></b>) of a state based increment and decrement counter <b>C<sub>state</sub></b>. 
 
-![State based increment and decrement counter (incorrect)][state-based-increment-and-decrement-counter-incorrect]
+* ![increment operation][increment-operation] depicts increment request issued by the client.
+* ![decrement operation][decrement-operation] depicts decrement request issued by the client.
 
+In accordance with the specification, each increment request increments the counter by one unit and each decrement request decrements the counte by one unit. The replica transmits its state at random times to a random replica.
 
+<figure class="fullwidth">
+    <img src="{{ site.baseurl }}/chapter/6/resources/images/counters/state-based-increment-and-decrement-counter-incorrect.png" alt="State based increment and decrement counter (incorrect)"/>
+</figure>
 
-#### Specification
+We can make the the following observations:
 
-```python
+* **Eventual convergence** - At *t<sub>26</sub>*, the replicas are inconsistent. Eventually, they all converge. This is because the increment operation happens immediately at one replica but takes time to be transmitted over the network to other replicas. Within this duration, the replicas may be inconsistent.
+* **Correctness** - The clients issue a total of four increment requests and 2 decrement requests. But the eventually consistent value of replicas is 4. So, the design is **incorrect**.
+* **Concurrent operations** - A replica may have to handle concurrent operations. For example, at *t<sub>27</sub>* <b>c<sub>1</sub></b> has to handle 2 merge operations concurrently. Since the state forms a partially ordered set and the merge operation computes its least upper bound, the order in which the merge operation happens does not affect the final outcome. Similarly, at *t<sub>21</sub>* and *t<sub>29</sub>*, two operations arrive concurrently at <b>c<sub>3</sub></b> and <b>c<sub>2</sub></b> respectively.
+* **Unreliable broadcast** - Messages may be lost during transmission. Message sent by <b>c<sub>3</sub></b> at *t<sub>12</sub>* is lost. But eventually, message at *t<sub>25</sub>* reaches another replica. As long as messages eventually reach other replicas, directly or indirectly, the system will achieve consistency. A message can also be received out of order or duplicated. 
 
-class CvRDT:
-    pass
+Let's try to figure out why the design is incorrect. At *t<sub>12</sub>*, <b>c<sub>1</sub></b> merges the state from <b>c<sub>2</sub></b>. The merge operation computes the index wise maximum in accordance with the specification. In doing so, the *-1* value of *c<sub>2</sub>* due to the decrement operation at *t<sub>6</sub>* is lost. Its clear that we have violated the basic constraint, the decrement operation does not take the state higher up in the lattice. In other words, the decrement operation is non monotonic. This causes us to lose the decrements and we are eventually left with replicas which only count the total number of increment requests.
+But we do gain two valuable insights from this design-
 
-class Counter(CvRDT):
+> Eventual convergence does not guarantee correctness.
 
-    def __init__(self,
-                 increments = None,
-                 decrements = None):   # constructor function
-        if increments is None:
-            self._increments = [0] * length(replicas())
-        else:
-            self._increments = increments
-        if decrements is None:
-            self._decrements = [0] * length(replicas())
-        else:
-            self._decrements = decrements
+> Incorrect designs may still converge eventually.
 
-    def increments(self):               # query function
-        return list(self._increments)   # return a clone
 
-    def decrements(self):               # query function
-        return list(self._decrements)   # return a clone
+Let's try to correct this problem. The problem happens because the decrement operation is non-monotonic. So we need a way to count the decrement operations without losing monotonicity. One solution is to model this counter using two increment only counters. The first counter counts the increment operations and the second one counts the decrement operations. The value of the actual counter is the difference between the two corresponding counters. The specification below shows how this can be implemented.
 
-    def value(self):                    # query function
-        return (sum(self.increments()) -
-                sum(self.decrements()))
+<pre style="background:#fff;color:#000"><span style="color:#ff5600">class</span> <span style="color:#21439c">Counter</span>(CvRDT):
 
-    def increment(self):                # update function
-        self._increments[self.replicaId()] += 1
+    <span style="color:#ff5600">def</span> <span style="color:#21439c"><span style="color:#a535ae">__init__</span></span>(self,
+                 increments <span style="color:#ff5600">=</span> <span style="color:#a535ae">None</span>,
+                 decrements <span style="color:#ff5600">=</span> <span style="color:#a535ae">None</span>):   <span style="color:#919191"># constructor function</span>
+        <span style="color:#ff5600">if</span> increments <span style="color:#ff5600">is</span> <span style="color:#a535ae">None</span>:
+            self._increments <span style="color:#ff5600">=</span> [0] <span style="color:#ff5600">*</span> length(replicas())
+        <span style="color:#ff5600">else</span>:
+            self._increments <span style="color:#ff5600">=</span> increments
+        <span style="color:#ff5600">if</span> decrements <span style="color:#ff5600">is</span> <span style="color:#a535ae">None</span>:
+            self._decrements <span style="color:#ff5600">=</span> [0] <span style="color:#ff5600">*</span> length(replicas())
+        <span style="color:#ff5600">else</span>:
+            self._decrements <span style="color:#ff5600">=</span> decrements
 
-    def decrement(self):                # update function
-        self._decrements[self.replicaId()] += 1
+    <span style="color:#ff5600">def</span> <span style="color:#21439c">increments</span>(self):               <span style="color:#919191"># query function</span>
+        <span style="color:#ff5600">return</span> <span style="color:#a535ae">list</span>(self._increments)   <span style="color:#919191"># return a clone</span>
 
-    def compare(self, other):           # comparison function
-        return (all(v1 <= v2 for (v1, v2) in
-                    zip(self.increments(),
+    <span style="color:#ff5600">def</span> <span style="color:#21439c">decrements</span>(self):               <span style="color:#919191"># query function</span>
+        <span style="color:#ff5600">return</span> <span style="color:#a535ae">list</span>(self._decrements)   <span style="color:#919191"># return a clone</span>
+
+    <span style="color:#ff5600">def</span> <span style="color:#21439c">value</span>(self):                    <span style="color:#919191"># query function</span>
+        <span style="color:#ff5600">return</span> (<span style="color:#a535ae">sum</span>(self.increments()) <span style="color:#ff5600">-</span>
+                <span style="color:#a535ae">sum</span>(self.decrements()))
+
+    <span style="color:#ff5600">def</span> <span style="color:#21439c">increment</span>(self):                <span style="color:#919191"># update function</span>
+        self._increments[self.replicaId()] <span style="color:#ff5600">+=</span> 1
+
+    <span style="color:#ff5600">def</span> <span style="color:#21439c">decrement</span>(self):                <span style="color:#919191"># update function</span>
+        self._decrements[self.replicaId()] <span style="color:#ff5600">+=</span> 1
+
+    <span style="color:#ff5600">def</span> <span style="color:#21439c">compare</span>(self, other):           <span style="color:#919191"># comparison function</span>
+        <span style="color:#ff5600">return</span> (<span style="color:#a535ae">all</span>(v1 <span style="color:#ff5600">&lt;=</span> v2 <span style="color:#ff5600">for</span> (v1, v2) <span style="color:#ff5600">in</span>
+                    <span style="color:#a535ae">zip</span>(self.increments(),
                         other.increments()))
-                and
-                all(v1 <= v2 for (v1, v2) in
-                    zip(self.decrements(),
+                <span style="color:#ff5600">and</span>
+                <span style="color:#a535ae">all</span>(v1 <span style="color:#ff5600">&lt;=</span> v2 <span style="color:#ff5600">for</span> (v1, v2) <span style="color:#ff5600">in</span>
+                    <span style="color:#a535ae">zip</span>(self.decrements(),
                         other.decrements())))
 
-    def merge(self, other):             # merge function
-        return Counter(increments = map(max, zip(self.increments(),
+    <span style="color:#ff5600">def</span> <span style="color:#21439c">merge</span>(self, other):             <span style="color:#919191"># merge function</span>
+        <span style="color:#ff5600">return</span> Counter(increments <span style="color:#ff5600">=</span> <span style="color:#a535ae">map</span>(<span style="color:#a535ae">max</span>, <span style="color:#a535ae">zip</span>(self.increments(),
                                                  other.increments())),
-                       decrements = map(max, zip(self.decrements(),
+                       decrements <span style="color:#ff5600">=</span> <span style="color:#a535ae">map</span>(<span style="color:#a535ae">max</span>, <span style="color:#a535ae">zip</span>(self.decrements(),
                                                  other.decrements())))
 
-```
+</pre>
 
-#### Figure
+The figure below shows an execution trace of three replicas (<b>c<sub>1</sub></b>, <b>c<sub>2</sub></b> and <b>c<sub>3</sub></b>) of this counter.
+
+* ![increment operation][increment-operation] depicts increment request issued by the client.
+* ![decrement operation][decrement-operation] depicts decrement request issued by the client.
+
+The values in the top row in the replica state depict the increments and the bottom ones depict the decrements. In accordance with the specification, each increment request increments the value in the top row by one unit and each decrement request increments the value in the lower row by one unit. Once the operation materializes locally, the new state is transmitted by the replica to some other randomly chosen replica.
+
+<figure class="fullwidth">
+    <img src="{{ site.baseurl }}/chapter/6/resources/images/counters/state-based-increment-and-decrement-counter-correct.png" alt="State based increment and decrement counter (correct)"/>
+</figure>
 
-![State based increment and decrement counter (correct)][state-based-increment-and-decrement-counter-correct]
+This design converges to the correct value.
 
 
+[increment-operation]: resources/images/counters/increment-operation.png
+[decrement-operation]: resources/images/counters/decrement-operation.png
 [operation-based-increment-only-counter]: resources/images/counters/operation-based-increment-only-counter.png
 [state-based-increment-only-counter-incorrect]: resources/images/counters/state-based-increment-only-counter-incorrect.png
 [state-based-increment-only-counter-correct]: resources/images/counters/state-based-increment-only-counter-correct.png
diff --git a/chapter/6/resources/images/counters/decrement-operation.png b/chapter/6/resources/images/counters/decrement-operation.png
new file mode 100644
index 0000000..a2d3f1a
Binary files /dev/null and b/chapter/6/resources/images/counters/decrement-operation.png differ
diff --git a/chapter/6/resources/images/counters/increment-operation.png b/chapter/6/resources/images/counters/increment-operation.png
new file mode 100644
index 0000000..f016c23
Binary files /dev/null and b/chapter/6/resources/images/counters/increment-operation.png differ
-- 
cgit v1.2.3


From 4265d72a46759e930436bf0c6349982ecf0adabd Mon Sep 17 00:00:00 2001
From: Aviral Goel <goel.aviral@gmail.com>
Date: Mon, 19 Dec 2016 02:23:12 -0500
Subject: Complete draft of the counters writeup

---
 chapter/6/counters.md                              | 225 ++++++++++-----------
 .../increment-and-decrement-operations-commute.png | Bin 0 -> 22837 bytes
 ...ation-based-increment-and-decrement-counter.png | Bin 259325 -> 231349 bytes
 .../operation-based-increment-only-counter.png     | Bin 236423 -> 275467 bytes
 ...sed-increment-and-decrement-counter-correct.png | Bin 250168 -> 302107 bytes
 ...ent-and-decrement-counter-incorrect-lattice.png | Bin 0 -> 42949 bytes
 ...d-increment-and-decrement-counter-incorrect.png | Bin 247402 -> 298653 bytes
 .../state-based-increment-only-counter-correct.png | Bin 240649 -> 282239 bytes
 ...tate-based-increment-only-counter-incorrect.png | Bin 241905 -> 283474 bytes
 9 files changed, 108 insertions(+), 117 deletions(-)
 create mode 100644 chapter/6/resources/images/counters/increment-and-decrement-operations-commute.png
 create mode 100644 chapter/6/resources/images/counters/state-based-increment-and-decrement-counter-incorrect-lattice.png

(limited to 'chapter')

diff --git a/chapter/6/counters.md b/chapter/6/counters.md
index faa7eb0..a2709af 100644
--- a/chapter/6/counters.md
+++ b/chapter/6/counters.md
@@ -6,150 +6,133 @@ by: "Aviral Goel"
 
 Counters are replicated integers. They are the most basic distributed object. This chapter describes the different variations of counter CRDT in both state based and operation based form.
 
-## G-counter - Increment only counter
+## 1. G-counter - Increment only counter
 
 As the name suggests, these counters only support increment operation. They can be used to implement the `like` button functionality of social media websites.
 
-### CmRDT: Operation based G-counter
+### 1.1. CmRDT: Operation based design
 
 In the operation based implementation, the increment operation is transmitted to all other replicas. 
 This is straightforward to implement as there is only one update operation. 
 
-#### Specification
+<pre style="background:#fff;color:#000"><span style="color:#ff5600">class</span> <span style="color:#21439c">Counter</span>(CmRDT):
 
-```python
-
-class CmRDT:
-    pass
-
-class Counter(CmRDT):
-
-    def __init__(self):         # constructor function
-        self._count = 0
+    <span style="color:#ff5600">def</span> <span style="color:#21439c"><span style="color:#a535ae">__init__</span></span>(self):         <span style="color:#919191"># constructor function</span>
+        self._count <span style="color:#ff5600">=</span> 0
 
-    def value(self):            # query function
-        return self._count
+    <span style="color:#ff5600">def</span> <span style="color:#21439c">value</span>(self):            <span style="color:#919191"># query function</span>
+        <span style="color:#ff5600">return</span> self._count
 
-    def increment(self):        # update function
-        self._count += 1
-        for replica in self.replicas():
-            self.transmit("increment", replica)
+    <span style="color:#ff5600">def</span> <span style="color:#21439c">increment</span>(self):        <span style="color:#919191"># update function</span>
+        self._count <span style="color:#ff5600">+=</span> 1
+        <span style="color:#ff5600">for</span> replica <span style="color:#ff5600">in</span> self.replicas():
+            self.transmit(<span style="color:#00a33f">"increment"</span>, replica)
 
-```
+</pre>
 
-#### Figure
+Let's try to understand how it works through an example. The figure below shows an execution trace of three replicas confirming to this specification. In accordance with the specification, each increment request increments the counter locally by one unit and the operation is transmitted by the replica to all other replicas of the system.
 
-![Operation based increment only counter][operation-based-increment-only-counter]
+<figure class="fullwidth">
+    <img style="margin: auto; display: block;" src="{{ site.baseurl }}/chapter/6/resources/images/counters/operation-based-increment-only-counter.png" alt="Operation based increment only counter"/>
+</figure>
 
-The figure above shows three replicas (<b>c<sub>1</sub></b>, <b>c<sub>2</sub></b> and <b>c<sub>3</sub></b>) of an operation based increment only counter <b>C<sub>operation</sub></b>. The clients issue increment requests depicted as <increment-request>. In accordance with the specification, each increment request increments the counter by 1 unit and the operation is transmitted by the replica to all other replicas of the system. 
-There are a few interesting observations:
+We can make the following observations:
 
 * **Eventually consistent** - At *t<sub>16</sub>*, the replicas are inconsistent. Eventually, they all attain consistency. This is because the increment operation happens immediately at one replica but takes time to be transmitted over the network to other replicas. Within this duration, the replicas may be inconsistent.
 
-* **Reliable broadcast** - The increment operation has to be transmitted to all replicas. If the network fails to deliver the operation, the system will never be able to achieve consistency.
-
-* **Concurrent operations** - A replica may have to handle concurrent operations. For example, at *t<sub>19</sub>*, <b>c<sub>1</sub></b> encounters two increment operations. Since the increment operation commutes with itself, the order does not matter. The replica can decide to handle the increments in arbitrary order.
+* **Reliable broadcast** - The increment operation has to be transmitted to all replicas. If the network fails to deliver the operation, the system will never be able to achieve consistency. For example - if the increment operation on **c<sub>2</sub>** at *t<sub>11</sub>* is not transmitted reliably to **c<sub>1</sub>**, then its value will always be one unit less than the correct value.
 
+* **Concurrent operations** - A replica may have to handle concurrent operations. For example, at *t<sub>19</sub>*, <b>c<sub>1</sub></b> encounters two increment operations. Since its the same operation, there is only one way to handle the situation. There is no conflict.
 
-### CvRDT: State based specification
+### 1.2. CvRDT: State based design
 
 In the state based implementation, the counter state is transmitted to all other replicas.
 But how do we model the state? Of course, the counter's count is its state. 
-Since the count always increases, modeling the state as count automatically makes it a monotonic semilattice.
-
-#### Specification
-
-```python
+Since the count always increases, modeling the state as count automatically makes it a join semilattice.
 
-class CvRDT:
-    pass
+The code below provides the specification of this counter.
 
-class Counter(CvRDT):
-
-    def __init__(self, count = 0):  # constructor function
-        self._count = count
-
-    def value(self):                # query function
-        return self._count
-
-    def increment(self):            # update function
-        self._count += 1
+<pre style="background:#fff;color:#000"><span style="color:#ff5600">class</span> <span style="color:#21439c">Counter</span>(CvRDT):
 
-    def compare(self, other):       # comparison function
-        return self.value() <= other.value()
+    <span style="color:#ff5600">def</span> <span style="color:#21439c"><span style="color:#a535ae">__init__</span></span>(self, count <span style="color:#ff5600">=</span> 0):  <span style="color:#919191"># constructor function</span>
+        self._count <span style="color:#ff5600">=</span> count
 
-    def merge(self, other):         # merge function
-        return Counter(max(self.value(), other.value()))
+    <span style="color:#ff5600">def</span> <span style="color:#21439c">value</span>(self):                <span style="color:#919191"># query function</span>
+        <span style="color:#ff5600">return</span> self._count
 
-```
+    <span style="color:#ff5600">def</span> <span style="color:#21439c">increment</span>(self):            <span style="color:#919191"># update function</span>
+        self._count <span style="color:#ff5600">+=</span> 1
 
-#### Figure
+    <span style="color:#ff5600">def</span> <span style="color:#21439c">compare</span>(self, other):       <span style="color:#919191"># comparison function</span>
+        <span style="color:#ff5600">return</span> self.value() <span style="color:#ff5600">&lt;=</span> other.value()
 
-![State based increment only counter (incorrect)][state-based-increment-only-counter-incorrect]
-The figure above shows three replicas (<b>c<sub>1</sub></b>, <b>c<sub>2</sub></b> and <b>c<sub>3</sub></b>) of a state based increment only counter <b>C<sub>state</sub></b>. The clients issue increment requests depicted as <increment-request>. In accordance with the specification, each increment request increments the counter by 1 unit.  and the operation is transmitted by the replica to all other replicas of the system. 
-There are a few interesting observations:
+    <span style="color:#ff5600">def</span> <span style="color:#21439c">merge</span>(self, other):         <span style="color:#919191"># merge function</span>
+        <span style="color:#ff5600">return</span> Counter(<span style="color:#a535ae">max</span>(self.value(), other.value()))
 
-* **Eventual convergence** - At *t<sub>26</sub>*, the replicas are inconsistent. Eventually, they all converge. This is because the increment operation happens immediately at one replica but takes time to be transmitted over the network to other replicas. Within this duration, the replicas may be inconsistent.
+</pre>
 
-> Eventual convergence does not guarantee correctness.
+Let's try to understand how it works through an example. The figure below shows an execution trace of three replicas confirming to this specification. The replicas keep transmitting their state at random times to other randomly chosen replicas.
 
-> Incorrect design may still converge eventually.
+<figure class="fullwidth">
+    <img src="{{ site.baseurl }}/chapter/6/resources/images/counters/state-based-increment-only-counter-incorrect.png" alt="State based increment only counter (incorrect)"/>
+</figure>
 
-* **Unreliable broadcast** - Messages may be lost increment operation has to be transmitted to all replicas. If the network fails to deliver the operation, the system will never be able to achieve consistency.
+We can make the following observations:
 
-* **Concurrent operations** - A replica may have to handle concurrent operations. For example, at *t<sub>19</sub>*, <b>c<sub>1</sub></b> encounters two increment operations. Since the increment operation commutes with itself, the order does not matter. The replica can decide to handle the increments in arbitrary order.
+* **Eventual convergence** - At *t<sub>26</sub>*, the replicas are inconsistent. Eventually, they all converge. This is because the replicas transmit state at random times to randomly chosen replicas. Until their states are merged, the replicas may be inconsistent.
 
-As it can be seen from the figure, the clients issue a total of 4 increment requests. However, the replicas finally converge to 2.
-Something is clearly amiss! When two replicas are incremented, they should together converge to 2. But the `merge` function computes the maximum of two states. 
+* **Correctness** - The clients issue a total of four increment requests. But the eventually consistent value of replicas is 4. So, the design is **incorrect**.
 
+* **Concurrent operations** - A replica may have to handle concurrent operations. For example, at *t<sub>28</sub>*, <b>c<sub>1</sub></b> receives states of the other two replicas. Since the merge operation is commutative, the order in which these operations are handled does not matter.
 
-#### Specification
+* **Unreliable broadcast** - Messages may be lost during transmission. Message sent by <b>c<sub>2</sub></b> at *t<sub>9</sub>* is lost. But eventually, some messages from <b>c<sub>2</sub></b> reach other replicas. As long as messages eventually reach other replicas, directly or indirectly, the system will achieve consistency. A message can also be received out of order or duplicated. 
 
-```python
+Let's figure out why our design is incorrect. We notice that the merge operation simply compares the state of the replicas and returns the bigger of the two counts. What we really need is to add the two counts as we need the total counts issued by all clients across all replicas. But this poses another problem. The merge operation is no longer idempotent, i.e. - repeated merging of same values will not return the same result. This means that if a message gets duplicated, then we will get incorrect count. What's more is that the merge operation will no longer compute the **least** upper bound. It will compute an upper bound but that will not be the least upper bound. This clearly violates the mathematical model we set out to implement. So we can't modify our merge method. This means that we need to change our representation of the state.
+Let's observe the problem again. Our merge method only returns the state of that replica which handled the maximum number of counts. It loses counts of other replicas. Let's represent the state as a sequence of counts. Each value in the sequence corresponds to the count of a replica. So we have as many values in a state as the number of replicas. We also design the merge operation to compute the index-wise maximum of the state.
 
-class CvRDT:
-    pass
+The specification below shows how this can be implemented.
 
-class Counter(CvRDT):
+<pre style="background:#fff;color:#000"><span style="color:#ff5600">class</span> <span style="color:#21439c">Counter</span>(CvRDT):
 
-    def __init__(self, counts = None):  # constructor function
-        if counts is None:
-            self._counts = [0] * length(self.replicas())
-        else:
-            self._counts = counts
+    <span style="color:#ff5600">def</span> <span style="color:#21439c"><span style="color:#a535ae">__init__</span></span>(self, counts <span style="color:#ff5600">=</span> <span style="color:#a535ae">None</span>):  <span style="color:#919191"># constructor function</span>
+        <span style="color:#ff5600">if</span> counts <span style="color:#ff5600">is</span> <span style="color:#a535ae">None</span>:
+            self._counts <span style="color:#ff5600">=</span> [0] <span style="color:#ff5600">*</span> length(self.replicas())
+        <span style="color:#ff5600">else</span>:
+            self._counts <span style="color:#ff5600">=</span> counts
 
-    def value(self):                    # query function
-        return sum(self._counts)
+    <span style="color:#ff5600">def</span> <span style="color:#21439c">value</span>(self):                    <span style="color:#919191"># query function</span>
+        <span style="color:#ff5600">return</span> <span style="color:#a535ae">sum</span>(self._counts)
 
-    def counts(self):                   # query function
-        return list(self._counts)       # return a clone
+    <span style="color:#ff5600">def</span> <span style="color:#21439c">counts</span>(self):                   <span style="color:#919191"># query function</span>
+        <span style="color:#ff5600">return</span> <span style="color:#a535ae">list</span>(self._counts)       <span style="color:#919191"># return a clone</span>
 
-    def increment(self):                # update function
-        self._counts[self.replicaId()] += 1
+    <span style="color:#ff5600">def</span> <span style="color:#21439c">increment</span>(self):                <span style="color:#919191"># update function</span>
+        self._counts[self.replicaId()] <span style="color:#ff5600">+=</span> 1
 
-    def compare(self, other):           # comparison function
-        return all(v1 <= v2 for (v1, v2) in
-                   zip(self.counts(),
+    <span style="color:#ff5600">def</span> <span style="color:#21439c">compare</span>(self, other):           <span style="color:#919191"># comparison function</span>
+        <span style="color:#ff5600">return</span> <span style="color:#a535ae">all</span>(v1 <span style="color:#ff5600">&lt;=</span> v2 <span style="color:#ff5600">for</span> (v1, v2) <span style="color:#ff5600">in</span>
+                   <span style="color:#a535ae">zip</span>(self.counts(),
                        other.counts()))
 
-    def merge(self, other):             # merge function
-        return Counter(map(max, zip(self.counts(),
+    <span style="color:#ff5600">def</span> <span style="color:#21439c">merge</span>(self, other):             <span style="color:#919191"># merge function</span>
+        <span style="color:#ff5600">return</span> Counter(<span style="color:#a535ae">map</span>(<span style="color:#a535ae">max</span>, <span style="color:#a535ae">zip</span>(self.counts(),
                                     other.counts())))
 
-```
+</pre>
 
-#### Figure
+The figure below shows an execution trace of three replicas confirming to this specification.
 
-![State based increment only counter (correct)][state-based-increment-only-counter-correct]
+<figure class="fullwidth">
+    <img src="{{ site.baseurl }}/chapter/6/resources/images/counters/state-based-increment-only-counter-correct.png" alt="State based increment only counter (correct) lattice"/>
+</figure>
 
-As it can be seen from the figure, the clients issue a total of 4 increment requests. However, the replicas finally converge to 2.
-Something is clearly amiss! When two replicas are incremented, they should together converge to 2. But the `merge` function computes the maximum of two states. 
+This design converges to the correct value. This provides us an eventually consistent state based increment only counter.
 
-## PN-counter - Increment and Decrement counter
+## 2. PN-counter - Increment and Decrement counter
 
-A PN-counter can be incremented and decremented.
+A PN-counter can be incremented and decremented. These can serve as a general purpose counters, as they also provide a decrement operation. For example - counting the number of users active one a social media website at any point. Note that the users can go offline and the counter will have to decremented. This can't be done with an increment only counter.
 
-### CmRDT: Operation based specification
+### 2.1. CmRDT: Operation based design
 
 The code below provides the specification of an operation based increment and decrement counter.
 
@@ -174,26 +157,29 @@ The code below provides the specification of an operation based increment and de
             self.transmit(<span style="color:#00a33f">"decrement"</span>, replica)
 </pre>
 
-Let's try to understand how it works through an example. The figure below shows three replicas (<b>c<sub>1</sub></b>, <b>c<sub>2</sub></b> and <b>c<sub>3</sub></b>) of an operation based increment and decrement counter <b>C<sub>operation</sub></b>. 
+Let's try to understand how it works through an example. The figure below shows an execution trace of three replicas confirming to this specification. In accordance with the specification, each increment request increments the counter locally by one unit and each decrement request decrements the counter locally by one unit. The corresponding operation is transmitted by the replica to all other replicas of the system. 
+
+<figure class="fullwidth">
+    <img style="margin: auto; display: block;" src="{{ site.baseurl }}/chapter/6/resources/images/counters/operation-based-increment-and-decrement-counter.png" alt="Operation based increment and decrement counter"/>
+</figure>
+
+We can make the the following observations:
+
+* **Eventual Consistency** - At *t<sub>26</sub>*, the replicas are inconsistent. Eventually, they all achieve consistency. This is because the operations happen immediately at one replica but take time to be transmitted over the network to other replicas. Within this duration, the replicas may be inconsistent.
 
-* ![increment operation][increment-operation] depicts increment request issued by the client.
-* ![decrement operation][decrement-operation] depicts decrement request issued by the client.
+* **Reliable broadcast** - Each operation has to be transmitted to all replicas. If the network fails to deliver an operation, the system will never be able to achieve consistency. For example - if the decrement operation on **c<sub>2</sub>** at *t<sub>6</sub>* is not transmitted reliably to **c<sub>1</sub>**, then its value will always be one unit more than the correct value.
 
-In accordance with the specification, each increment request increments the counter locally by one unit and each decrement request decrements the counter locally by one unit. The corresponding operation is transmitted by the replica to all other replicas of the system. 
+* **Concurrent operations** - A replica may have to handle concurrent operations. For example, at *t<sub>30</sub>*, <b>c<sub>1</sub></b> and <b>c<sub>2</sub></b> encounter increment and decrement operations concurrently. Let's take a look at the two choices:
 
 <figure class="fullwidth">
-    <img src="{{ site.baseurl }}/chapter/6/resources/images/counters/operation-based-increment-and-decrement-counter.png" alt="Operation based increment and decrement counter"/>
+    <img style="margin: auto; display: block;" src="{{ site.baseurl }}/chapter/6/resources/images/counters/increment-and-decrement-operations-commute.png" alt="Increment and decrement operations commute"/>
 </figure>
 
-One can make the the following observations:
-
-* **Eventually consistent** - At *t<sub>26</sub>*, the replicas are inconsistent. Eventually, they all achieve consistency. This is because the operations happen immediately at one replica but take time to be transmitted over the network to other replicas. Within this duration, the replicas may be inconsistent.
-* **Reliable broadcast** - The operations have to be transmitted to all replicas. If the network fails to deliver an operation, the system will never be able to achieve consistency.
-* **Concurrent operations** - A replica may have to handle concurrent operations. For example, at *t<sub>30</sub>*, <b>c<sub>1</sub></b> and <b>c<sub>2</sub></b> encounter increment and decrement operations concurrently. Since the increment and decrement  operations commute, the order in which they are executed by the replicas does not matter. Both replicas perform them in different orders and still achieve consistency, eventually.
+In both cases the result is same because the two operations commute, i.e. - the order in which they are executed by the replicas does not matter. Both replicas perform them in different orders and still achieve consistency, eventually.
 
-### CvRDT: State based specification
+### 2.2. CvRDT: State based design
 
-The code below provides the specification of a state based increment and decrement counter.
+The code below provides the specification of a state based increment and decrement counter. We take inspiration from the design of state based increment only counter and model the state of this counter in the same way.
 
 <pre style="background:#fff;color:#000"><span style="color:#ff5600">class</span> <span style="color:#21439c">Counter</span>(CvRDT):
 
@@ -226,12 +212,7 @@ The code below provides the specification of a state based increment and decreme
 
 </pre>
 
-Let's try to understand how it works through an example. The figure below shows three replicas (<b>c<sub>1</sub></b>, <b>c<sub>2</sub></b> and <b>c<sub>3</sub></b>) of a state based increment and decrement counter <b>C<sub>state</sub></b>. 
-
-* ![increment operation][increment-operation] depicts increment request issued by the client.
-* ![decrement operation][decrement-operation] depicts decrement request issued by the client.
-
-In accordance with the specification, each increment request increments the counter by one unit and each decrement request decrements the counte by one unit. The replica transmits its state at random times to a random replica.
+Let's try to understand how it works through an example. The figure below shows an execution trace of three replicas confirming to this specification. The replicas keep transmitting their state at random times to other randomly chosen replicas.
 
 <figure class="fullwidth">
     <img src="{{ site.baseurl }}/chapter/6/resources/images/counters/state-based-increment-and-decrement-counter-incorrect.png" alt="State based increment and decrement counter (incorrect)"/>
@@ -239,12 +220,23 @@ In accordance with the specification, each increment request increments the coun
 
 We can make the the following observations:
 
-* **Eventual convergence** - At *t<sub>26</sub>*, the replicas are inconsistent. Eventually, they all converge. This is because the increment operation happens immediately at one replica but takes time to be transmitted over the network to other replicas. Within this duration, the replicas may be inconsistent.
+* **Eventual convergence** - At *t<sub>26</sub>*, the replicas are inconsistent. Eventually, they all converge. This is because the replicas transmit state at random times to randomly chosen replicas. Until their states are merged, the replicas may be inconsistent.
+
 * **Correctness** - The clients issue a total of four increment requests and 2 decrement requests. But the eventually consistent value of replicas is 4. So, the design is **incorrect**.
+
 * **Concurrent operations** - A replica may have to handle concurrent operations. For example, at *t<sub>27</sub>* <b>c<sub>1</sub></b> has to handle 2 merge operations concurrently. Since the state forms a partially ordered set and the merge operation computes its least upper bound, the order in which the merge operation happens does not affect the final outcome. Similarly, at *t<sub>21</sub>* and *t<sub>29</sub>*, two operations arrive concurrently at <b>c<sub>3</sub></b> and <b>c<sub>2</sub></b> respectively.
+
 * **Unreliable broadcast** - Messages may be lost during transmission. Message sent by <b>c<sub>3</sub></b> at *t<sub>12</sub>* is lost. But eventually, message at *t<sub>25</sub>* reaches another replica. As long as messages eventually reach other replicas, directly or indirectly, the system will achieve consistency. A message can also be received out of order or duplicated. 
 
-Let's try to figure out why the design is incorrect. At *t<sub>12</sub>*, <b>c<sub>1</sub></b> merges the state from <b>c<sub>2</sub></b>. The merge operation computes the index wise maximum in accordance with the specification. In doing so, the *-1* value of *c<sub>2</sub>* due to the decrement operation at *t<sub>6</sub>* is lost. Its clear that we have violated the basic constraint, the decrement operation does not take the state higher up in the lattice. In other words, the decrement operation is non monotonic. This causes us to lose the decrements and we are eventually left with replicas which only count the total number of increment requests.
+Though we modeled the state after the increment only state based counter, this design doesn't work. Let's try to figure out what went wrong. At *t<sub>12</sub>*, <b>c<sub>1</sub></b> merges the state from <b>c<sub>2</sub></b>. The merge operation computes the index wise maximum in accordance with the specification. In doing so, the *-1* value of *c<sub>2</sub>* due to the decrement operation at *t<sub>6</sub>* is lost. 
+To make matters clearer, let's look at a section of the lattice formed by the state of this counter -
+
+<figure class="fullwidth">
+    <img src="{{ site.baseurl }}/chapter/6/resources/images/counters/state-based-increment-and-decrement-counter-incorrect-lattice.png" alt="State based increment and decrement counter(incorrect) lattice"/>
+</figure>
+
+Its clear that we have violated the basic constraint, the decrement operation does not take the state higher up in the lattice. In other words, the decrement operation is non monotonic. So, when the results of increment and decrement operations are merged together, then the result of the increment operation is returned, as it is always higher up in the lattice. So the replicas only count the total number of increments.
+
 But we do gain two valuable insights from this design-
 
 > Eventual convergence does not guarantee correctness.
@@ -252,7 +244,7 @@ But we do gain two valuable insights from this design-
 > Incorrect designs may still converge eventually.
 
 
-Let's try to correct this problem. The problem happens because the decrement operation is non-monotonic. So we need a way to count the decrement operations without losing monotonicity. One solution is to model this counter using two increment only counters. The first counter counts the increment operations and the second one counts the decrement operations. The value of the actual counter is the difference between the two corresponding counters. The specification below shows how this can be implemented.
+Let's try to correct this problem. We need a way to count the decrement operations without losing monotonicity. One solution is to model this counter using two increment only counters. The first counter counts the increment operations and the second one counts the decrement operations. The value of the actual counter is the difference between the two corresponding counters. The specification below shows how this can be implemented.
 
 <pre style="background:#fff;color:#000"><span style="color:#ff5600">class</span> <span style="color:#21439c">Counter</span>(CvRDT):
 
@@ -301,19 +293,18 @@ Let's try to correct this problem. The problem happens because the decrement ope
 
 </pre>
 
-The figure below shows an execution trace of three replicas (<b>c<sub>1</sub></b>, <b>c<sub>2</sub></b> and <b>c<sub>3</sub></b>) of this counter.
-
-* ![increment operation][increment-operation] depicts increment request issued by the client.
-* ![decrement operation][decrement-operation] depicts decrement request issued by the client.
-
-The values in the top row in the replica state depict the increments and the bottom ones depict the decrements. In accordance with the specification, each increment request increments the value in the top row by one unit and each decrement request increments the value in the lower row by one unit. Once the operation materializes locally, the new state is transmitted by the replica to some other randomly chosen replica.
+The figure below shows an execution trace of three replicas confirming to this specification.
 
 <figure class="fullwidth">
     <img src="{{ site.baseurl }}/chapter/6/resources/images/counters/state-based-increment-and-decrement-counter-correct.png" alt="State based increment and decrement counter (correct)"/>
 </figure>
 
-This design converges to the correct value.
+This design converges to the correct value. This provides us an eventually consistent state based increment and decrement counter.
+
+
+## 3. References
 
+{% bibliography --file counters %}
 
 [increment-operation]: resources/images/counters/increment-operation.png
 [decrement-operation]: resources/images/counters/decrement-operation.png
diff --git a/chapter/6/resources/images/counters/increment-and-decrement-operations-commute.png b/chapter/6/resources/images/counters/increment-and-decrement-operations-commute.png
new file mode 100644
index 0000000..93b52bf
Binary files /dev/null and b/chapter/6/resources/images/counters/increment-and-decrement-operations-commute.png differ
diff --git a/chapter/6/resources/images/counters/operation-based-increment-and-decrement-counter.png b/chapter/6/resources/images/counters/operation-based-increment-and-decrement-counter.png
index f046c0b..ddbc789 100644
Binary files a/chapter/6/resources/images/counters/operation-based-increment-and-decrement-counter.png and b/chapter/6/resources/images/counters/operation-based-increment-and-decrement-counter.png differ
diff --git a/chapter/6/resources/images/counters/operation-based-increment-only-counter.png b/chapter/6/resources/images/counters/operation-based-increment-only-counter.png
index 398c562..1231b92 100644
Binary files a/chapter/6/resources/images/counters/operation-based-increment-only-counter.png and b/chapter/6/resources/images/counters/operation-based-increment-only-counter.png differ
diff --git a/chapter/6/resources/images/counters/state-based-increment-and-decrement-counter-correct.png b/chapter/6/resources/images/counters/state-based-increment-and-decrement-counter-correct.png
index 0d6468b..880aee0 100644
Binary files a/chapter/6/resources/images/counters/state-based-increment-and-decrement-counter-correct.png and b/chapter/6/resources/images/counters/state-based-increment-and-decrement-counter-correct.png differ
diff --git a/chapter/6/resources/images/counters/state-based-increment-and-decrement-counter-incorrect-lattice.png b/chapter/6/resources/images/counters/state-based-increment-and-decrement-counter-incorrect-lattice.png
new file mode 100644
index 0000000..d13dfaa
Binary files /dev/null and b/chapter/6/resources/images/counters/state-based-increment-and-decrement-counter-incorrect-lattice.png differ
diff --git a/chapter/6/resources/images/counters/state-based-increment-and-decrement-counter-incorrect.png b/chapter/6/resources/images/counters/state-based-increment-and-decrement-counter-incorrect.png
index 3f7f1b9..7981767 100644
Binary files a/chapter/6/resources/images/counters/state-based-increment-and-decrement-counter-incorrect.png and b/chapter/6/resources/images/counters/state-based-increment-and-decrement-counter-incorrect.png differ
diff --git a/chapter/6/resources/images/counters/state-based-increment-only-counter-correct.png b/chapter/6/resources/images/counters/state-based-increment-only-counter-correct.png
index 4ca2843..c382f8b 100644
Binary files a/chapter/6/resources/images/counters/state-based-increment-only-counter-correct.png and b/chapter/6/resources/images/counters/state-based-increment-only-counter-correct.png differ
diff --git a/chapter/6/resources/images/counters/state-based-increment-only-counter-incorrect.png b/chapter/6/resources/images/counters/state-based-increment-only-counter-incorrect.png
index 3f95e59..3e79e42 100644
Binary files a/chapter/6/resources/images/counters/state-based-increment-only-counter-incorrect.png and b/chapter/6/resources/images/counters/state-based-increment-only-counter-incorrect.png differ
-- 
cgit v1.2.3


From 2a9048a1f87a2fcff1d9fcdd035108cec4b44a14 Mon Sep 17 00:00:00 2001
From: Aviral Goel <goel.aviral@gmail.com>
Date: Mon, 19 Dec 2016 14:23:50 -0500
Subject: Added lattice diagram for the state based pn counter

---
 chapter/6/counters.md                                 |   5 ++++-
 ...ncrement-and-decrement-counter-correct-lattice.png | Bin 0 -> 1346630 bytes
 2 files changed, 4 insertions(+), 1 deletion(-)
 create mode 100644 chapter/6/resources/images/counters/state-based-increment-and-decrement-counter-correct-lattice.png

(limited to 'chapter')

diff --git a/chapter/6/counters.md b/chapter/6/counters.md
index a2709af..95b6c5d 100644
--- a/chapter/6/counters.md
+++ b/chapter/6/counters.md
@@ -299,8 +299,11 @@ The figure below shows an execution trace of three replicas confirming to this s
     <img src="{{ site.baseurl }}/chapter/6/resources/images/counters/state-based-increment-and-decrement-counter-correct.png" alt="State based increment and decrement counter (correct)"/>
 </figure>
 
-This design converges to the correct value. This provides us an eventually consistent state based increment and decrement counter.
+This design converges to the correct value. This provides us an eventually consistent state based increment and decrement counter. You can take a look at the lattice to convince yourself.
 
+<figure class="fullwidth">
+    <img src="{{ site.baseurl }}/chapter/6/resources/images/counters/state-based-increment-and-decrement-counter-correct-lattice.png" alt="State based increment and decrement counter(correct) lattice"/>
+</figure>
 
 ## 3. References
 
diff --git a/chapter/6/resources/images/counters/state-based-increment-and-decrement-counter-correct-lattice.png b/chapter/6/resources/images/counters/state-based-increment-and-decrement-counter-correct-lattice.png
new file mode 100644
index 0000000..2bbcf6b
Binary files /dev/null and b/chapter/6/resources/images/counters/state-based-increment-and-decrement-counter-correct-lattice.png differ
-- 
cgit v1.2.3


From f27ba2bd06be195a06fe11b571aebd9a7c1ef930 Mon Sep 17 00:00:00 2001
From: Aviral Goel <goel.aviral@gmail.com>
Date: Mon, 19 Dec 2016 14:25:21 -0500
Subject: Corrected text

---
 chapter/6/counters.md | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

(limited to 'chapter')

diff --git a/chapter/6/counters.md b/chapter/6/counters.md
index 95b6c5d..67e822a 100644
--- a/chapter/6/counters.md
+++ b/chapter/6/counters.md
@@ -299,7 +299,7 @@ The figure below shows an execution trace of three replicas confirming to this s
     <img src="{{ site.baseurl }}/chapter/6/resources/images/counters/state-based-increment-and-decrement-counter-correct.png" alt="State based increment and decrement counter (correct)"/>
 </figure>
 
-This design converges to the correct value. This provides us an eventually consistent state based increment and decrement counter. You can take a look at the lattice to convince yourself.
+This design converges to the correct value. This provides us an eventually consistent state based increment and decrement counter. We can take a look at the lattice formed by the state to convince ourselves.
 
 <figure class="fullwidth">
     <img src="{{ site.baseurl }}/chapter/6/resources/images/counters/state-based-increment-and-decrement-counter-correct-lattice.png" alt="State based increment and decrement counter(correct) lattice"/>
-- 
cgit v1.2.3