1 \documentclass[11pt]{article}
\r
2 \newcommand{\tuple}[1]{\ensuremath \langle #1 \rangle}
\r
6 \usepackage{graphicx}
\r
7 \usepackage{mathrsfs}
\r
9 \usepackage{algpseudocode}% http://ctan.org/pkg/algorithmicx
\r
10 \usepackage[all]{xy}
\r
11 \usepackage{varwidth}
\r
13 \newtheorem{theorem}{Theorem}
\r
14 \newtheorem{prop}{Proposition}
\r
15 \newtheorem{lem}{Lemma}
\r
16 \newtheorem{defn}{Definition}
\r
17 \newcommand{\note}[1]{{\color{red} \bf [[#1]]}}
\r
18 \newcommand{\push}[1][1]{\hskip\dimexpr #1\algorithmicindent\relax}
\r
19 \newcommand*\xor{\mathbin{\oplus}}
\r
23 \setlength\parindent{0pt} % Removes all indentation from paragraphs - comment this line for an assignment with lots of text
\r
26 \section{\textbf{Introduction}}
\r
34 \section{\textbf{Server}}
\r
35 The server maintains a collection of slots such that each slot contains some data.
\r
36 The operations on the slot are as follows:
\r
43 \subsection{\textbf{Server Notation Conventions}}
\r
44 $s \in SN$ is a server sequence number\\
\r
45 $sv \in SV$ is a slot's value\\
\r
46 $slot_s = \tuple{s, sv} \in SL \subseteq SN \times SV$
\r
48 \subsection{\textbf{Server State}}
\r
49 \textit{n = current server sequence number}\\
\r
50 \textit{SL = set of live slots on the server}\\
\r
52 \textbf{Initial Server State}\\
\r
56 \subsection{\textbf{Put Slot}}
\r
57 Put slot is an operation that inserts data into a new slot at the server.\\
\r
61 \begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}
\r
62 \textbf{Put Function:}
\r
63 \begin{algorithmic}[1]
\r
64 \Function{PutSlotServer}{$sv_p$}
\r
65 \State $s_p \gets n$
\r
66 \State $n \gets n + 1$
\r
67 \State $SL \gets SL \cup \{\tuple{s_p,sv_p}\}$
\r
73 \subsection{\textbf{Get Slot}}
\r
74 Get slot is an operation that returns all server slots that are greater than some server sequence number.\\
\r
78 \begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}
\r
79 \textbf{Get Function:}
\r
80 \begin{algorithmic}[1]
\r
81 \Function{GetSlotServer}{$s_g$}
\r
82 \State \Return{$\{\tuple{s, sv} \in SL \mid s \geq s_g\}$}
\r
88 \subsection{\textbf{Delete Slot}}
\r
89 Delete slot is an operation that deletes all live slots that have server sequence numbers that are equal to or less than some server sequence number.\\
\r
93 \begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}
\r
94 \textbf{Delete Function:}
\r
95 \begin{algorithmic}[1]
\r
96 \Function{DeleteSlotServer}{$s_d$}
\r
97 \State $SD \gets \{\tuple{s, sv} \in SL \mid s \leq s_g\}$
\r
98 \State $SL \gets SL - SD$
\r
111 \section{\textbf{Client}}
\r
112 The data structure acts as a key store where key-value pairs can be read and set.
\r
113 The data structure exposes the following functions:
\r
115 \item Put Transaction
\r
116 \item Get key-value pair
\r
117 \item Create new key
\r
120 \subsection{\textbf{Client Notation Conventions}}
\r
122 $K$ is the set of all keys.\\
\r
123 $MID$ is the set of the machine IDs of the devices that are in the system.
\r
124 $K_{mid}$ is a set of all keys that have device mid as the arbitrator\\
\r
125 $ssn_s$ is the server sequence number of a record $s$\\
\r
126 $mid_s \in MID$ is the machine ID for the device that created $record_s$.\\
\r
127 $hmac_s$ is the HMAC of $record_s$\\
\r
128 $c_{mid}$ is the latest read clock for a device with machine ID $mid$\\
\r
129 $vc_s = \{c_{mid} | mid \in MID\}$\\
\r
130 $rid_s = \tuple{mid_s, c_{mid_s}}$
\r
131 $k$ is a key entry\\
\r
132 $v$ is a value entry\\
\r
133 $kv_n$ is a key-value entry $\tuple{k_n,v_n} , k \in K$\\
\r
135 $tid_s = \tuple{mid_s,c_{mid_s}}$\\
\r
136 $guard_s = \tuple{\{kv_1, kv_2, ... ,kv_n | \exists mid \in MID, \forall n, kv_n[k] \in K_{mid}\},$ boolean condition using $ \{kv_1, kv_2, ... ,kv_n\}} $\\
\r
137 $transaction_s = \{mid_s,vc_{s_t} ,\{kv_1, kv_2,...kv_n | \exists mid \in MID, mid = guard_s[mid], \forall n, kv_n[k] \in K_{mid}\},guard_s\}$\\
\r
138 $commit_s = \tuple{tid_s,vc_s}$\\
\r
139 $abort_s = \tuple{tid_s,mid_s,vc_s}$\\
\r
140 $sequence_s = \tuple{rid_s, ssn_s}$\\
\r
141 $delete_s = \tuple{ssn_d}$\\
\r
142 $resize_s = \tuple{x | x \in \mathbb{N}}$\\
\r
143 $newkey_s = \tuple{k_s, vc_s, ssn_s$ or $-1, mid_s}$\\
\r
145 $payload_s = \{x_1, x_2,..., x_k | \forall k, x_k \in \{$transaction, commit, abort, resize, newkey, sequence, delete$\}\}$\\
\r
146 $rd_s = \tuple{mid_s, vc_s, hmac_s, payload_s}$ \\
\r
147 $record_s = \tuple{ssn_s,rd_s}$\\
\r
149 \subsection{\textbf{Client State}}
\r
150 \textit{s = largest server sequence number pulled from the server by a device} \\
\r
151 \textit{R = set of records pulled from the server so far with their server sequence numbers} \\
\r
152 \textit{RL = set of records that contain live data} \\
\r
154 \subsection{Helper Functions}
\r
155 The following helper functions are needed:\\
\r
157 %Get Payload Items from Record with SSN
\r
159 \begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}
\r
160 \textbf{Get Payload Items from Record with SSN}:
\r
161 \begin{algorithmic}[1]
\r
162 \Function{GetPayloadItemsWithSSN}{$record_s$}
\r
163 \State $PISSN \gets \emptyset$ \Comment{Set of Payload Items with ssn}
\r
164 \State $\tuple{ssn_s, rd_s} \gets record_s$
\r
165 \State $\tuple{mid_s, vc_s, hmac_s, payload_s} \gets rd_s$\\
\r
167 \ForAll{$payloadItems$ in $payload_s$}
\r
168 \State $PISSN \gets PISSN \cup \tuple{payloadItem, ssn_s}$
\r
171 \State \Return {$PISSN$}
\r
177 %Get rid For Record
\r
179 \begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}
\r
180 \textbf{Get rid For Record}:
\r
181 \begin{algorithmic}[1]
\r
182 \Function{GetRid}{$record_s$}
\r
183 \State $\tuple{ssn_s, \tuple{mid_s, \{c_{mid_1}, c_{mid_2}, ... , c_{mid_k}\}, hmac_s, payload_s}} \gets record_s$
\r
184 \State \Return {$\tuple{mid_s, c_{mid_s}}$}
\r
192 \begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}
\r
193 \textbf{Sequence Live}:
\r
194 \begin{algorithmic}[1]
\r
195 \Function{SequenceLive}{$sequence_s, ssn_{s1}$}
\r
196 \State $API \gets \emptyset$ \Comment{Set of all Payload Items}
\r
197 \State $AS \gets \emptyset$ \Comment{Set of all Payload Items that are sequences}
\r
198 \State $StillHasRecord \gets False$
\r
199 \State $\tuple{rid_s, ssn_{s2}} \gets sequence_s$\\
\r
201 \ForAll{$record$ in $R$}
\r
202 \State $API \gets API \cup$ \Call{GetPayloadItemsWithSSN}{record}
\r
203 \If{$rid_s = $\Call{GetRid}{$record$}}
\r
204 \State $StillHasRecord \gets True$
\r
208 \If{$\lnot StillHasRecord$} \Comment{The Record does not exists anymore}
\r
209 \State \Return{False}
\r
212 \ForAll{$\tuple{ssn, payload}$ in $API$}
\r
213 \If{$payload$ is a $sequence$}
\r
214 \State $AS \gets AS \cup \{\tuple{ssn, payload}\}$ \Comment{Extract all sequence payloads}
\r
218 \ForAll{$\tuple{ssn_1', \tuple{rid', ssn_2'}}$ in $AS$}
\r
219 \If{$(rid'=rid_s) \land (ssn_1' > ssn_{s_1})$}
\r
220 \State \Return{False}
\r
223 \State \Return{True}
\r
231 \begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}
\r
232 \textbf{Delete Live}:
\r
233 \begin{algorithmic}[1]
\r
234 \Function{DeleteLive}{$delete_s, ssn_s$}
\r
235 \State $API \gets \emptyset$ \Comment{Set of all Payload Items}
\r
236 \State $AD \gets \emptyset$ \Comment{Set of all Payload Items that are deletes}
\r
237 \State $\tuple{ssn_d} \gets delete_s$\\
\r
239 \ForAll{record in R}
\r
240 \State $API \gets API \cup$ \Call{GetPayloadItemsWithSSN}{record}
\r
243 \ForAll{$\tuple{ssn, payload}$ in $API$}
\r
244 \If{$payload$ is a $delete$}
\r
245 \State $AD \gets AD \cup \{\tuple{ssn, payload}\}$ \Comment{Extract all delete payloads}
\r
249 \ForAll{delete in AD}
\r
250 \State $\tuple{{ssn_s}', \tuple{{ssn_d}'}} \gets delete$
\r
251 \If{${ssn_d}' > ssn_d$} \Comment{More recently deleted record}
\r
252 \State \Return{False}
\r
253 \ElsIf{$({ssn_d}'= ssn_d) \land ({ssn_s}' > ssn_s)$} \Comment{More recent delete of same record}
\r
254 \State \Return{False}
\r
257 \State \Return{True}
\r
265 \begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}
\r
266 \textbf{Abort Live}:
\r
267 \begin{algorithmic}[1]
\r
268 \Function{AbortLive}{$abort_s$}
\r
269 \State $\tuple{tid_s,mid_s,vc_s} \gets abort_s$\\
\r
270 \ForAll{record in R}
\r
271 \State $\tuple{ssn_s',\tuple{mid_s', vc_s', hmac_s', payload_s'}} \gets record$
\r
272 \If{$(mid_s'=mid_s) \land (vc_s' > vc_s)$}
\r
273 \State \Return{True}
\r
276 \State \Return{False}
\r
284 \begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}
\r
285 \textbf{Resize Live}:
\r
286 \begin{algorithmic}[1]
\r
287 \Function{ResizeLive}{$resize_s, ssn_s$}
\r
288 \State $API \gets \emptyset$ \Comment{Set of all Payload Items}
\r
289 \State $AR \gets \emptyset$ \Comment{Set of all Payload Items that are resize}
\r
290 \State $\tuple{size} \gets resize_s$\\
\r
292 \ForAll{record in R}
\r
293 \State $API \gets API \cup$ \Call{GetPayloadItemsWithSSN}{record}
\r
296 \ForAll{$\tuple{ssn, payload}$ in $API$}
\r
297 \If{$payload$ is a $resize$}
\r
298 \State $AR \gets AR \cup \{\tuple{ssn, payload}\}$ \Comment{Extract all resize payloads}
\r
302 \ForAll{$\tuple{ssn', \tuple{size'}}$ in $AR$}
\r
303 \If{$size' > size$}
\r
304 \State \Return{False}
\r
305 \ElsIf{$(size'=size) \land (ssn' > ssn_s)$}
\r
306 \State \Return{False}
\r
309 \State \Return{True}
\r
317 \begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}
\r
319 \begin{algorithmic}[1]
\r
320 \Function{IsLive}{$item_s, ssn_S$}
\r
321 \If{$item_s$ is a $tansaction$}
\r
322 \State \Return{\Call{TransactionLive}{$item_s, ssn_s$}}
\r
324 \ElsIf{$item_s$ is a $commit$}
\r
325 \State \Return{\Call{CommitLive}{$item_s, ssn_s$}}
\r
327 \ElsIf{$item_s$ is a $abort$}
\r
328 \State \Return{\Call{AbortLive}{$item_s$}}
\r
330 \ElsIf{$item_s$ is a $delete$}
\r
331 \State \Return{\Call{DeleteLive}{$item_s, ssn_s$}}
\r
333 \ElsIf{$item_s$ is a $commit$}
\r
334 \State \Return{\Call{ResizeLive}{$item_s, ssn_s$}}
\r
336 \ElsIf{$item_s$ is a $sequence$}
\r
337 \State \Return{\Call{SequenceLive}{$item_s, ssn_s$}}
\r
339 \ElsIf{$item_s$ is a $newkey$}
\r
340 \State \Return{\Call{NewKeyLive}{$item_s, ssn_s$}}
\r
342 \ElsIf{$item_s$ is a $keyvalue$}
\r
343 \State \Return{\Call{KeyValueLive}{$item_s, ssn_s$}}
\r
346 \State \Return{False} \Comment{Will never get here}
\r
352 %Record has live payload data
\r
354 \begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}
\r
355 \textbf{Record has live payload data:}:
\r
356 \begin{algorithmic}[1]
\r
357 \Function{HasLivePayload}{$record_s, ssn_s$}
\r
358 \State $\tuple{mid_s, vc_s, hmac_s, payload_s} \gets record_s$
\r
359 \ForAll{$item$ in $payload_s$}
\r
360 \If{\Call{IsLive}{$item, ssn_s$}}
\r
361 \State \Return{True}
\r
364 \State \Return{False}
\r
370 % Get Data Structure Size
\r
372 \begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}
\r
373 \textbf{Get Data Structure Size:}
\r
374 \begin{algorithmic}[1]
\r
375 \Function{GetDataStrucSize}{ }
\r
376 \State $API \gets \emptyset$ \Comment{Set of all Payload Items}
\r
377 \State $AR \gets \emptyset$ \Comment{Set of all Payload Items that are resize}
\r
379 \ForAll{record in R}
\r
380 \State $API \gets API \cup$ \Call{GetPayloadItemsWithSSN}{record}
\r
383 \ForAll{$\tuple{ssn, payload}$ in $API$}
\r
384 \If{($payload$ is a $resize) \land$ \Call{IsLive}{$payload, ssn$}}
\r
385 \State $\tuple{size'} \gets payload$
\r
386 \State \Return{$size'$}
\r
390 \State \Return{$0$} \Comment{Get Here only if data structure has no entries}
\r
396 %Rescue Payload Items
\r
398 \begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}
\r
399 \textbf{Rescue Payload Items}:
\r
400 \begin{algorithmic}[1]
\r
401 \Function{RescuePayloadItems}{$payload_s$}
\r
402 \State $PIList =$ empty list of $\tuple{ssn, payload}$
\r
403 \State $SpaceRemaining = MaxPayloadSize - $ \Call{GetSize}{$payload_s$}
\r
405 \If{$SpaceRemaining = 0$}
\r
406 \Return{$payload_s$}
\r
409 \ForAll{record in R}
\r
410 \State $PIList \gets PIList \cup$ \Call{GetPayloadItemsWithSSN}{$record$}
\r
413 \State Sort $PIList$ by $ssn$ from lowest to highest\\
\r
415 \ForAll{$\tuple{ssn', payload'}$ in $PIList$}
\r
416 \If{\Call{IsLive}{$payload', ssn'$} $\land$ \Call{getRandomBoolean}{ } }
\r
418 \If{\Call{GetSize}{$payload'$} $ > SpaceRemaining$} \Comment{No more space for resuces in payload}
\r
419 \State \Return{$payload_s$}
\r
422 \State $SpaceRemaining \gets SpaceRemaining -$ \Call{GetSize}{$payload'$}
\r
423 \State $payload_s \gets payload_s \cup payload'$
\r
426 \State \Return{$payload_s$}
\r
434 \begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}
\r
435 \textbf{Pad Payload}:
\r
436 \begin{algorithmic}[1]
\r
437 \Function{PadPayload}{$payload_s$}
\r
438 \State $SpaceRemaining = MaxPayloadSize - $ \Call{GetSize}{$payload_s$}
\r
440 \If{$SpaceRemaining = 0$}
\r
441 \State \Return{$payload_s$}
\r
443 \State \Return{$payload_s \gets payload_s \cup$ \Call{GenerateFiller}{$SpaceRemaining$}}
\r
451 \begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}
\r
452 \textbf{Delete Records (Deletes n records)}:
\r
453 \begin{algorithmic}[1]
\r
454 \Function{Delete}{$num\_of\_records$}
\r
455 \State $RS \gets$ List of all Records sorted by ssn and has form $\tuple{ssn_s, record_s}$
\r
456 \State $n \gets 0$\\
\r
458 \ForAll{$\tuple{ssn_s, record_s}$ in $RS$}
\r
459 \If{\Call{HasLivePayload}{$record_s, ssn_s$}}
\r
460 \State \Call{ResizeDataStruc}{ }
\r
461 \State \Return{False}
\r
463 \State \Call{DeleteSlotServer}{$ssn_s$}
\r
464 \State $n \gets n + 1$
\r
467 \If{$n = num\_of\_records$}
\r
468 \State \textbf{break}
\r
472 \State \Return{True}
\r
482 \textbf{Evaluate Guard Condition:}\\
\r
483 \textbf{Get Latest Data Structure From Server:}\\
\r
484 \textbf{Check Data Structure for Malicious Activity:}\\
\r
485 \textbf{Resize Data Structure:}\\
\r
486 \textbf{Get Transaction Arbitrator}:\\
\r
487 \textbf{Transaction Live}:\\
\r
488 \textbf{Commit Live}:\\
\r
489 \textbf{New Key Live}:\\\
\r
490 \textbf{Key Value Live}:\\\
\r
493 % - Need to Change Transaction sizes
\r
500 %-Check Data Structure
\r
502 \subsection{\textbf{Put Transaction}}
\r
506 \subsection{\textbf{Get key-value pair}}
\r
507 \subsection{\textbf{Create new key}}
\r