Minor fixes to pseudocode and proof
[iotcloud.git] / doc / iotcloud.tex
1 \documentclass[11pt]{article}\r
2 \newcommand{\tuple}[1]{\ensuremath \langle #1 \rangle}\r
3 \usepackage{color}\r
4 \usepackage{amsthm}\r
5 \usepackage{amsmath}\r
6 \usepackage{graphicx}\r
7 \usepackage{mathrsfs}\r
8 \usepackage{algpseudocode}% http://ctan.org/pkg/algorithmicx\r
9 \newtheorem{theorem}{Theorem}\r
10 \newtheorem{prop}{Proposition}\r
11 \newtheorem{lem}{Lemma}\r
12 \newtheorem{defn}{Definition}\r
13 \newcommand{\note}[1]{{\color{red} \bf [[#1]]}}\r
14 \newcommand{\push}[1][1]{\hskip\dimexpr #1\algorithmicindent\relax}\r
15 \begin{document}\r
16 \section{Approach}\r
17 \r
18 \subsection{Keys}\r
19 \r
20 Each device has: user id + password\r
21 \r
22 Server login is:\r
23 hash1(user id), hash1(password)\r
24 \r
25 Symmetric Crypto keys is:\r
26 hash2(user id | password)\r
27 \r
28 Server has finite length queue of entries + max\_entry\_identifier +\r
29 server login key\r
30 \r
31 \subsection{Entry layout}\r
32 Each entry has:\r
33 \begin{enumerate}\r
34 \item Sequence identifier\r
35 \item Random IV (if needed by crypto algorithm)\r
36 \item Encrypted payload\r
37 \end{enumerate}\r
38 \r
39 Payload has:\r
40 \begin{enumerate}\r
41 \item Sequence identifier\r
42 \item Machine id (most probably something like a 64-bit random number \r
43 that is self-generated by client)\r
44 \item HMAC of previous slot\r
45 \item Data entries\r
46 \item HMAC of current slot\r
47 \end{enumerate}\r
48 \r
49 A data entry can be one of these:\r
50 \begin{enumerate}\r
51 \item All or part of a Key-value entry\r
52 \item Slot sequence entry: Machine id + last message identifier \r
53 \newline {The purpose of this is to keep the record of the last slot \r
54 from a certain client if a client's update has to expunge that other \r
55 client's last entry from the queue. This is kept in the slot until \r
56 the entry owner inserts a newer update into the queue.}\r
57 \item Queue state entry: Includes queue size \newline {The purpose \r
58 of this is for the client to tell if the server lies about the number \r
59 of slots in the queue, e.g. if there are 2 queue state entry in the queue, \r
60 e.g. 50 and 70, the client knows that when it sees 50, it should expect \r
61 at most 50 slots in the queue and after it sees 70, it should expect \r
62 50 slots before that queue state entry slot 50 and at most 70 slots. \r
63 The queue state entry slot 70 is counted as slot number 51 in the queue.}\r
64 \item Collision resolution entry: message identifier + machine id of a\r
65 collision winner\r
66 \newline {The purpose of this is to keep keep track of the winner of \r
67 all the collisions until all clients have seen the particular entry.}\r
68 \end{enumerate}\r
69 \r
70 \subsection{Live status}\r
71 \r
72 Live status of entries:\r
73 \begin{enumerate}\r
74 \item Key-Value Entry is dead if either (a) there is a newer key-value pair or (b) it is incomplete.\r
75         \r
76 \item Slot sequence number (of either a message version data\r
77 or user-level data) is dead if there is a newer slot from the same machine.\r
78 \r
79 \item Queue state entry is dead if there is a newer queue state entry.\r
80 {In the case of queue state entries 50 and 70, this means that queue state \r
81 entry 50 is dead and 70 is live. However, not until the number of slots reaches \r
82 70 that queue state entry 50 will be expunged from the queue.}\r
83 \r
84 \item Collision resolution entry is dead if this entry has been seen\r
85 by all clients after a collision happens.\r
86 \end{enumerate}\r
87 \r
88 When data is at the end of the queue ready to expunge, if:\r
89 \begin{enumerate}\r
90 \item The key-value entry is not dead, it must be reinserted at the\r
91 beginning of the queue.\r
92 \r
93 \item If the slot sequence number is not dead, then a message sequence\r
94 entry must be inserted.\r
95 \r
96 \item If the queue state entry is not dead, it must be reinserted at the\r
97 beginning of the queue.\r
98 \end{enumerate}\r
99 \r
100 \r
101 \paragraph{Reads:}\r
102 Client sends a sequence number.  Server replies with either: all data\r
103 entries or all newer data entries.\r
104 \r
105 \paragraph{Writes:}\r
106 Client sends slot, server verifies that sequence number is valid,\r
107 checks entry hash, and replies with an accept message if all checks\r
108 pass.  On success, client updates its sequence number.  On failure,\r
109 server sends updates slots to client and client validates those slots.\r
110 \r
111 \paragraph{Local state on each client:}\r
112 A list of machines and the corresponding latest sequence numbers.\r
113 \r
114 \paragraph{Validation procedure on client:}\r
115 \begin{enumerate}\r
116 \item Decrypt each new slot in order.\r
117 \item For each slot:\r
118     (a) check its HMAC, and\r
119     (b) check that the previous entry HMAC field matches the previous\r
120     entry.\r
121 \item Check that the last-message entry for our machine matches the stored HMAC of our last message sent.\r
122 \item For all other machines, check that the latest sequence number is\r
123 at least as large (never goes backwards).\r
124 \item That the queue has a current queue state entry.\r
125 \item That the number of entries received is consistent with the size\r
126 specified in the queue state entry.\r
127 \end{enumerate}\r
128 \r
129 Key-value entries can span multiple slots.  They aren't valid until\r
130 they are complete.\r
131 \r
132 \subsection{Resizing Queue}\r
133 Client can make a request to resize the queue. This is done as a write that combines:\r
134   (a) a slot with the message, and (b) a request to the server. The queue can only be expanded, never contracted; attempting to decrease the size of the queue will cause future clients to throw an error.\r
135 \r
136 \subsection{Server Algorithm}\r
137 $s \in SN$ is a sequence number set\\\r
138 $sv \in SV$ is a slot's value\\\r
139 $slot_s = \tuple{s, sv} \in SL \subseteq SN \times SV$ \\ \\\r
140 \textbf{State} \\\r
141 \textit{SL = set of live slots on server} \\\r
142 \textit{max = maximum number of slots (input only for resize message)} \\\r
143 \textit{n = number of slots} \\ \\\r
144 \textbf{Helper Function} \\\r
145 $MaxSlot(SL_s)= \tuple{s, sv} \mid \tuple{s, sv}\r
146 \in SL_s \wedge \forall \tuple{s_s, sv_s} \in SL_s, s \geq s_s$ \\\r
147 $MinSlot(SL_s)= \tuple{s, sv} \mid \tuple{s, sv} \r
148 \in SL_s \wedge \forall \tuple{s_s, sv_s} \in SL_s, s \leq s_s$ \\\r
149 $SeqN(\tuple{s, sv})=s$ \\\r
150 $SlotVal(\tuple{s, sv})=sv$ \\\r
151 \r
152 \begin{algorithmic}[1]\r
153 \Function{GetSlot}{$s_g$}\r
154 \State \Return{$\{\tuple{s, sv} \in SL \mid s \geq s_g\}$}\r
155 \EndFunction\r
156 \end{algorithmic}\r
157 \r
158 \begin{algorithmic}[1]\r
159 \Function{PutSlot}{$s_p,sv_p,max'$}\r
160 \If{$(max' \neq \emptyset)$}  \Comment{Resize}\r
161 \State $max \gets max'$\r
162 \EndIf\r
163 \State $\tuple{s_n,sv_n} \gets MaxSlot(SL)$\Comment{Last sv}\r
164 \State $s_n \gets SeqN(\tuple{s_n,sv_n})$\r
165 \If{$(s_p = s_n + 1)$}\r
166         \If{$n = max$}\r
167         \State $\tuple{s_m,sv_m} \gets MinSlot(SL)$\Comment{First sv}\r
168                 \State $SL \gets SL - \{\tuple{s_m,sv_m}\}$\r
169         \Else \Comment{$n < max$}\r
170                 \State $n \gets n + 1$\r
171         \EndIf\r
172     \State $SL \gets SL \cup \{\tuple{s_p,sv_p}\}$\r
173         \State \Return{$(true,\emptyset)$}\r
174 \Else\r
175         \State \Return{$(false,\{\tuple{s,sv}\in SL \mid \r
176     s \geq s_p\})$}\r
177 \EndIf\r
178 \EndFunction\r
179 \end{algorithmic}\r
180 \r
181 \subsection{Client Algorithm}\r
182 \subsubsection{Reading Slots}\r
183 \textbf{Data Entry} \\\r
184 $de$ is a data entry \\\r
185 $k$ is key of entry \\\r
186 $v$ is value of entry \\\r
187 $kv$ is a key-value entry $\tuple{k,v}$, $kv \in DE$ \\\r
188 $ss$ is a slot sequence entry $\tuple{id,s_{last}}$, \r
189 id + last s of a machine, $ss \in DE$ \\\r
190 $qs$ is a queue state entry (contains $max$ size of queue), $qs \in DE$ \\\r
191 $cr$ is a collision resolution entry $\tuple{s_{col},id_{col}}$, \r
192 s + id of a machine that wins a collision, $cr \in DE$ \\\r
193 $DE$ is a set of all data entries, possibly of different types, in a single message \\\r
194 $s \in SN$ is a sequence number set \\\r
195 $id$ is a machine ID\\\r
196 $hmac_p$ is the HMAC value of the previous slot \\\r
197 $hmac_c$ is the HMAC value of the current slot \\\r
198 $Dat_s = \tuple{s,id,hmac_p,DE,hmac_c}$ \\\r
199 $sv_s = \tuple{s, E(Dat_s)} = \r
200 \tuple{s, E(\tuple{s,id,hmac_p,DE,hmac_c})}$ \\ \\\r
201 \r
202 \textbf{States} \\\r
203 \textit{$id_{self}$ = machine Id of this client} \\\r
204 \textit{$max_g$ = maximum number of slots (initially $max_g > 0$)} \\\r
205 \textit{m = number of slots stored on client (initially $m = 0$)} \\\r
206 \textit{$sl_{last}$ = info of last slot in queue = \r
207         $\tuple{s_{last},sv_{last},id_{last}}$ (initially $\emptyset$)} \\\r
208 \textit{DT = set of $\tuple{k,v}$ on client} \\\r
209 \textit{MS = associative array of $\tuple{id, s_{last}}$ of all clients on client \r
210 (initially empty)} \\\r
211 \textit{$MS_g$ = set MS to save all $\tuple{id, s_{last}}$ pairs while\r
212 traversing DT after a request to server (initially empty)} \\\r
213 \textit{SK = Secret Key} \\\r
214 \textit{$SM$ = associative array of $\tuple{s, id}$ of all slots in a previous read\r
215 (initially empty)} \\ \\\r
216 \r
217 \textbf{Helper Functions} \\\r
218 $MaxSlot(SL_s)= \tuple{s, sv}$ \textit{such that} $\tuple{s, sv}\r
219 \in SL_s \wedge \forall \tuple{s_s, sv_s} \in SL_s, s \geq s_s$ \\\r
220 $MinSlot(SL_s)= \tuple{s, sv}$ \textit{such that} $\tuple{s, sv} \r
221 \in SL_s \wedge \forall \tuple{s_s, sv_s} \in SL_s, s \leq s_s$ \\\r
222 $Slot(SL_s,s_s)= \tuple{s, sv}$ \textit{such that} $\tuple{s, sv} \r
223 \in SL_s \wedge \forall \tuple{s_s, sv_s} \in SL_s, s = s_s$ \\\r
224 $SeqN(\tuple{s, sv})=s$ \\\r
225 $SlotVal(\tuple{s, sv})=sv$ \\\r
226 $CreateLastSL(s,sv,id)=\tuple{s,sv,id}=sl_{last}$ \\\r
227 $Decrypt(SK_s,sv_s)=Dat_s=\tuple{s,id,hmac_p,DE,hmac_c}$ \\\r
228 $GetSeqN(Dat_s = \tuple{s,id,hmac_p,DE,hmac_c})=s$ \\\r
229 $GetMacId(Dat_s = \tuple{s,id,hmac_p,DE,hmac_c})=id$ \\\r
230 $GetPrevHmac(Dat_s = \tuple{s,id,hmac_p,DE,hmac_c})=hmac_p$ \\\r
231 $GetCurrHmac(Dat_s = \tuple{s,id,hmac_p,DE,hmac_c})=hmac_c$ \\\r
232 $GetDatEnt(Dat_s = \tuple{s,id,hmac_p,DE,hmac_c})=DE$ \\\r
233 $GetKV($key-value data entry$)=\tuple{k_s,v_s}$ \\\r
234 $GetSS($slot-sequence data entry$)=\tuple{id,s_{last}}$ \\\r
235 $GetQS($queue-state data entry$)=qs_s$ \\\r
236 $GetCR($collision-resolution data entry$)=\tuple{s_s,id_s}$ \\\r
237 $GetS(\tuple{s, id})=s$ \\\r
238 $GetId(\tuple{s, id})=id$ \\\r
239 $GetKey(\tuple{k, v})=k$ \\\r
240 $GetVal(\tuple{k, v})=v$ \\\r
241 $GetKeyVal(DT_s,k_s)= \tuple{k, v}$ \textit{such that} $\tuple{k, v} \r
242 \in DT_s \wedge \forall \tuple{k_s, v_s} \in DT_s, k = k_s$ \\\r
243 $MaxLastSeqN(MS_s)= s_{last}$ \textit{such that} $\tuple{id, s_{last}} \in MS_s \r
244 \wedge \forall \tuple{id_s, s_{s_{last}}} \in MS_s, s_{last} \geq s_{s_{last}}$ \\\r
245 $MinLastSeqN(MS_s)= s_{last}$ \textit{such that} $\tuple{id, s_{last}} \in MS_s \r
246 \wedge \forall \tuple{id_s, s_{s_{last}}} \in MS_s, s_{last} \leq s_{s_{last}}$ \\\r
247 \r
248 \begin{algorithmic}[1]\r
249 \Procedure{Error}{$msg$}\r
250 \State $Print(msg)$\r
251 \State $Halt()$\r
252 \EndProcedure\r
253 \end{algorithmic}\r
254 \r
255 \begin{algorithmic}[1]\r
256 \Function{ValidHmac}{$DE_s,SK_s,hmac_{stored}$}\r
257 \State $hmac_{computed} \gets Hmac(DE_s,SK_s)$\r
258 \State \Return {$hmac_{stored} = hmac_{computed}$}\r
259 \EndFunction\r
260 \end{algorithmic}\r
261 \r
262 \begin{algorithmic}[1]\r
263 \Function{ValidPrevHmac}{$DE_s,hmac_{p_s},hmac_{p_{sto}}$}\r
264 \If{$hmac_{p_s} = \emptyset$}\Comment{First slot - no previous HMAC}\r
265         \State \Return $true$\r
266 \Else\r
267         \State \Return {$hmac_{p_{sto}} = hmac_{p_s}$}\r
268 \EndIf\r
269 \EndFunction\r
270 \end{algorithmic}\r
271 \r
272 \note{So if a slot has a null previous hmac, everything is fine?  What if it isn't the first slot?}\r
273 \r
274 \begin{algorithmic}[1]\r
275 \Function{GetQueSta}{$Dat_s$}\r
276 \State $DE_s \gets GetDatEnt(DE_s)$\r
277 \State $de_{qs} \gets de_s$ \textit{such that} $de_s \in DE_s, \r
278         de_s \in D \land de_s = qs$\r
279 \If{$de_{qs} \neq \emptyset$}\r
280         \State $qs_{ret} \gets GetQS(de_{qs})$\r
281 \Else\r
282         \State $qs_{ret} \gets \emptyset$\r
283 \EndIf\r
284 \State \Return{$qs_{ret}$}\r
285 \EndFunction\r
286 \end{algorithmic}\r
287 \r
288 \begin{algorithmic}[1]\r
289 \Function{GetSlotSeq}{$Dat_s$}\r
290 \State $DE_s \gets GetDatEnt(Dat_s)$\r
291 \State $de_{ss} \gets de_s$ \textit{such that} $de_s \in DE_s, \r
292         de_s \in D \land de_s = ss$\r
293 \If{$de_{ss} \neq \emptyset$}\r
294         \State $\tuple{id_{ret},s_{last_{ret}}} \gets GetSS(de_{ss})$\r
295 \Else\r
296         \State $\tuple{id_{ret},s_{last_{ret}}} \gets \emptyset$\r
297 \EndIf\r
298 \State \Return{$\tuple{id_{ret},s_{last_{ret}}}$}\r
299 \EndFunction\r
300 \end{algorithmic}\r
301 \r
302 \begin{algorithmic}[1]\r
303 \Function{GetColRes}{$Dat_s$}\Comment{At most 2 $cr$ entries in a slot}\r
304 \State $DE_s \gets GetDatEnt(Dat_s)$\r
305 \State $de_{cr} \gets de_s$ \textit{such that} $de_s \in DE_s, \r
306         de_s \in D \land de_s = cr$\r
307 \If{$de_{cr} \neq \emptyset$}\r
308         \State $\tuple{s_{ret},id_{ret}} \gets GetCR(de_{cr})$\r
309 \Else\r
310         \State $\tuple{s_{ret},id_{ret}} \r
311         \gets \emptyset$\r
312 \EndIf\r
313 \State $de_{r_{cr}} \gets de_s$ \textit{such that} $de_s \in DE_s, \r
314         de_s \in D \land de_s = cr \land de_s \neq de_{cr}$\r
315 \If{$de_{r_{cr}} \neq \emptyset$}\r
316         \State $\tuple{s_{r_{ret}},id_{r_{ret}}} \gets GetCR(de_{r_{cr}})$\r
317 \Else\r
318         \State $\tuple{s_{r_{ret}},id_{r_{ret}}} \r
319         \gets \emptyset$\r
320 \EndIf\r
321 \State \Return{$\{\tuple{s_{ret},id_{ret}},\tuple{s_{r_{ret}},id_{r_{ret}}}\}$}\r
322 \EndFunction\r
323 \end{algorithmic}\r
324 \r
325 \begin{algorithmic}[1]\r
326 \Function{UpdateLastSeqN}{$id_s,s_s,MS_s$}\r
327 \State $s_t \gets MS_s[id_s]$\r
328 \If{$s_t = \emptyset$}\r
329         \State $MS_s[id_s] = s_s$  \Comment{First occurrence}\r
330 \Else\r
331         \State $MS_S[id_s] \gets max(s_t, s_s)$\r
332 \EndIf\r
333 \State \Return{$MS_s$}\r
334 \EndFunction\r
335 \end{algorithmic}\r
336 \r
337 \begin{algorithmic}[1]\r
338 \Procedure{CheckLastSeqN}{$MS_s,MS_t$}\Comment{Check $MS_t$ based on the newer $MS_s$}\r
339 \For {$\tuple{id, s_t}$ in $MS_t$}\r
340         \State $s_s \gets MS_s[id]$\r
341         \If{$s_s = \emptyset$}\r
342         \Call{Error}{'No $s$ for machine $id$'}\r
343         \ElsIf{$id = id_{self}$ and $s_s \neq s_t$}\r
344                         \State \Call{Error}{'Invalid last $s$ for this machine'}\r
345         \ElsIf{$id \neq id_{self}$ and $s_{s_{last}} < s_{t_{last}}$}\r
346         \State \Call{Error}{'Invalid last $s$ for machine $id$'}\r
347     \Else\r
348                 \State $MS_t[id] \gets s_s$\r
349         \EndIf\r
350 \EndFor\r
351 \EndProcedure\r
352 \end{algorithmic}\r
353 \r
354 \begin{algorithmic}[1]\r
355 \Procedure{CheckCollision}{$MS_s,SM_s,\tuple{s_s,id_s}$}\r
356 \If{$\tuple{s_s,id_s} \neq \emptyset$}\r
357         \State $s_s \gets GetS(\tuple{s_s,id_s})$\r
358         \State $id_s \gets GetId(\tuple{s_s,id_s})$\r
359         \State $s_{s_{last}} \gets GetLastSeqN(MS_s,id_s)$\r
360         \If{$s_{s_{last}} < s_s$}\r
361                 \State $\Call{CheckColRes}{SM_s,\tuple{s_s,id_s}}$\r
362         \EndIf\r
363 \EndIf\r
364 \EndProcedure\r
365 \end{algorithmic}\r
366 \r
367 \begin{algorithmic}[1]\r
368 \Procedure{CheckColRes}{$SM_s,\tuple{s_t,id_t}$}\Comment{Check $id_s$ in $SM_s$}\r
369 \State $id_s \gets SM_s[s_t]$\r
370 \If{$id_s \neq id_t$}\r
371         \State \Call{Error}{'Invalid $id_s$ for this slot update'}\r
372 \EndIf\r
373 \EndProcedure\r
374 \end{algorithmic}\r
375 \r
376 \begin{algorithmic}[1]\r
377 \Function{StoreLastSlot}{$MS_s,sl_l,s_s,sv_s,id_s$}\r
378 \State $s_{min} \gets MinLastSeqN(MS_s)$\r
379 \If{$s_{min} \neq \emptyset \land s_{min} = s_s$}\Comment{$MS$ initially empty}\r
380         \State $sl_l \gets CreateLastSL(s_s,sv_s,id_s)$\r
381 \EndIf\r
382 \State \Return{$sl_l$}\r
383 \EndFunction\r
384 \end{algorithmic}\r
385 \r
386 \begin{algorithmic}[1]\r
387 \Function{UpdateDT}{$DT_s,Dat_s$}\r
388 \State $DE_s \gets GetDatEnt(Dat_s)$\r
389 \ForAll{$de_s \in DE_s$}\r
390         \If{$de_s$ \textit{such that} $de_s \in D \land de_s = kv$}\r
391                 \State $\tuple{k_s,v_s} \gets GetKV(de_s)$\r
392                 \State $\tuple{k_s,v_t} \gets GetKeyVal(DT_s,k_s)$\r
393                 \If{$\tuple{k_s,v_t} = \emptyset$}\r
394                         \State $DT_s \gets DT_s \cup \{\tuple{k_s,v_s}\}$\r
395                 \Else\r
396                 \State $DT_s \gets (DT_s - \{\tuple{k_s,v_t}\}) \cup \r
397                         \{\tuple{k_s,v_s}\}$\r
398                 \EndIf\r
399     \EndIf\r
400 \EndFor\r
401 \State \Return{$DT_s$}\r
402 \EndFunction\r
403 \end{algorithmic}\r
404 \r
405 \begin{algorithmic}[1]\r
406 \Procedure{ProcessSL}{$SL_g$}\r
407 \State $MS_g \gets \emptyset$\r
408 \State $SM_{curr} \gets \emptyset$\r
409 \State $\tuple{s_{g_{max}},sv_{g_{max}}} \gets MaxSlot(SL_g)$\r
410 \State $s_{g_{max}} \gets SeqN(\tuple{s_{g_{max}},sv_{g_{max}}})$\r
411 \State $\tuple{s_{g_{min}},sv_{g_{min}}} \gets MinSlot(SL_g)$\r
412 \State $s_{g_{min}} \gets SeqN(\tuple{s_{g_{min}},sv_{g_{min}}})$\r
413 \For{$s_g \gets s_{g_{min}}$ \textbf{to} $s_{g_{max}}$}\Comment{Process slots \r
414         in $SL_g$ in order}\r
415         \State $\tuple{s_g,sv_g} \gets Slot(SL_g,s_g)$\r
416         \State $SM_{curr} \gets SM_{curr} \cup \{\tuple{s_g,sv_g}\}$\r
417         \State $Dat_g \gets Decrypt(SK,sv_g)$\r
418         \State $s_{g_{in}} \gets GetSeqN(Dat_g)$\r
419     \If{$s_g \neq s_{g_{in}}$}\r
420                 \State \Call{Error}{'Invalid sequence number'}\r
421         \EndIf\r
422         \State $DE_g \gets GetDatEnt(Dat_g)$\r
423         \State $hmac_{p_{stored}} \gets GetPrevHmac(Dat_g)$\r
424         \If{$\neg \Call{ValidPrevHmac}{DE_g,hmac_{p_g},hmac_{p_{stored}}}$}\r
425                 \State \Call{Error}{'Invalid previous HMAC value'}\r
426         \EndIf\r
427         \State $hmac_{c_g} \gets GetCurrHmac(Dat_g)$\r
428         \If{$\neg \Call{ValidHmac}{DE_g,SK,hmac_{c_g}}$}\r
429                 \State \Call{Error}{'Invalid current HMAC value'}\r
430         \EndIf\r
431         \State $hmac_{p_g} \gets Hmac(DE_g,SK)$\Comment{Update $hmac_{p_g}$ for next check}\r
432         \State $qs_g \gets \Call{GetQueSta}{Dat_g}$\Comment{Handle qs}\r
433         \If{$qs_g \neq \emptyset \land qs_g > max_g$}\r
434                 \State $max_g \gets qs_g$\r
435         \EndIf\r
436     %Check for last s in Dat\r
437         \State $id_g \gets GetMacId(Dat_g)$\Comment{Handle last s}\r
438         \State $MS_g \gets \Call{UpdateLastSeqN}{id_g,s_g,MS_g}$\r
439     %Check for last s in DE in Dat\r
440     \State $\tuple{id_d,s_{d_{last}}} \gets \Call{GetSlotSeq}{Dat_g}$\Comment{Handle ss}\r
441         \If{$\tuple{id_d,s_{d_{last}}} \neq \emptyset$}\r
442         \State $MS_g \gets \Call{UpdateLastSeqN}{id_d,s_{d_{last}},MS_g}$\r
443         \EndIf\r
444         \State $\{\tuple{s_e,id_e},\tuple{s_f,id_f}\} \gets \r
445         \Call{GetColRes}{Dat_g}$\Comment{Handle cr}\r
446         \State $\Call{CheckCollision}{MS,SM,\tuple{s_e,id_e}}$\Comment{From normal slot}\r
447         \State $\Call{CheckCollision}{MS,SM,\tuple{s_f,id_f}}$\Comment{From reinsertion}\r
448         \State $sl_{last} \gets \Call{StoreLastSlot}{MS,sl_{last},s_g,sv_g,id_g}$\r
449         \State $DT \gets \Call{UpdateDT}{DT,Dat_g}$\r
450 \EndFor\r
451 \State $SM \gets SM_{curr}$\r
452 \If{$m + |SL_g| \leq max_g$}\Comment{Check actual size against $max_g$}\r
453         \State $m \gets m + |SL_g|$\r
454 \Else\r
455         \State \Call{Error}{'Actual queue size exceeds $max_g$'}\r
456 \EndIf\r
457 \State $\Call{CheckLastSeqN}{MS_g,MS}$\r
458 \EndProcedure\r
459 \end{algorithmic}\r
460 \r
461 \begin{algorithmic}[1]\r
462 \Procedure{GetKVPairs}{}\r
463 \State $s_g \gets GetLastSeqN(MS,id_{self}) + 1$\r
464 \State $SL_c \gets \Call{GetSlot}{s_g}$\r
465 \State $\Call{ProcessSL}{SL_c}$\Comment{Process slots and update DT}\r
466 \EndProcedure\r
467 \end{algorithmic}\r
468 \r
469 \begin{algorithmic}[1]\r
470 \Function{GetValFromKey}{$k_g$}\r
471 \State $\tuple{k_s,v_s} \gets \tuple{k,v}$ \textit{such that} $\tuple{k,v} \r
472         \in DT \land k = k_g$\r
473 \State \Return{$v_s$}\r
474 \EndFunction\r
475 \end{algorithmic}\r
476 \r
477 \subsubsection{Writing Slots}\r
478 \textbf{Data Entry} \\\r
479 $k$ is key of entry \\\r
480 $v$ is value of entry \\\r
481 $kv$ is a key-value entry $\tuple{k,v}$\\\r
482 $D = \{kv,ss,qs,cr\}$ \\\r
483 $DE = \{de \mid de \in D\}$ \\\r
484 $Dat_s = \tuple{s,id,hmac_p,DE,hmac_c}$ \\\r
485 $sv_s = \tuple{s, E(Dat_s)} = \r
486 \tuple{s, E(\tuple{s,id,hmac_p,DE,hmac_c})}$ \\ \\\r
487 \textbf{States} \\\r
488 \textit{$cp$ = data entry $DE$ maximum size/capacity} \\\r
489 \textit{$cr_p$ = saved cr entry $\tuple{s,id}$ on client if there is a collision\r
490 (sent in the following slot)} \\\r
491 \textit{$cr_{p_{last}}$ = saved cr entry $\tuple{s,id}$ on client if there is a \r
492 collision in reinserting the last slot (sent in the following slot)} \\\r
493 \textit{$ck_p$ = counter of $kv \in KV$ for putting pairs (initially 0)} \\\r
494 \textit{$ck_g$ = counter of $kv \in KV$ for getting pairs (initially 0)} \\\r
495 \textit{$hmac_{c_p}$ = the HMAC value of the current slot} \\\r
496 \textit{$hmac_{p_p}$ = the HMAC value of the previous slot \r
497 ($hmac_{p_p} = \emptyset$ for the first slot)} \\\r
498 \textit{$id_{self}$ = machine Id of this client} \\\r
499 \textit{$sl_{last}$ = info of last slot in queue = \r
500         $\tuple{s_{last},sv_{last},id_{last}}$ (initially $\emptyset$)} \\\r
501 \textit{$th_p$ = threshold number of dead slots for a resize to happen} \\\r
502 \textit{$m'_p$ = offset added to $max$ for resize} \\\r
503 \textit{$KV$ = set of $\tuple{ck, \tuple{k,v}}$ of kv entries on client} \\\r
504 \textit{$SL_p$ = set of returned slots on client} \\\r
505 \textit{SK = Secret Key} \\ \\\r
506 \textbf{Helper Functions} \\\r
507 $CreateDat(s,id,hmac_p,DE,hmac_c)=Dat_s=\tuple{s,id,hmac_p,DE,hmac_c}$ \\\r
508 $CreateCR(s,id)=\tuple{s,id}$ \\\r
509 $CreateQS(max')=qs$ \\\r
510 $CreateSS(id,s_{last})=\tuple{id,s_{last}}$ \\\r
511 $Encrypt(Dat_s,SK_s)=sv_s$ \\\r
512 $GetStatus(\tuple{status,SL})=status$ \\\r
513 $GetSL(\tuple{status,SL})=SL$ \\\r
514 $GetLastS(sl = \tuple{s,sv,id})=s$ \\\r
515 $GetSV(sl = \tuple{s,sv,id})=sv$ \\\r
516 $GetID(sl = \tuple{s,sv,id})=id$ \\\r
517 $GetColSeqN(SL_s,s_s)= \tuple{s, sv}$ \textit{such that} $\tuple{s, sv}\r
518 \in SL_s \wedge \forall \tuple{s_s, sv_s} \in SL_s, s = s_s$ \\\r
519 $GetKV(KV_s,k_s)= \tuple{ck,\tuple{k, v}}$ \textit{such that} \r
520 $\tuple{ck,\tuple{k, v}} \in KV_s \wedge\r
521 \forall \tuple{ck_s,\tuple{k_s, v_s}} \in KV_s, k = k_s$ \\\r
522 \r
523 \begin{algorithmic}[1]\r
524 \Function{PutKVPair}{$KV_s,\tuple{k_s,v_s}$}\r
525 \State $\tuple{ck_s,\tuple{k_s,v_t}} \gets GetKV(KV_s,k_s)$\r
526 \If{$\tuple{ck_s,\tuple{k_s,v_t}} = \emptyset$}\r
527         \State $KV_s \gets KV_s \cup \{\tuple{ck_p, \tuple{k_s,v_s}}\}$\r
528         \State $ck_p \gets ck_p + 1$\r
529 \Else\r
530         \State $KV_s \gets (KV_s - \{\tuple{ck_s, \tuple{k_s,v_t}}\}) \cup \r
531         \{\tuple{ck_s, \tuple{k_s,v_s}}\}$\r
532 \EndIf\r
533 \State \Return{$KV_s$}\r
534 \EndFunction\r
535 \end{algorithmic}\r
536 \r
537 \begin{algorithmic}[1]\r
538 \Function{CheckResize}{$MS_s,th_s,max'_t,m'_s$}\r
539 \State $s_{last_{min}} \gets MinLastSeqN(MS_s)$\r
540 \State $s_{last_{max}} \gets MaxLastSeqN(MS_s)$\r
541 \State $n_{live} \gets s_{last_{max}} - s_{last_{min}}$\Comment{Number of live slots}\r
542 \State $n_{dead} \gets max'_t - n_{live}$\r
543 \If{$n_{dead} \leq th_s$}\r
544         \State $max'_s \gets max'_t + m'_s$\r
545 \Else\r
546         \State $max'_s \gets \emptyset$\r
547 \EndIf\r
548 \State \Return{$max'_s$}\r
549 \EndFunction\r
550 \end{algorithmic}\r
551 \r
552 \begin{algorithmic}[1]\r
553 \Function{CheckNeedSS}{$MS_s,max'_t$}\Comment{Check if $ss$ is needed}\r
554 \State $s_{last_{min}} \gets MinLastSeqN(MS_s)$\r
555 \State $s_{last_{max}} \gets MaxLastSeqN(MS_s)$\r
556 \State $n_{live} \gets s_{last_{max}} - s_{last_{min}}$\Comment{Number of live slots}\r
557 \State $n_{dead} \gets max'_t - n_{live}$\r
558 \State \Return {$n_{dead} = 0$}\r
559 \EndFunction\r
560 \end{algorithmic}\r
561 \r
562 \begin{algorithmic}[1]\r
563 \Function{HandleCollision}{$\tuple{stat_s,SL_s}$}\r
564 \State $stat_s \gets GetStatus(\tuple{stat_s,SL_s})$\r
565 \State $SL_s \gets GetSL(\tuple{stat_s,SL_s})$\r
566 \If{$\neg stat_s$}\Comment{Handle collision}\r
567         \State $\tuple{s_{col},sv_{col}} \gets GetColSeqN(SL_s,s_s)$\r
568         \State $s_{col} \gets SeqN(\tuple{s_{col},sv_{col}})$\r
569         \State $sv_{col} \gets SlotVal(\tuple{s_{col},sv_{col}})$\r
570         \State $Dat_{col} \gets Decrypt(SK,sv_{col})$\r
571         \State $id_{col} \gets GetMacId(Dat_{col})$\r
572         \State $\tuple{s_{col},id_{col}} \gets CreateCR(s_{col},id_{col})$\r
573         \State $cr_s \gets \tuple{s_{col},id_{col}}$\r
574 \Else\r
575         \State $cr_s \gets \emptyset$\r
576 \EndIf\r
577 \State $\Call{ProcessSL}{SL_s}$\r
578 \State \Return{$cr_s$}\r
579 \EndFunction\r
580 \end{algorithmic}\r
581 \r
582 \begin{algorithmic}[1]\r
583 \Function{ReinsertLastSlot}{$need_s,sl_{s_{last}},max'_s$}\r
584 \If{$need_s$}\r
585         \State $s_s \gets GetLastS(sl_{s_{last}})$\r
586         \State $sv_s \gets GetSV(sl_{s_{last}})$\r
587         \State $\tuple{stat_s,SL_s} \gets \Call{PutSlot}{s_s,sv_s,max'_s}$\r
588         \State $cr_s \gets \Call{HandleCollision}{\tuple{stat_s,SL_s}}$\r
589 \EndIf\r
590 \State \Return{$cr_s$}\r
591 \EndFunction\r
592 \end{algorithmic}\r
593 \note{Shouldn't this function do something pretty sophisticated about seeing what data we actually need to keep from the last slot and not just insert the entire thing?}\r
594 \r
595 \note{Probably best to just not call this function is $need_s$ is false and not pass in such parameters.  It makes it harder to read.}\r
596 \r
597 \r
598 \begin{algorithmic}[1]\r
599 \Function{GetDEPairs}{$KV_s,max'_s,need_s,sl_s$}\r
600 \State $DE_{ret} \gets \emptyset$\r
601 \State $cp_s \gets cp$\r
602 \If{$cr_p \neq \emptyset$}\Comment{Check and insert a $cr$}\r
603         \State $DE_{ret} \gets DE_{ret} \cup cr_p$\r
604         \State $cp_s \gets cp_s - 1$\r
605 \EndIf\r
606 \If{$cr_{p_{last}} \neq \emptyset$}\Comment{Check and insert a $cr$}\r
607         \State $DE_{ret} \gets DE_{ret} \cup cr_{p_{last}}$\r
608         \State $cp_s \gets cp_s - 1$\r
609 \EndIf\r
610 \If{$max'_s \neq \emptyset$}\Comment{Check and insert a $qs$}\r
611         \State $qs_s \gets max'_s$\r
612         \State $DE_{ret} \gets DE_{ret} \cup qs_s$\r
613         \State $cp_s \gets cp_s - 1$\r
614 \EndIf\r
615 \If{$need_s$}\Comment{Check and insert a $ss$}\r
616         \State $id_s \gets GetID(sl_s)$\r
617         \State $s_{s_{last}} \gets GetLastS(sl_s)$\r
618         \State $ss_s \gets CreateSS(id_s,s_{s_{last}})$\r
619         \State $DE_{ret} \gets DE_{ret} \cup ss_s$\r
620         \State $cp_s \gets cp_s - 1$\r
621 \EndIf\r
622 \If{$|KV_s| \leq cp$}\Comment{$KV$ set can extend multiple slots}\r
623         \State $DE_{ret} \gets DE_{ret} \cup\r
624         \{\tuple{k_s,v_s} \mid \tuple{ck_s,\tuple{k_s,v_s}} \in KV_s\}$\r
625 \Else\r
626         \State $DE_{ret} \gets DE_{ret} \cup\r
627         \{\tuple{k_s,v_s} \mid \tuple{ck_s,\tuple{k_s,v_s}} \in KV_s,\r
628                 ck_g \leq ck_s < ck_g + cp_s\}$\r
629         \If{$|DE_{ret}| = cp$}\r
630                 \State $ck_g \gets ck_g + cp_s$\Comment{Middle of KV set}\r
631         \Else\r
632                 \State $ck_g \gets 0$\Comment{End of KV set}\r
633         \EndIf\r
634 \EndIf\r
635 \State \Return{$DE_{ret}$}\r
636 \EndFunction\r
637 \end{algorithmic}\r
638 \r
639 \begin{algorithmic}[1]\r
640 \Procedure{PutDataEntries}{$th_p,m'_p$}\r
641 \State $s_p \gets MaxLastSeqN(MS)$\r
642 \State $max'_p \gets \Call{CheckResize}{MS,th_p,max'_g,m'_p}$\r
643 \State $need_p \gets \Call{CheckNeedSS}{MS,max'_g}$\r
644 \State $DE_p \gets \Call{GetDEPairs}{KV,max'_p,need_p,sl_{last}}$\r
645 \State $hmac_{c_p} \gets Hmac(DE_p,SK)$\r
646 \State $Dat_p \gets CreateDat(s_p,id_{self},hmac_{p_p},DE_p,hmac_{c_p})$\r
647 \State $hmac_{p_p} \gets hmac_{c_p}$\r
648 \State $sv_p \gets Encrypt(Dat_p,SK)$\r
649 \State $\tuple{stat_p,SL_p} \gets \Call{PutSlot}{s_p,sv_p,max'_p}$\r
650 \State $cr_p \gets \Call{HandleCollision}{\tuple{stat_p,SL_p}}$\r
651 \State $cr_{p_{last}} \gets \Call{ReinsertLastSlot}{need_p,sl_{last},max'_p}$\r
652 \EndProcedure\r
653 \end{algorithmic}\r
654 \r
655 \note{Lots of problems with PutDataEntries: (1) What happens if lose network connectivity after adding the key value pair, but before reinserting the last slot?  You probably need to create space first and then insert your data entry...  (2) What if reinsertlastslot kicks something else important out?  What if the server rejects our update because it is out of date?  At the very least, any putdataentries function w/o a loop is wrong!}\r
656 \r
657 \note{General comments...  Work on structuring things to improve\r
658   readability...  This include names of functions/variables, how\r
659   things are partitioned into functions, adding useful comments,...}\r
660 \r
661 \r
662 \subsection{Definitions for Formal Guarantees}\r
663 \r
664 \begin{enumerate}\r
665 \item Equality: Two messages $t$ and $u$ are equal if their sequence numbers, senders, and contents are exactly the same.\r
666 \item Message: A message $t$, is the tuple $t = (i(t), s(t), contents(t))$ containing the sequence number, machine ID of the sender, and contents of $t$ respectively.\r
667 \item Parent: A parent of a message $t$ is the message $A(t)$, unique by the correctness of HMACs, such that $HMAC_C(t) = HMAC_P(A(t))$.\r
668 \item Partial message sequence: A partial message sequence is a sequence of messages, no two with the same sequence number, that can be divided into disjoint chains, where a chain of messages with length $n \ge 1$ is a message sequence $(t_i, t_{i+1}, ..., t_{i+n-1})$ such that for every index $i < k \le i+n-1$, $t_k$ has sequence number $k$ and is the parent of $t_{k-1}$.\r
669 \item Total message sequence: A total message sequence $T$ with length $n$ is a chain of messages that starts at $i = 1$.\r
670 \item Path: The path of a message $t$ is the total message sequence whose last message is $t$.\r
671 \item Consistency: A partial message sequence $P$ is consistent with a total message sequence $T$ of length $n$ if for every message $p \in P$ with $i(p) < n$, $T_{i(p)} = p$. This implies that $\{p \in P | i(p) \le n\}$ is a subsequence of T.\r
672 \item Transitive closure set at index $n$: A set $\mathscr{S}$ of clients comprising a connected component of an undirected graph, where two clients are connected by an edge if they both received the same message $t$ with index $i(t) > n$.\r
673 \r
674 \end{enumerate}\r
675 \r
676 \subsection{Formal Guarantee}\r
677 \r
678 \begin{prop} Every client $J$ who sends a message $t$ has $A(t)$ as its latest stored message, and $i(t) = i(A(t)) + 1$. \end{prop}\r
679 \begin{proof} True by definition, because $J$ sets $HMAC_P(t) = HMAC_C(A(t))$ and $i(t) = i(A(t)) + 1$ when a message is sent. \end{proof}\r
680 \r
681 \begin{prop} If a rejected message entry is added to the RML at index $i$, the message will remain in the RML until every client has seen it. \end{prop}\r
682 \begin{proof} Every RML entry $e$ remains in the queue until it reaches the tail, and is refreshed by the next sender $J$ at that time if $min(MS) > i(e)$; that is, until every client has sent a message with sequence number greater than $i(e)$. Because every client who sends a message with index $i$ has the state of the queue at $i - 1$, this client will have seen the message at $i(e)$. \end{proof}\r
683 \r
684 \begin{lem} \r
685 \r
686 \end{lem}\r
687 \r
688 \begin{lem} If two packets $t$ and $u$, with $i(t) \le i(u)$, are received without errors by a client $C$, then $t$ is in the path of $u$. \end{lem}\r
689 \begin{proof}\r
690 Assume that $t$ is not in the path of $u$. Take $u$ to be the packet of smallest index for which this occurs, and $t$ be the packet with largest index for this $u$. We will prove that an error occurs upon receipt of $u$.\r
691 \r
692 Let $R_1$ be the earliest member of the path of $t$ that is not in the path of $u$, and $q$ be its parent. $q$, the last common ancestor of $t$ and $u$, must exist, since all clients and the server were initialized with the same state. Let $S_1$ be the successor of $q$ that is in the path of $u$; we know $S_1 \neq R_1$. Let $R = (R_1, R_2, \dots, R_m = t)$ be the distinct portion of the path of $t$, and similarly let $S$ be the distinct portion of the path of $S_n = u$.\r
693 \r
694 Let $J = s(R_1)$, and $K = s(S_1)$. Because no client can send two messages with the same index, and $i(R_1) = i(S_1) = i(q) + 1$, we know that $J \neq K$.\r
695 \r
696 There are two cases:\r
697 \r
698 \begin{itemize}\r
699 \item Case 1: $J$ did not send a message in $S$. Then $v_J(t) > v_J(q) = v_J(u)$.\r
700 \begin{itemize}\r
701 \item Case 1.1: $C$ will throw an error, because the latest index of $J$ changes in the opposite direction of the sequence number: $v_J(u) < v_J(t)$ but $i(u) > i(t)$.\r
702 \r
703 \r
704 \r
705 \end{itemize}\r
706 \r
707 \r
708 \r
709 \item Case 2: $J$ sent at least one message in $S$. Call the first one $p$. We know that $i(p) > i(S_1)$, since $J \neq K$. $R_1$ must be sent either before or after $p$.\r
710 \begin{itemize}\r
711 \item Case 2.1: Client $J$ sends $p$, and then $R_1$. When $p$ was sent, whether it was accepted or rejected, $i(J, p) \geq i(p)$. Since $i(p) > i(S_1)$, $i(J, p) > q$. So $i(q) < i(J, p)$, which would cause $J$ to fail to send $R_1$, a contradiction.\r
712 \begin{itemize}\r
713 \item Case 2.2.1: \r
714 \r
715 \r
716 \r
717 \end{itemize}\r
718 \item Case 2.2: Client $J$ sends $R_1$, and then $p$. Let $X = (R_1, \dots )$ be the list of messages $J$ sends starting before $R_1$ and ending before $p$.\r
719 \begin{itemize}\r
720 \item Case 2.2.1: Some message in $X$ was accepted. In this case, before sending $p$, $J$'s value for its own latest index would be strictly greater than $v_J(q)$. ($J$ could not have sent a message with index less than $i(q)$ after receiving $q$). When preparing to send $p$, $J$ would have received its own latest index as at most $v_J(q)$. $J$ throws an error before sending $p$, because its own latest index decreases.\r
721 \item Case 2.2.2: All messages in $X$ were rejected. Client $J$ will always add the latest rejected message to the rejected-message list in the next update; so for every $i$, $1 \leq i < |X|$, the $i$th element of $X$ will be recorded in the RML of all further elements of $X$; and every element of $X$ will be recorded in $RML(p)$. Since every rejected message in $RML(p)$ will be in $RML(C, u)$, and $u$ is the first message that $C$ sees which does not have $t$ in its path, $R_1$ will be recorded in $RML(C, p)$. When $C$ receives $u$, $C$ will throw an error from the match $(J, iq+1)$ in $RML(C, p)$.\r
722 \end{itemize}\r
723 \end{itemize}\r
724 \end{itemize}\r
725 \end{proof}\r
726 \r
727 \begin{theorem}\r
728 Suppose that there is a transitive closure set $\mathscr{S}$ of clients, at index $n$. Then there is some total message sequence $T$ of length $n$ such that every client $C$ in $\mathscr{S}$ sees a partial sequence $P_C$ consistent with $T$. \end{theorem}\r
729 \r
730 \begin{proof}\r
731 The definition of consistency of $P_C$ with $T$ is that every message $p \in P_C$ with index $i(p) \le n$ is equal to the message in that slot in $T$. Let $C_1$ be some client in the transitive closure set, with partial message sequence $P_{C_1}$, and let $u$ be some message with $i(u) > i$ that $C_1$ shares with another client. Then let $T$ be the portion of the path of $u$ ending at index $i$ and $t$ be the message at that index. Clearly, by Lemma 1, $P_{C_1}$ is consistent with $T$, and furthermore. We will show that, for every other client $D$ with partial sequence $P_D$, $P_D$ has some message whose path includes $t$. Because $D$ is in the transitive closure, there is a sequence of edges from $C_1$ to $D$. Call this $\mathscr{C} = (C_1, C_2, ..., D)$. I will prove by induction that $D$ has a message whose path includes $t$.\r
732 \r
733 For the base case, $P_{C_1}$ includes $u$, whose path includes $t$. For the inductive step, suppose $P_{C_k}$ has an message $w$ with a path that includes $t$, and shares message $x$ with $P_{C_{k+1}}$ such that $i(x) > i$. If $i(w) = i(x)$, then $w = x$. If $i(w) < i(x)$, then, by Lemma 1, $w$ is in the path of $x$. If $i(w) > i(x)$, $x$ is in the path of $w$; note again that its index is greater than $i$. In any case, $t$ is in the path of $u_k+1$.\r
734 \r
735 Let $w$ the message of $D$ whose path includes $t$. By Lemma 1, every message in $P_D$ with index smaller than $i(w)$ is in the path of $w$. Since $t$ is in the path of $w$, every message in $P_D$ with smaller index than $i(t)$ is in $T$. Therefore, $P_D$ is consistent with $T$.\r
736 \end{proof}\r
737 \r
738 \subsection{Future Work}\r
739 \paragraph{Support Messages}\r
740   A message is dead once receiving machine sends an entry with a newer\r
741   sequence identifier\r
742 \r
743 \paragraph{Persistent data structures}\r
744         Root object w/ fields\r
745         Other objects can be reachable from root\r
746         Each object has its own entries\r
747         Dead objects correspond to dead \r
748 \r
749 \paragraph{Multiple App Sharing}\r
750 \r
751 Idea is to separate subspace of entries...  Shared with other cloud...\r
752 \end{document}\r