Declarative, Convergent, Edge Computation

Craft Conference, 2017

Transcript

1. Declarative, Convergent, Edge Computation Christopher S. Meiklejohn Université catholique de Louvain, Belgium Instituto Superior Técnico, Portugal LIGHT ONE
2. RA RB
3. RA RB 1 set(1)
4. RA RB 1 set(1) 3 2 set(2) set(3) Concurrent operations.
5. RA RB 1 set(1) 3 2 set(2) set(3) ? ? Nondeterministic outcome.
6. Synchronization • To enforce an order
 Makes programming easier 6
7. Synchronization • To enforce an order
 Makes programming easier • Eliminate accidental nondeterminism
 Prevent race conditions 6
8. Synchronization • To enforce an order
 Makes programming easier • Eliminate accidental nondeterminism
 Prevent race conditions • Techniques
 Locks, mutexes, semaphores, monitors, Paxos, Raft, etc. 6
9. Difficult Cases • “Internet of Things”, 
 Low power, limited memory and connectivity 7
10. Difficult Cases • “Internet of Things”, 
 Low power, limited memory and connectivity • Mobile Gaming
 Offline operation with replicated, shared state 7
12. The Fundamentals of Distributed Computation 9
13. Distributed Computation • Concurrent to distributed programming
 Consistency and now partial failure 10
14. Distributed Computation • Concurrent to distributed programming
 Consistency and now partial failure • Enforcing the “single system” illusion
 Traditional approach for gaining performance, scalability, fault- tolerance while still “easy to program” 10
15. Distributed Computation • Concurrent to distributed programming
 Consistency and now partial failure • Enforcing the “single system” illusion
 Traditional approach for gaining performance, scalability, fault- tolerance while still “easy to program” • Consistency models
 Contract between the system and the programmer 10
16. Distributed Computation • Concurrent to distributed programming
 Consistency and now partial failure • Enforcing the “single system” illusion
 Traditional approach for gaining performance, scalability, fault- tolerance while still “easy to program” • Consistency models
 Contract between the system and the programmer • Correctness criteria
 For both distributed and concurrent programs 10
17. Distributed Computation • Concurrent to distributed programming
 Consistency and now partial failure • Enforcing the “single system” illusion
 Traditional approach for gaining performance, scalability, fault- tolerance while still “easy to program” • Consistency models
 Contract between the system and the programmer • Correctness criteria
 For both distributed and concurrent programs • Synchronization as “knob”
 Models live along a spectrum requiring more or less synchronization 10
18. Databases Consistency Models 11
19. Databases Strong Consistency 12
20. R1 C1 C2 13
21. R1 C1 C2 14
22. R1 C1 C2 Read 15
23. R1 C1 C2 Read 16
24. R1 C1 C2 17
25. R1 C1 C2 CAS 18
26. R1 C1 C2 19
27. R1 C1 C2 CAS 20 Operation refused because value changed between read/write.
28. I won’t diagram the Paxos protocol 21
29. R2 C1 C2 Value 2 Value 1 Value 2 R1 R3 Paxos 22 Coordination is extremely expensive.
30. Databases Eventual Consistency 23
31. R1 R2 R3 C1 C2 24
32. R1 R2 R3 C1 C2 25
33. R1 R2 R3 C1 C2 Read 26
34. R1 R2 R3 C1 C2 Read 27
35. R1 R2 R3 C1 C2 Write 28
36. R1 R2 R3 C1 C2 Write 29
37. R1 R2 R3 C1 C2 Write C1 30 Do I store both values or do I choose a value arbitrarily?
38. R1 R2 R3 C1 C2 Read 31 If I store both, the programmer must expect multiple values…
39. R1 R2 R3 C1 C2 Write 32 …and be able to semantically resolve them in application code.
40. Strong Eventual Consistency (SEC) • Convergent
 Same updates realize the same state 33
41. Strong Eventual Consistency (SEC) • Convergent
 Same updates realize the same state • Primary requirement
 “Eventual” replica-to-replica communication 33
42. Strong Eventual Consistency (SEC) • Convergent
 Same updates realize the same state • Primary requirement
 “Eventual” replica-to-replica communication • Order insensitive!
 Operations are commutative 33
43. Strong Eventual Consistency (SEC) • Convergent
 Same updates realize the same state • Primary requirement
 “Eventual” replica-to-replica communication • Order insensitive!
 Operations are commutative • Duplicate insensitive!
 Operations are idempotent 33
44. RA RB
45. RA RB 1 set(1)
46. RA RB 1 set(1) 3 2 set(2) set(3)
47. RA RB 1 3 2 3 3 set(1) set(2) set(3) max(2,3) max(2,3) Automatic resolution of conflicting updates.
48. How can we succeed with Strong Eventual Consistency? 38
49. Programming SEC 1. Eliminate accidental nondeterminism
 (ex. deterministic, modeling non-monotonic operations monotonically) 39
50. Programming SEC 1. Eliminate accidental nondeterminism
 (ex. deterministic, modeling non-monotonic operations monotonically) 2. Retain the properties of functional programming
 (ex. confluence, “correct-by-construction” applications) 39
51. Programming SEC 1. Eliminate accidental nondeterminism
 (ex. deterministic, modeling non-monotonic operations monotonically) 2. Retain the properties of functional programming
 (ex. confluence, “correct-by-construction” applications) 3. Distributed, and fault-tolerant runtime
 (ex. replication, membership, dissemination) 39
52. Programming SEC 1. Eliminate accidental nondeterminism
 (ex. deterministic, modeling non-monotonic operations monotonically) 2. Retain the properties of functional programming
 (ex. confluence, “correct-by-construction” applications) 3. Distributed, and fault-tolerant runtime
 (ex. replication, membership, dissemination) 40
53. Convergent Objects
 Conflict-Free 
 Replicated Data Types 41 SSS 2011
54. Conflict-Free 
 Replicated Data Types • Many types exist with different properties
 Sets, counters, registers, flags, maps 42
55. Conflict-Free 
 Replicated Data Types • Many types exist with different properties
 Sets, counters, registers, flags, maps • Strong Eventual Consistency
 Instances satisfy SEC property per-object 42
56. Conflict-Free 
 Replicated Data Types • Many types exist with different properties
 Sets, counters, registers, flags, maps • Strong Eventual Consistency
 Instances satisfy SEC property per-object • Bounded join-semilattices
 Formalized using bounded join-semilattices where the merge operation is the join 42
57. Convergent Objects Observed-Remove Set 43
58. RA RB RC
59. RA RB RC {1} (1, {a}, {}) add(1)
60. RA RB RC {1} (1, {a}, {}) add(1) {1} (1, {b}, {}) add(1)
61. RA RB RC {1} (1, {a}, {}) add(1) {1} (1, {b}, {}) add(1) {} (1, {b}, {b}) remove(1)
62. RA RB RC {1} (1, {a}, {}) add(1) {1} (1, {b}, {}) add(1) {} (1, {b}, {b}) remove(1) {1} {1} {1} (1, {a, b}, {b}) (1, {a, b}, {b}) (1, {a, b}, {b}) Convergence reached.
63. Convergent Objects Composition 49
64. RA {1} (1, {a}, {}) {1} (1, {a, b}, {a}) RB {1} (1, {b}, {}) {1} (1, {a, b}, {a}) {} (1, {a}, {a}) add(1) remove(1) add(1) Replicated set of naturals across two nodes.
65. RA {1} (1, {a}, {}) {1} (1, {a, b}, {a}) RB {1} (1, {b}, {}) {1} (1, {a, b}, {a}) {} (1, {a}, {a}) add(1) remove(1) add(1) Map Process \x.2x F(RA) {2} {2} {} F(RB) {2} ? Map Process \x.2x Map Process \x.2x Map Process \x.2x Map Process \x.2x {2} Map \x.2x over a set of naturals.
66. RA {1} (1, {a}, {}) {1} (1, {a, b}, {a}) RB {1} (1, {b}, {}) {1} (1, {a, b}, {a}) {} (1, {a}, {a}) add(1) remove(1) add(1) Map Process \x.2x F(RA) {2} {2} {} F(RB) {2} ? Map Process \x.2x Map Process \x.2x Map Process \x.2x Map Process \x.2x {2} One node…
67. RA {1} (1, {a}, {}) {1} (1, {a, b}, {a}) RB {1} (1, {b}, {}) {1} (1, {a, b}, {a}) {} (1, {a}, {a}) add(1) remove(1) add(1) Map Process \x.2x F(RA) {2} {2} {} F(RB) {2} ? Map Process \x.2x Map Process \x.2x Map Process \x.2x Map Process \x.2x {2} …another node.
68. RA {1} (1, {a}, {}) {1} (1, {a, b}, {a}) RB {1} (1, {b}, {}) {1} (1, {a, b}, {a}) {} (1, {a}, {a}) add(1) remove(1) add(1) Map Process \x.2x F(RA) {2} {2} {} F(RB) {2} ? Map Process \x.2x Map Process \x.2x Map Process \x.2x Map Process \x.2x {2}
69. RA {1} (1, {a}, {}) {1} (1, {a, b}, {a}) RB {1} (1, {b}, {}) {1} (1, {a, b}, {a}) {} (1, {a}, {a}) add(1) remove(1) add(1) Map Process \x.2x F(RA) {2} {2} {} F(RB) {2} ? Map Process \x.2x Map Process \x.2x Map Process \x.2x Map Process \x.2x {2} Nondeterministic outcome.
70. RA {1} (1, {a}, {}) {1} (1, {a, b}, {a}) RB {1} (1, {b}, {}) {1} (1, {a, b}, {a}) {} (1, {a}, {a}) add(1) remove(1) add(1) Map Process \x.2x F(RA) {2} {2} {} F(RB) {2} ? Map Process \x.2x Map Process \x.2x Map Process \x.2x Map Process \x.2x {2} Correct output that’s seen all updates.
71. RA {1} (1, {a}, {}) {1} (1, {a, b}, {a}) RB {1} (1, {b}, {}) {1} (1, {a, b}, {a}) {} (1, {a}, {a}) add(1) remove(1) add(1) Map Process \x.2x F(RA) {2} {2} {} F(RB) {2} ? Map Process \x.2x Map Process \x.2x Map Process \x.2x Map Process \x.2x {2} “Earlier” value that’s been delayed.
72. Programming SEC 1. Eliminate accidental nondeterminism
 (ex. deterministic, modeling non-monotonic operations monotonically) 2. Retain the properties of functional programming
 (ex. confluence, “correct-by-construction” applications) 3. Distributed, and fault-tolerant runtime
 (ex. replication, membership, dissemination) 58
73. Convergent Programs Lattice Processing 59 PPDP 2015
74. Lattice Processing • Asynchronous dataflow with streams
 Combine and transform streams of inputs into streams of outputs 60
75. Lattice Processing • Asynchronous dataflow with streams
 Combine and transform streams of inputs into streams of outputs • Convergent data structures
 Data abstraction (inputs/outputs) is the CRDT 60
76. Lattice Processing • Asynchronous dataflow with streams
 Combine and transform streams of inputs into streams of outputs • Convergent data structures
 Data abstraction (inputs/outputs) is the CRDT • Confluence
 Provides composition that preserves the SEC property 60
77. Lattice Processing Confluence 61
78. A B Map Process \x.2x 62 Sequential specification.
79. A’ A’’ B’ B’’ Map Process \x.2x Map Process \x.2x A B Map Process \x.2x 63 Replication per node.
80. A’ A’’ B’ B’’ Map Process \x.2x Map Process \x.2x A B Map Process \x.2x 64 Replication per node.
81. A’ A’’ B’ B’’ Map Process \x.2x Map Process \x.2x A B Map Process \x.2x 65 Replication per node.
82. A’ A’’ B’ B’’ Map Process \x.2x Map Process \x.2x A B Map Process \x.2x 66 One possible schedule….
83. A’ A’’ B’ B’’ Map Process \x.2x Map Process \x.2x A B Map Process \x.2x 67 …another possible schedule.
84. A’ A’’ B’ B’’ Map Process \x.2x Map Process \x.2x A B Map Process \x.2x 68
85. A B Map Process \x.2x 69 All schedules equivalent to sequential schedule.
86. A B F 70 Arbitrary application.
87. Lattice Processing Example 71
88. 72 %% Create initial set. S1 = declare(set), %% Add elements to initial set and update. update(S1, {add, [1,2,3]}), %% Create second set. S2 = declare(set), %% Apply map operation between S1 and S2. map(S1, fun(X) -> X * 2 end, S2).
89. 73 %% Create initial set. S1 = declare(set), %% Add elements to initial set and update. update(S1, {add, [1,2,3]}), %% Create second set. S2 = declare(set), %% Apply map operation between S1 and S2. map(S1, fun(X) -> X * 2 end, S2).
90. 74 %% Create initial set. S1 = declare(set), %% Add elements to initial set and update. update(S1, {add, [1,2,3]}), %% Create second set. S2 = declare(set), %% Apply map operation between S1 and S2. map(S1, fun(X) -> X * 2 end, S2).
91. 75 %% Create initial set. S1 = declare(set), %% Add elements to initial set and update. update(S1, {add, [1,2,3]}), %% Create second set. S2 = declare(set), %% Apply map operation between S1 and S2. map(S1, fun(X) -> X * 2 end, S2).
92. 76 %% Create initial set. S1 = declare(set), %% Add elements to initial set and update. update(S1, {add, [1,2,3]}), %% Create second set. S2 = declare(set), %% Apply map operation between S1 and S2. map(S1, fun(X) -> X * 2 end, S2).
93. Processes • Replicas as monotonic streams
 Each replica of a CRDT produces a monotonic stream of states 77
94. Processes • Replicas as monotonic streams
 Each replica of a CRDT produces a monotonic stream of states • Monotonic processes
 Read from one or more input replica streams and produce a single output replica stream 77
95. Processes • Replicas as monotonic streams
 Each replica of a CRDT produces a monotonic stream of states • Monotonic processes
 Read from one or more input replica streams and produce a single output replica stream • Inflationary reads
 Read operation ensures that we only read inflationary updates to replicas 77
96. Lattice Processing Monotonic Streams 78
97. RA {} C1 {} C2 {} 79
98. RA {} (1, {a}, {}) C1 (1, {a}, {}) {} C2 {} 80
99. RA {} (1, {a}, {}) (1, {a, b}, {}) C1 (1, {a}, {}) {} C2 (1, {b}, {}) {} 81
100. RA {} (1, {a}, {}) (1, {a, b}, {}) (1, {a, b}, {a}) C1 (1, {a}, {}) {} (1, {a}, {a}) C2 (1, {b}, {}) {} 82
101. RA {} (1, {a}, {}) (1, {a, b}, {}) (1, {a, b}, {a}) C1 (1, {a}, {}) {} (1, {a}, {a}) C2 (1, {b}, {}) {} (1, {a, b}, {a}) (1, {a, b}, {a}) (1, {a, b}, {a}) 83
102. RA {} (1, {a}, {}) (1, {a, b}, {}) (1, {a, b}, {a}) C1 (1, {a}, {}) {} (1, {a}, {a}) C2 (1, {b}, {}) {} (1, {a, b}, {a}) (1, {a, b}, {a}) (1, {a, b}, {a}) 84 Clients can operate with partial state…
103. RA {} (1, {a}, {}) (1, {a, b}, {}) (1, {a, b}, {a}) C1 (1, {a}, {}) {} (1, {a}, {a}) C2 (1, {b}, {}) {} (1, {a, b}, {a}) (1, {a, b}, {a}) (1, {a, b}, {a}) 85 … and synchronize with their local replica.
104. Lattice Processing Monotonic Processes 86
105. RA {} P1 F(RA) {} 87
106. RA {} P1 F(RA) {} strict_read({}) 88
107. RA {} P1 F(RA) {} strict_read({}) (1, {a}, {}) 89
108. RA {} P1 F(RA) {} strict_read({}) (1, {a}, {}) F((1, {a}, {})) 90
109. RA {} P1 F(RA) {} strict_read({}) (1, {a}, {}) F((1, {a}, {})) (2, {a}, {}) 91 Every time replica changes…
110. RA {} P1 F(RA) {} strict_read({}) (1, {a}, {}) F((1, {a}, {})) (2, {a}, {}) 92 ….the process will compute a new result.
111. RA {} P1 F(RA) {} strict_read({}) (1, {a}, {}) F((1, {a}, {})) (2, {a}, {}) strict_read((1, {a}, {}) (1, {a}, {}) 93
112. RA {} P1 F(RA) {} strict_read({}) (1, {a}, {}) F((1, {a}, {})) (2, {a}, {}) strict_read((1, {a}, {}) (1, {a}, {}) (1, {a}, {a}) F((1, {a}, {a})) (2, {a}, {a}) strict_read((1, {a}, {a}) (1, {a}, {a}) 94
113. RA {} P1 F(RA) {} strict_read({}) (1, {a}, {}) (1, {a}, {}) (1, {a}, {a}) F((1, {a}, {a})) (2, {a}, {a}) strict_read((1, {a}, {a}) (1, {a}, {a}) 95 Omitted interleaving does not sacrifice correctness.
114. Lattice Processing Map Example 96
115. RC F(RC) 97
116. RC F(RC) {2} Map Process \x.2x (2, {b}, {}) (1, {b}, {}) {1} 98 Transform element, map metadata.
117. RC F(RC) {2} Map Process \x.2x (2, {b}, {}) (1, {b}, {}) {1} {} (1, {b}, {b}) {} Map Process \x.2x (2, {b}, {b}) 99
118. RC F(RC) {2} Map Process \x.2x (2, {b}, {}) (1, {b}, {}) {1} {} (1, {b}, {b}) {} Map Process \x.2x (2, {b}, {b}) {1} (1, {a, b}, {b}) {2} Map Process \x.2x (2, {a, b}, {b}) 100
119. RC F(RC) {2} Map Process \x.2x (2, {b}, {}) (1, {b}, {}) {1} {} (1, {b}, {b}) {} Map Process \x.2x (2, {b}, {b}) {1} (1, {a, b}, {b}) {2} Map Process \x.2x (2, {a, b}, {b}) {1} {2} 101
120. Programming SEC 1. Eliminate accidental nondeterminism
 (ex. deterministic, modeling non-monotonic operations monotonically) 2. Retain the properties of functional programming
 (ex. confluence, “correct-by-construction” applications) 3. Distributed, and fault-tolerant runtime
 (ex. replication, membership, dissemination) 102
121. Example Application Advertisement Counter 103
122. Advertisement Counter • Lower-bound invariant
 Advertisements are paid according to a minimum number of impressions 104
123. Advertisement Counter • Lower-bound invariant
 Advertisements are paid according to a minimum number of impressions • Clients will go offline
 Clients have limited connectivity and the system still needs to make progress while clients are offline 104
124. Advertisement Counter • Lower-bound invariant
 Advertisements are paid according to a minimum number of impressions • Clients will go offline
 Clients have limited connectivity and the system still needs to make progress while clients are offline • No lost updates
 All displayed advertisements should be accounted for, with no lost updates 104
125. Advertisement Counter Losing Updates 105
126. RA RB 106
127. RA RB 1 set(1) 107
128. RA RB 1 set(1) 2 2 set(2) set(2) 108
129. RA RB 1 set(1) 2 2 set(2) set(2) 2 2 max(2,2) max(2,2) 109
130. RA RB 1 set(1) 2 2 set(2) set(2) 2 2 max(2,2) max(2,2) 110 Incorrect value is computed because of incompatible lattice.
131. Advertisement Counter Application Flow 111
132. Server Client Client 112
133. Server Client Client 113 Client reads state from the server.
134. Server Client Client 114 Client locally mutates state.
135. Server Client Client 115 Client pushes changes back to the server.
136. Server Client Client 116
137. Server Client Client 117 Server enforces invariants over state.
138. Server Client Client 118 Client retrieves updated state periodically.
139. Server Client Client 119 Clients unable to communicate may violate invariant.
140. Advertisement Counter Application Design 120
141. Ads Contracts Product Filter Map Ads X Contracts Ads With Contracts Ads To Display Asynchronous Dataflow Counters Counters Counters Counter Ads Update (Insert) Application Initialization Counter Read > 50,000 Ads Update (Remove) Epsilon-Invariant Ads Map Configure Invariant Enforce Invariant 121
142. Ads Contracts Product Filter Map Ads X Contracts Ads With Contracts Ads To Display Asynchronous Dataflow 122
143. Counters Counters Counters Counter Ads Update (Insert) Application Initialization 123
144. Counter Read > 50,000 Ads Update (Remove) Epsilon-Invariant Ads Map Configure Invariant Enforce Invariant 124
145. Counter Read > 50,000 Ads Update (Remove) Epsilon-Invariant Ads Map Configure Invariant Enforce Invariant 125 Configure invariants for all of the advertisements.
146. Counter Read > 50,000 Ads Update (Remove) Epsilon-Invariant Ads Map Configure Invariant Enforce Invariant 126 Remove the advertisement from the list.
147. Advertisement Counter • Completely monotonic
 Disabling advertisements and contracts are all modeled through monotonic state growth 127
148. Advertisement Counter • Completely monotonic
 Disabling advertisements and contracts are all modeled through monotonic state growth • Arbitrary distribution
 Use of convergent data structures allows computational graph to be arbitrarily distributed 127
149. Advertisement Counter • Completely monotonic
 Disabling advertisements and contracts are all modeled through monotonic state growth • Arbitrary distribution
 Use of convergent data structures allows computational graph to be arbitrarily distributed • Divergence
 Divergence is a factor of synchronization period, concurrency, and throughput rate 127
150. Programming SEC 1. Eliminate accidental nondeterminism
 (ex. deterministic, modeling non-monotonic operations monotonically) 2. Retain the properties of functional programming
 (ex. confluence, “correct-by-construction” applications) 3. Distributed, and fault-tolerant runtime
 (ex. replication, membership, dissemination) 128
151. Distributed Runtime Anabranch 129 work-in-progress
152. Anabranch • Layered approach
 Cluster membership and state dissemination for large clusters 130
153. Anabranch • Layered approach
 Cluster membership and state dissemination for large clusters • Delta-state synchronization 
 Efficient incremental state dissemination and anti-entropy mechanism [Almeida et al. 2016] 130
154. Anabranch • Layered approach
 Cluster membership and state dissemination for large clusters • Delta-state synchronization 
 Efficient incremental state dissemination and anti-entropy mechanism [Almeida et al. 2016] • Epsilon-invariants
 Lower-bound invariants, configurable at runtime 130
155. Anabranch • Layered approach
 Cluster membership and state dissemination for large clusters • Delta-state synchronization 
 Efficient incremental state dissemination and anti-entropy mechanism [Almeida et al. 2016] • Epsilon-invariants
 Lower-bound invariants, configurable at runtime • Scalable
 Demonstrated high scalability in production Cloud environments 130
156. Anabranch Layered Approach 131
157. Layered Approach 132
158. Layered Approach • Backend
 Configurable persistence layer depending on application. 132
159. Layered Approach • Backend
 Configurable persistence layer depending on application. • Membership
 Configurable membership protocol which can operate in a client-server or peer-to-peer mode [Leitao et al. 2007] 132
160. Layered Approach • Backend
 Configurable persistence layer depending on application. • Membership
 Configurable membership protocol which can operate in a client-server or peer-to-peer mode [Leitao et al. 2007] • Broadcast (via Gossip, Tree, etc.)
 Efficient dissemination of both program state and application state via gossip, broadcast tree, or hybrid mode [Leitao et al. 2007] 132
161. Mobile Phone Distributed Hash Table Application Language Execution KV Store KV Backend Membership Broadcast Layer Client/Server Peer-to-Peer
162. Mobile Phone Distributed Hash Table Application Language Execution KV Store KV Backend Membership Broadcast Layer Client/Server Peer-to-Peer Language and applications.
163. Mobile Phone Distributed Hash Table Application Language Execution KV Store KV Backend Membership Broadcast Layer Client/Server Peer-to-Peer Storage for CRDT state.
164. Mobile Phone Distributed Hash Table Application Language Execution KV Store KV Backend Membership Broadcast Layer Client/Server Peer-to-Peer State dissemination.
165. Anabranch Delta-state CRDTs 137
166. Delta-based Dissemination • Delta-state based CRDTs
 Reduces state transmission for clients 138
167. Delta-based Dissemination • Delta-state based CRDTs
 Reduces state transmission for clients • Operate locally
 Objects are mutated locally; delta’s buffered locally and periodically gossiped 138
168. Delta-based Dissemination • Delta-state based CRDTs
 Reduces state transmission for clients • Operate locally
 Objects are mutated locally; delta’s buffered locally and periodically gossiped • Only fixed number of clients
 Clients resort to full state synchronization when they’ve been partitioned too long 138
169. RC BufferA BufferB
170. RC BufferA BufferB (1, {b}, {}) {1} (1, {b}, {}) (1, {b}, {}) Buffer minimal change representation…
171. RC BufferA BufferB (1, {b}, {}) {1} (1, {b}, {}) (1, {b}, {}) {} (1, {b}, {b}) (1, {b}, {b}) (1, {b}, {b})
172. RC BufferA BufferB (1, {b}, {}) {1} (1, {b}, {}) (1, {b}, {}) {} (1, {b}, {b}) (1, {b}, {b}) (1, {b}, {b}) {2} (1, {b}, {b}) (2, {c}, {}) (2, {c}, {}) (2, {c}, {}) …then, disseminate state in causal order to neighbors.
173. RC BufferA BufferB (1, {b}, {}) {1} (1, {b}, {}) (1, {b}, {}) {} (1, {b}, {b}) (1, {b}, {b}) (1, {b}, {b}) {2} (1, {b}, {b}) (2, {c}, {}) (2, {c}, {}) (2, {c}, {}) {1, 2} (1, {a, b}, {b}) (2, {c}, {}) {1, 2} (1, {a}, {}) (1, {a}, {}) Only ship inflation from incoming state.
174. Anabranch Scalability 144
175. Scalability • 1024+ nodes
 Demonstrated scalability to 1024 nodes in Amazon cloud computing environment 145
176. Scalability • 1024+ nodes
 Demonstrated scalability to 1024 nodes in Amazon cloud computing environment • Modular approach
 Many of the components built and can be operated outside of Lasp to improve scalability of Erlang 145
177. Scalability • 1024+ nodes
 Demonstrated scalability to 1024 nodes in Amazon cloud computing environment • Modular approach
 Many of the components built and can be operated outside of Lasp to improve scalability of Erlang • Automated and repeatable
 Fully automated deployment, scenario execution, log aggregation and archival of experimental results 145
178. Programming SEC 1. Eliminate accidental nondeterminism
 (ex. deterministic, modeling non-monotonic operations monotonically) 2. Retain the properties of functional programming
 (ex. confluence, “correct-by-construction” applications) 3. Distributed, and fault-tolerant runtime
 (ex. replication, membership, dissemination) 146
179. What have we learned? 147
180. We’ve build up from zero synchronization 148
181. We’ve build up from zero synchronization 148 Instead of working to remove synchronization
182. Programming SEC 1. Eliminate accidental nondeterminism
 Convergent Objects: Conflict-Free Replicated Data Types [Shapiro et al. 2011] 149
183. Programming SEC 1. Eliminate accidental nondeterminism
 Convergent Objects: Conflict-Free Replicated Data Types [Shapiro et al. 2011] 2. Retain the properties of functional programming
 Convergent Programs: Lattice Processing
 [Meiklejohn et al. 2015] 149
184. Programming SEC 1. Eliminate accidental nondeterminism
 Convergent Objects: Conflict-Free Replicated Data Types [Shapiro et al. 2011] 2. Retain the properties of functional programming
 Convergent Programs: Lattice Processing
 [Meiklejohn et al. 2015] 3. Distributed, and fault-tolerant runtime
 Distributed Runtime: Anabranch
 [Meiklejohn et al. work-in-progress] 149
185. Key Points • Synchronization is sometimes not possible
 Mobile and “Internet of Things” applications make synchronization for replicated state impractical 150
186. Key Points • Synchronization is sometimes not possible
 Mobile and “Internet of Things” applications make synchronization for replicated state impractical • Apply synchronization only where required
 Global invariants, atomic visibility, etc. 150
187. Key Points • Synchronization is sometimes not possible
 Mobile and “Internet of Things” applications make synchronization for replicated state impractical • Apply synchronization only where required
 Global invariants, atomic visibility, etc. • Holistic approach
 Taking a holistic approach to the design of distributed systems is important for building higher-availability applications 150
188. Artifacts • Lasp
 CRDT based programming model: testbed for Loquat
 http://github.com/lasp-lang/lasp 151
189. Artifacts • Lasp
 CRDT based programming model: testbed for Loquat
 http://github.com/lasp-lang/lasp • Partisan
 TCP-based pluggable membership service offering client/server, static, and HyParView- based protocols
 https://github.com/lasp-lang/partisan 151
190. Artifacts • Lasp
 CRDT based programming model: testbed for Loquat
 http://github.com/lasp-lang/lasp • Partisan
 TCP-based pluggable membership service offering client/server, static, and HyParView- based protocols
 https://github.com/lasp-lang/partisan • Plumtree
 Epidemic broadcast trees for use with Partisan
 https://github.com/lasp-lang/plumtree 151
191. Artifacts • Lasp
 CRDT based programming model: testbed for Loquat
 http://github.com/lasp-lang/lasp • Partisan
 TCP-based pluggable membership service offering client/server, static, and HyParView- based protocols
 https://github.com/lasp-lang/partisan • Plumtree
 Epidemic broadcast trees for use with Partisan
 https://github.com/lasp-lang/plumtree • Sprinter
 Service discovery and deployment for Mesos and Kubernetes
 https://github.com/lasp-lang/sprinter 151
192. Artifacts • Lasp
 CRDT based programming model: testbed for Loquat
 http://github.com/lasp-lang/lasp • Partisan
 TCP-based pluggable membership service offering client/server, static, and HyParView- based protocols
 https://github.com/lasp-lang/partisan • Plumtree
 Epidemic broadcast trees for use with Partisan
 https://github.com/lasp-lang/plumtree • Sprinter
 Service discovery and deployment for Mesos and Kubernetes
 https://github.com/lasp-lang/sprinter • Types
 CRDT implementations for Erlang
 https://github.com/lasp-lang/types 151
193. 152 Christopher Meiklejohn @cmeik http://www.lasp-lang.org Thanks!