Server algorithm revised - two basic functions, e.g. put and get; preliminary writeup...
authorrtrimana <rtrimana@uci.edu>
Mon, 11 Jul 2016 16:28:17 +0000 (09:28 -0700)
committerrtrimana <rtrimana@uci.edu>
Mon, 11 Jul 2016 16:28:17 +0000 (09:28 -0700)
doc/iotcloud.tex

index 12266ac..4f59ad8 100644 (file)
@@ -6,7 +6,7 @@
 \newtheorem{theorem}{Theorem}\r
 \newtheorem{defn}{Definition}\r
 \newcommand{\note}[1]{{\color{red} \bf [[#1]]}}\r
-\newcommand{\pushcode}[1][1]{\hskip\dimexpr #1\algorithmicindent\relax}\r
+\newcommand{\push}[1][1]{\hskip\dimexpr #1\algorithmicindent\relax}\r
 \begin{document}\r
 \section{Approach}\r
 \r
@@ -124,49 +124,65 @@ Client can make a request to resize the queue. This is done as a write that comb
        (b) a request to the server\r
 \r
 \subsection{Server Algorithm}\r
+\textbf{Key-Value $\langle K,V \rangle$ Pair} \\\r
+$k \in K$ \\\r
+$v \in V$ \\\r
+$\langle k,v \rangle \in P \subseteq K \times V$ \\\r
+$s \in SN \subseteq P*$ \\\r
+$slot_s = \langle s,E( \langle k,v \rangle ) \rangle$ \\\r
+$SN = \{sn_1, sn_2, \dots, sn_n\}$ \\\r
+$Q = \{slot_{sn_1}, slot_{sn_2}, \dots, slot_{sn_n}\}$ \\\r
+\r
+\textbf{States} \\\r
+\textit{Q = queue of slots on server} \\\r
+\textit{SN = set of existing sequence numbers $\leftrightarrow$\r
+$SN = \{sn_1, sn_2, \dots, sn_n\}$} \\\r
+\textit{max = maximum number of slots (input only for resize message)} \\\r
+\textit{n = number of slots} \\\r
+\textit{d = distance between two subsequent $sn_i$, e.g. 1 for 1, 2, 3, \r
+$\dots$} \\\r
+\r
 \begin{algorithmic}[1]\r
-%\Function{CallServer}{$m$,$max$,$s$,$Data*$}\r
-\Function{CallServer}{$m,max,s,Data*$}\r
-\textit{\r
-\newline{// m = client message (read/write/resize)}\r
-\newline{// max = maximum number of slots (input only for resize message)}\r
-\newline{// n = number of slots}\r
-\newline{// s = sequence number}\r
-\newline{// t = sequence numbers of slots on server}\r
-\newline{// d = sequence number difference (1 by default)}\r
-\newline{// Data = array of slots written/read (input only for write)}\r
-\newline{// Q = queue of slots on server}\r
-\newline{// Slot = one data slot)}\r
-\newline{// Resize() returns the old last slot in the queue}\r
-\newline{// Append() updates Q and latest s after appending the new slot}\r
-\newline{// Append() returns the latest Slot written with its correct s}\r
-}\r
-\If{$m = read$}\r
-       \If{$s \in T = \{t_1, t_2, \dots, t_n\}$}\r
-               \State $Data \gets \{Slot_{s}, Slot_{s+1}, \dots, Slot_{t_n}\} \forall Slot_i \in Q$\r
-       \Else\r
-               \State $Data \gets \emptyset$\r
-       \EndIf\r
-\ElsIf{$m = write$}\r
-       \If{$(s = t_n + d) \land (n \leq max) \land (Length(Data) = 1$)}\r
-               \State $newSlot \gets Data[1]$\r
-               \If{$n = max$}\r
-                       \State $Data[2] \gets RemoveFirst(Q)$\r
-                       \State $Data[1] \gets Append(newSlot,Q)$\r
-               \Else \Comment{$n < max$}\r
-                       \State $n \gets n + 1$\r
-                       \State $Data[1] \gets Append(newSlot,Q)$\r
-               \EndIf\r
-       \Else\r
-               \State $Data \gets \emptyset$\r
-       \EndIf\r
-\ElsIf{$m = resize$}\r
-       \State $Data \gets Resize(max)$\r
+\Function{Get}{$s,Data$}\r
+\If{$s \in SN$}\r
+       \State $Data \gets \{slot_{s}, \dots, slot_{sn_n}\} \forall $\r
+    $slot_i = \langle i,E( \langle k,v \rangle ) \rangle \in Q$\r
+\Else\r
+       \State $Data \gets \emptyset$\r
 \EndIf\r
 \State \Return{$Data$}\r
 \EndFunction\r
 \end{algorithmic}\r
 \r
+\begin{algorithmic}[1]\r
+\Function{Put}{$s,newMax,newSlot$}\r
+\If{$(newMax \neq \emptyset) \land (newMax > max)$}\Comment{Resize}\r
+       \State $Q' \gets \{slot_1, slot_2, \dots, slot_{newMax}\} \forall slot_i = 0 \r
+       \Leftrightarrow Q' = \emptyset$\r
+       \State $Q \gets Q' \cup Q$\r
+    \State $max \gets newMax$\r
+\EndIf\r
+\If{$(s = sn_n + d)$}\r
+       \If{$n = max$}\r
+               \State $Q \gets Q - \{slot_{sn_1}\}$\r
+               \State $SN \gets SN - \{sn_1\}$\r
+               \State $Q \gets Q \cup newSlot$\r
+       \Else \Comment{$n < max$}\r
+               \State $Q \gets Q \cup newSlot$\r
+               \State $n \gets n + 1$\r
+       \EndIf\r
+    \State $SN \gets SN \cup \{s\: |\: s = new\: sn_n\}$\r
+       \State $status \gets true$\r
+    \State $MSlot \gets \emptyset$\r
+\Else\r
+       \State $status \gets false$\r
+    \State $MSlot \gets \{slot_{s}, \dots, slot_{sn_n}\} \forall $\r
+    $slot_i = \langle i,E( \langle k,v \rangle ) \rangle \in Q$\r
+\EndIf\r
+\State \Return{$\langle status,MSlot \rangle$}\Comment{Return missed updates and status}\r
+\EndFunction\r
+\end{algorithmic}\r
+\r
 \subsection{Client Algorithm}\r
 \begin{algorithmic}[1]\r
 \Function{CallClient}{$uid,pw,d,m,max,s,Data*,Result*$}\r
@@ -202,7 +218,7 @@ Client can make a request to resize the queue. This is done as a write that comb
                \ForAll{$Slot_i \in Data$}\r
                        \State $DSlot_i \gets Decrypt(SK,Slot_i)$\Comment{Check s and HMAC}\r
                        \If{$\neg (ValidSeqN(DSlot_i) \land ValidHmac(DSlot_i) \land $\\\r
-                               \pushcode[1] $ValidPrevHmac(DSlot_i))$}\r
+                               \push[1] $ValidPrevHmac(DSlot_i))$}\r
                                \State $ReportError(DSlot_i,read)$\r
                        \Else\Comment{Check only live entries}\r
                                \If{$IsLiveSlotSequenceEntry(DSlot_i)$}\r
@@ -216,12 +232,12 @@ Client can make a request to resize the queue. This is done as a write that comb
                                        \State $seq \gets SeqN(DSlot_i)$\r
                                        \If{$IsOwnMid(mid)$}\r
                                                \If{$IsLastS(mid,seq,Data) \land $\\\r
-                                               \pushcode[1] $(seq \neq LastSeqN(mid,M))$}\r
+                                               \push[1] $(seq \neq LastSeqN(mid,M))$}\r
                                                        \State $ReportError(DSlot_i,read)$\r
                                                \EndIf\r
                                        \Else\Comment{Check s for other machines}\r
                                                \If{$IsLastS(mid,seq,Data) \land $\\\r
-                                               \pushcode[1] $(seq < LastSeqN(mid,M))$}\r
+                                               \push[1] $(seq < LastSeqN(mid,M))$}\r
                                                        \State $ReportError(DSlot_i,read)$\r
                                                \EndIf\r
                                        \EndIf\Comment{Check queue state entry}\r
@@ -279,40 +295,93 @@ Client can make a request to resize the queue. This is done as a write that comb
 \textit{To be completed ...}\r
 \r
 \begin{defn}[System Execution]\r
-Formalize a system execution as a sequence of slot updates...  There\r
-is a total order of all slot updates.\r
+Let \\\r
+\begin{center}\r
+$Q = \{slot_{sn_1}, slot_{sn_2}, \dots, Slot_{sn_n}\}$, \\\r
+$SN = \{sn_1, sn_2, \dots, sn_n\}$ \\\r
+\end{center}\r
+denote a queue $Q$ of $n$ slots, with each slot entry being denoted by a\r
+valid sequence number $sn_i \in SN$. $Q$ represents a total order of all \r
+slot updates from all corresponding machines.\r
+%\textit{Formalize a system execution as a sequence of slot updates...\r
+%There is a total order of all slot updates.}\r
 \end{defn}\r
 \r
 \begin{defn}[Transitive Closure]\r
-Define transitive closure relation for slot updates...  There is an\r
-edge from a slot update to a slot receive event if the receive event\r
-reads from the update event.\r
+A transitive closure $\tau : \tau = \epsilon_{update(slot_i)} R $\r
+$\epsilon_{receive(slot_i)}$ is a relation from slot update event\r
+$\epsilon$ to a slot receive event $\epsilon$ for $slot_i$.\r
+%Define transitive closure relation for slot updates...  There is an\r
+%edge from a slot update to a slot receive event if the receive event\r
+%reads from the update event.\r
 \end{defn}\r
 \r
 \begin{defn}[Suborder]\r
-Define suborder of total order.  It is a sequence of contiguous slots\r
-updates (as observed by a given device).\r
+Let \\\r
+\begin{center}\r
+$q = \{slot_{i}, slot_{i+1}, \dots, slot_{j}\}, \r
+sn_1 \leq i \leq j \leq sn_n \Longrightarrow q \subseteq Q$\r
+\end{center}\r
+denote a suborder of the total order. Set q is a sequence of contiguous\r
+slot updates that is a subset of a total order of all slot updates in Q.\r
+%Define suborder of total order.  It is a sequence of contiguous slots\r
+%updates (as observed by a given device).\r
 \end{defn}\r
 \r
 \begin{defn}[Prefix of a suborder]\r
-Given a sub order $o=u_{i},u_{i+1},...,u_j, u_{j+i},..., u', ...$ and\r
-a slot update $u'$ in $o$, the prefix of $o$ is a sequence of all\r
-updates that occur before $u'$ and $u'$.\r
+Given a suborder \\ \r
+\begin{center}\r
+$q' = \{slot_{i}, slot_{i+1}, \dots, slot_{j}, \dots\}, \r
+sn_1 \leq i \leq j \leq sn_n \Longrightarrow \r
+q' \subseteq Q$\r
+\end{center}\r
+with $slot_{j}$ as a slot update in $q'$, the prefix of $q'$ is a sequence \r
+of all slot updates $\{slot_{i}, slot_{i+1}, \dots, slot_{j-1}\} \cup\r
+slot_{j}$.\r
+%Given a sub order $o=u_{i},u_{i+1},...,u_j, u_{j+i},..., u', ...$ and\r
+%a slot update $u'$ in $o$, the prefix of $o$ is a sequence of all\r
+%updates that occur before $u'$ and $u'$.\r
 \end{defn}\r
 \r
 \begin{defn}[Consistency between a suborder and a total order]\r
-A suborder $o$ is consistent with a total order $t$, if all updates in $o$ appear in $t$ and they appear in the same order.\r
+A suborder $q'$ is consistent with a total order $T$ of $Q$, if all\r
+updates in $q'$ appear in $T$ and they appear in the same order, as \r
+the following:\r
+\begin{center}\r
+$q' = \{slot_{i}, slot_{i+1}, \dots, slot_{j}\},$\r
+$T = \{slot_{sn_1}, \dots, slot_{i}, slot_{i+1}, \dots, slot_{j}, \dots,\r
+slot_{sn_n}\},$ \\ $sn_1 \leq i \leq j \leq sn_n \Longrightarrow\r
+q' \subseteq T$\r
+\end{center}\r
+%A suborder $o$ is consistent with a total order $t$, if all updates in $o$ %appear in $t$ and they appear in the same order.\r
 \end{defn}\r
 \r
 \begin{defn}[Consistency between suborders]\r
-Define notion of consistency between suborders...  Two suborders U,V\r
-are consistent if there exist a total order T such that both U and V\r
-are suborders of T.\r
+Two suborders U and V are consistent if there exist a total order T \r
+such that both U and V are suborders of T.\r
+\begin{center}\r
+$U = \{slot_{i}, slot_{i+1}, \dots, slot_{j}\},$ \\\r
+$V = \{slot_{k}, slot_{k+1}, \dots, slot_{l}\},$ \\\r
+$sn_1 \leq i \leq j \leq k \leq l \leq sn_n,$ \\\r
+$U \subset T \land V \subset T$ \\\r
+$T = \{slot_{sn_1}, \dots, slot_{i}, slot_{i+1}, \dots, slot_{j}, $\\\r
+$\dots, slot_{k}, slot_{k+1}, \dots, slot_{l}, \dots, slot_{sn_n}\}$\r
+\end{center}\r
+%Define notion of consistency between suborders...  Two suborders U,V\r
+%are consistent if there exist a total order T such that both U and V\r
+%are suborders of T.\r
 \end{defn}\r
 \r
 \begin{defn}[Error-free execution]\r
-Define error-free execution --- execution for which the client does\r
-not flag any errors...\r
+An error-free execution, for which the client does not flag any errors\r
+is defined by the following criteria:\r
+\begin{enumerate}\r
+\item Item 1\r
+\item Item 2\r
+\end{enumerate}\r
+%not flag any errors...\r
+%Define error-free execution --- execution for which the client does\r
+%not flag any errors...\r
 \end{defn}\r
 \r
 \begin{theorem} Error-free execution of algorithm ensures that the suborder\r
@@ -350,3 +419,4 @@ Algorithm gives consistent view of data structure.
 \r
 Idea is to separate subspace of entries...  Shared with other cloud...\r
 \end{document}\r
+\r