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