\documentclass[11pt]{article}\r
\newcommand{\tuple}[1]{\ensuremath \langle #1 \rangle}\r
+\usepackage{color}\r
\usepackage{amsthm}\r
+\usepackage{algpseudocode}% http://ctan.org/pkg/algorithmicx\r
\newtheorem{theorem}{Theorem}\r
\newtheorem{defn}{Definition}\r
-\r
+\newcommand{\note}[1]{{\color{red} \bf [[#1]]}}\r
+\newcommand{\push}[1][1]{\hskip\dimexpr #1\algorithmicindent\relax}\r
\begin{document}\r
\section{Approach}\r
\r
Each device has: user id + password\r
\r
Server login is:\r
-hash1(user id), hash1(password)...\r
+hash1(user id), hash1(password)\r
\r
Symmetric Crypto keys is:\r
hash2(user id | password)\r
Payload has:\r
\begin{enumerate}\r
\item Sequence identifier\r
-\item Machine id\r
-\item Hash of previous slot\r
+\item Machine id (most probably something like a 64-bit random number \r
+that is self-generated by client)\r
+\item HMAC of previous slot\r
\item Data entries\r
\item HMAC of current slot\r
\end{enumerate}\r
\r
-Data entry can be:\r
+A data entry can be one of these:\r
\begin{enumerate}\r
-\item All or part of a Key-value entry,\r
-\item Slot sequence entry: Machine id + last message identifier, or\r
-\item Queue state entry: Includes queue size\r
+\item All or part of a Key-value entry\r
+\item Slot sequence entry: Machine id + last message identifier \r
+\newline {The purpose of this is to keep the record of the last slot \r
+from a certain client if a client's update has to expunge that other \r
+client's last entry from the queue. This is kept in the slot until \r
+the entry owner inserts a newer update into the queue.}\r
+\item Queue state entry: Includes queue size \newline {The purpose \r
+of this is for the client to tell if the server lies about the number \r
+of slots in the queue, e.g. if there are 2 queue state entry in the queue, \r
+e.g. 50 and 70, the client knows that when it sees 50, it should expect \r
+at most 50 slots in the queue and after it sees 70, it should expect \r
+50 slots before that queue state entry slot 50 and at most 70 slots. \r
+The queue state entry slot 70 is counted as slot number 51 in the queue.}\r
+\item Collision resolution entry: Machine id + message identifier of\r
+collision winner\r
+\newline {The purpose of this is to keep keep track of the winner of \r
+all the collisions until all clients have seen the particular entry.}\r
\end{enumerate}\r
\r
\subsection{Live status}\r
\item Key-Value Entry is dead if either (a) there is a newer key-value pair or (b) it is incomplete.\r
\r
\item Slot sequence number (of either a message version data\r
-or user-level data) is dead if there is a newer slot from the same machine\r
+or user-level data) is dead if there is a newer slot from the same machine.\r
+\r
+\item Queue state entry is dead if there is a newer queue state entry.\r
+{In the case of queue state entries 50 and 70, this means that queue state \r
+entry 50 is dead and 70 is live. However, not until the number of slots reaches \r
+70 that queue state entry 50 will be expunged from the queue.}\r
\r
-\item Queue state entry is dead if there is a newer queue state entry\r
+\item Collision resolution entry is dead if this entry has been seen\r
+by all clients after a collision happens.\r
\end{enumerate}\r
\r
When data is at the end of the queue ready to expunge, if:\r
beginning of the queue.\r
\r
\item If the slot sequence number is not dead, then a message sequence\r
-entry must be inserted\r
+entry must be inserted.\r
\r
\item If the queue state entry is not dead, it must be reinserted at the\r
-beginning of the queue\r
+beginning of the queue.\r
\end{enumerate}\r
\r
\r
server sends updates slots to client and client validates those slots.\r
\r
\paragraph{Local state on each client:}\r
-A list of machines and the corresponding latest sequence numbers\r
+A list of machines and the corresponding latest sequence numbers.\r
\r
\paragraph{Validation procedure on client:}\r
\begin{enumerate}\r
-\item Decrypt each new slot in order\r
+\item Decrypt each new slot in order.\r
\item For each slot:\r
- (a) check its HMAC\r
+ (a) check its HMAC, and\r
(b) check that the previous entry HMAC field matches the previous\r
- entry\r
+ entry.\r
\item Check that the last message version for our machine matches our\r
-last message sent\r
+last message sent.\r
\item For all other machines, check that the latest sequence number is\r
-at least as large (never goes backwards)\r
-\item That the queue has a current queue state entry\r
+at least as large (never goes backwards).\r
+\item That the queue has a current queue state entry.\r
\item That the number of entries received is consistent with the size\r
-specified in the queue state entry\r
+specified in the queue state entry.\r
\end{enumerate}\r
\r
Key-value entries can span multiple slots. They aren't valid until\r
they are complete.\r
\r
\subsection{Resizing Queue}\r
-Client can make a request to resize the queue... This is done as a write that combines:\r
- (a) a slot with the message\r
+Client can make a request to resize the queue. This is done as a write that combines:\r
+ (a) a slot with the message, and\r
(b) a request to the server\r
\r
+\subsection{Server Algorithm}\r
+$s \in SN$ is a sequence number set\\\r
+$sv \in SV$ is a slot's value\\\r
+$slot_s = \tuple{s, sv} \in SL \subseteq SN \times SV$ \\\r
+\r
+\textbf{State} \\\r
+\textit{SL = set of live slots on server} \\\r
+\textit{max = maximum number of slots (input only for resize message)} \\\r
+\textit{n = number of slots} \\ \\\r
+\textbf{Helper Function} \\\r
+$MaxSlot(SL_s)= \tuple{s, sv} \mid \tuple{s, sv}\r
+\in SL_s \wedge \forall \tuple{s_s, sv_s} \in SL_s, s \geq s_s$ \\\r
+$MinSlot(SL_s)= \tuple{s, sv} \mid \tuple{s, sv} \r
+\in SL_s \wedge \forall \tuple{s_s, sv_s} \in SL_s, s \leq s_s$ \\\r
+$SeqN(\tuple{s, sv})=s$ \\\r
+$SlotVal(\tuple{s, sv})=sv$ \\\r
+\r
+\begin{algorithmic}[1]\r
+\Function{GetSlot}{$s_g$}\r
+\State \Return{$\{\tuple{s, sv} \in SL \mid s \geq s_g\}$}\r
+\EndFunction\r
+\end{algorithmic}\r
+\r
+\begin{algorithmic}[1]\r
+\Function{PutSlot}{$s_p,sv_p,max'$}\r
+\If{$(max' \neq \emptyset)$}\Comment{Resize}\r
+\State $max \gets max'$\r
+\EndIf\r
+\State $\tuple{s_n,sv_n} \gets MaxSlot(SL)$\Comment{Last sv}\r
+\State $s_n \gets SeqN(\tuple{s_n,sv_n})$\r
+\If{$(s_p = s_n + 1)$}\r
+ \If{$n = max$}\r
+ \State $\tuple{s_m,sv_m} \gets MinSlot(SL)$\Comment{First sv}\r
+ \State $SL \gets SL - \{\tuple{s_m,sv_m}\}$\r
+ \Else \Comment{$n < max$}\r
+ \State $n \gets n + 1$\r
+ \EndIf\r
+ \State $SL \gets SL \cup \{\tuple{s_p,sv_p}\}$\r
+ \State \Return{$(true,\emptyset)$}\r
+\Else\r
+ \State \Return{$(false,\{\tuple{s,sv}\in SL \mid \r
+ s \geq s_p\})$}\r
+\EndIf\r
+\EndFunction\r
+\end{algorithmic}\r
+\r
+\subsection{Client Algorithm}\r
+\textbf{Data Entry} \\\r
+$de$ is a data entry \\\r
+$k$ is key of entry \\\r
+$v$ is value of entry \\\r
+$kv$ is a key-value entry $\tuple{k,v}$, $kv \in D$ \\\r
+$ss$ is a slot sequence entry $\tuple{id,s_{last}}$, \r
+id + last s of a machine, $ss \in D$ \\\r
+$qs$ is a queue state entry, $qs \in D$ \\\r
+$D = \{kv,ss,qs\}$ \\\r
+$DE = \{de \mid de \in D\}$ \\ \\\r
+$s \in SN$ is a sequence number set\\\r
+$id$ is a machine ID\\\r
+$hmac_p$ is the HMAC value of the previous slot \\\r
+$hmac_c$ is the HMAC value of the current slot \\\r
+$Dat_s = \tuple{s,id,hmac_p,DE,hmac_c}$ \\\r
+$sv_s = \tuple{s, E(Dat_s)} = \r
+\tuple{s, E(\tuple{s,id,hmac_p,DE,hmac_c})}$ \\ \\\r
+\r
+\textbf{States} \\\r
+\textit{DT = set of $\tuple{k,v}$ on client} \\\r
+\textit{MS = set of $\tuple{id, s_{last}}$ of all clients on client \r
+(initially empty)} \\\r
+\textit{$MS_c$ = set MS to save all $\tuple{id, s_{last}}$ pairs while\r
+traversing DT after a request to server (initially empty)} \\\r
+\textit{$max_c$ = maximum number of slots (initially $max_c > 0$)} \\\r
+\textit{m = number of slots on client (initially $m = 0 and m \leq n$)} \\\r
+\textit{$hmac_p$ = the HMAC value of the previous slot ($hmac_p = \emptyset$ \r
+for the first slot)} \\\r
+\textit{$id_{self}$ = machine Id of this client} \\\r
+\textit{SK = Secret Key} \\ \\\r
+\textbf{Helper Functions} \\\r
+$MaxSlot(SL_s)= \tuple{s, sv}$ \textit{such that} $\tuple{s, sv}\r
+\in SL_s \wedge \forall \tuple{s_s, sv_s} \in SL_s, s \geq s_s$ \\\r
+$MinSlot(SL_s)= \tuple{s, sv}$ \textit{such that} $\tuple{s, sv} \r
+\in SL_s \wedge \forall \tuple{s_s, sv_s} \in SL_s, s \leq s_s$ \\\r
+$Slot(SL_s,s_s)= \tuple{s, sv}$ \textit{such that} $\tuple{s, sv} \r
+\in SL_s \wedge \forall \tuple{s_s, sv_s} \in SL_s, s = s_s$ \\\r
+$SeqN(\tuple{s, sv})=s$ \\\r
+$SlotVal(\tuple{s, sv})=sv$ \\\r
+$Decrypt(SK_s,sv_s)=Dat_s=\tuple{s,id,hmac_p,DE,hmac_c}$ \\\r
+$ComputeHash(bit_s)$ is a hash function that generates hash value on $bit_s$ \\\r
+$ComputeHmac(bit_s,SK_s)$ is a HMAC function that generates HMAC value on $bit_s$ \r
+based on key $SK_s$\\\r
+$GetSeqN(Dat_s = \tuple{s,id,hmac_p,DE,hmac_c})=s$ \\\r
+$GetMacId(Dat_s = \tuple{s,id,hmac_p,DE,hmac_c})=id$ \\\r
+$GetPrevHmac(Dat_s = \tuple{s,id,hmac_p,DE,hmac_c})=hmac_p$ \\\r
+$GetCurrHmac(Dat_s = \tuple{s,id,hmac_p,DE,hmac_c})=hmac_c$ \\\r
+$GetDatEnt(Dat_s = \tuple{s,id,hmac_p,DE,hmac_c})=DE$ \\\r
+$GetQS(de_s$ \textit{such that} $de_s \in D \land de_s = qs)=qs$ \\\r
+$GetSS(de_s$ \textit{such that} $de_s \in D \land de_s = ss)=ss$ \\\r
+$GetKV(de_s$ \textit{such that} $de_s \in D \land de_s = kv)=kv=\tuple{k,v}$ \\\r
+$GetLastSeqN(MS_s,id_s)= s_{last}$ \textit{such that} $\tuple{id, s_{last}}\r
+\in MS_s \wedge \forall \tuple{id_s, s_{s_{last}}} \in MS_s, \r
+id = id_s$ \\\r
+$GetKey(\tuple{k, v})=k$ \\\r
+$GetVal(\tuple{k, v})=v$ \\\r
+$GetKeyVal(DT_s,k_s)= \tuple{k, v}$ \textit{such that} $\tuple{k, v} \r
+\in DT_s \wedge \forall \tuple{k_s, v_s} \in DT_s, k = k_s$ \\\r
+\r
+\begin{algorithmic}[1]\r
+\Procedure{ReportError}{$msg$}\r
+\State $Print(msg)$\r
+\State $Halt()$\r
+\EndProcedure\r
+\end{algorithmic}\r
+\r
+\begin{algorithmic}[1]\r
+\Function{ValidHmac}{$Dat_s,SK_s$}\r
+\State $hmac_{stored} \gets GetCurrHmac(Dat_s)$\r
+\State $hmac_{computed} \gets Hmac(Dat_s,SK_s)$\r
+\If{$hmac_{stored} = hmac_{computed}$}\r
+ \State $valid \gets true$\r
+\Else\r
+ \State $valid \gets false$\r
+\EndIf\r
+\State \Return{$valid$}\r
+\EndFunction\r
+\end{algorithmic}\r
+\r
+\begin{algorithmic}[1]\r
+\Function{ValidPrevHmac}{$Dat_s,hmac_{p_s}$}\r
+\If{$hmac_{p_s} = \emptyset$}\Comment{First slot - no previous HMAC}\r
+ \State $valid \gets true$\r
+\Else\r
+ \State $hmac_{stored} \gets GetPrevHmac(Dat_s)$\r
+ \If{$hmac_{stored} = hmac_{p_s}$}\r
+ \State $valid \gets true$\r
+ \Else\r
+ \State $valid \gets false$\r
+ \EndIf\r
+\EndIf\r
+\State \Return{$valid$}\r
+\EndFunction\r
+\end{algorithmic}\r
+\r
+\begin{algorithmic}[1]\r
+\Function{GetQueSta}{$Dat_s$}\r
+\State $DE_s \gets GetDatEnt(Dat_s)$\r
+\State $de_{qs} \gets de_s$ \textit{such that} $de_s \in DE_s, \r
+ de_s \in D \land de_s = qs$\r
+\If{$de_{qs} \neq \emptyset$}\r
+ \State $qs_{ret} \gets GetQS(de_{qs})$\r
+\Else\r
+ \State $qs_{ret} \gets \emptyset$\r
+\EndIf\r
+\State \Return{$qs_{ret}$}\r
+\EndFunction\r
+\end{algorithmic}\r
+\r
+\begin{algorithmic}[1]\r
+\Function{GetSlotSeq}{$Dat_s$}\r
+\State $DE_s \gets GetDatEnt(Dat_s)$\r
+\State $de_{ss} \gets de_s$ \textit{such that} $de_s \in DE_s, \r
+ de_s \in D \land de_s = ss$\r
+\If{$\tuple{id_{ret},s_{last_{ret}}} \neq \emptyset$}\r
+ \State $\tuple{id_{ret},s_{last_{ret}}} \gets GetSS(de_{ss})$\r
+\Else\r
+ \State $\tuple{id_{ret},s_{last_{ret}}} \gets \emptyset$\r
+\EndIf\r
+\State \Return{$\tuple{id_{ret},s_{last_{ret}}}$}\r
+\EndFunction\r
+\end{algorithmic}\r
+\r
+\begin{algorithmic}[1]\r
+\Function{UpdateLastSeqN}{$id_s,s_s,MS_s$}\r
+\State $s_t \gets GetLastSeqN(MS_s,id_s)$\r
+\If{$s_t = \emptyset$}\r
+ \State $MS_s \gets MS_s \cup \{\tuple{id_s,s_s}\}$\Comment{First occurrence}\r
+\Else\r
+ \If{$s_s > s_t$}\Comment{Update entry with a later s}\r
+ \State $MS_s \gets (MS_s - \{\tuple{id_s,s_t}\}) \cup \r
+ \{\tuple{id_s,s_s}\}$\r
+ \EndIf\r
+\EndIf\r
+\State \Return{$MS_s$}\r
+\EndFunction\r
+\end{algorithmic}\r
+\r
+\begin{algorithmic}[1]\r
+\Procedure{CheckLastSeqN}{$MS_s,MS_t$}\Comment{Check $MS_t$ based on $MS_s$}\r
+\ForAll{$\tuple{id_t,s_{t_{last}}} \in MS_t$}\r
+ \State $s_{s_{last}} \gets GetLastSeqN(MS_s,id_t)$\r
+ \If{$s_{s_{last}} \neq \emptyset$}\r
+ \If{$id_t = id_{self}$}\r
+ \If{$s_{s_{last}} \neq s_{t_{last}}$}\r
+ \State \Call{ReportError}{'Invalid last $s$ for this machine'}\r
+ \EndIf\r
+ \Else\r
+ \If{$s_{s_{last}} \geq s_{t_{last}}$}\r
+ \State $MS_s \gets (MS_s - \{\tuple{id_t,s_{t_{last}}}\}) \cup \r
+ \{\tuple{id_t,s_{s_{last}}}\}$\r
+ \Else\r
+ \State \Call{ReportError}{'Invalid last $s$ for machine $id_t$'}\r
+ \EndIf\r
+ \EndIf\r
+ \EndIf\r
+\EndFor\r
+\EndProcedure\r
+\end{algorithmic}\r
+\r
+\begin{algorithmic}[1]\r
+\Function{UpdateDT}{$DT_s,Dat_s$}\r
+\State $DE_s \gets GetDatEnt(Dat_s)$\r
+\ForAll{$de_s \in DE_s$}\r
+ \If{$de_s$ \textit{such that} $de_s \in D \land de_s = kv$}\r
+ \State $\tuple{k_s,v_s} \gets GetKV(de_s)$\r
+ \State $k_s \gets GetKey(\tuple{k_s,v_s})$\r
+ \State $\tuple{k_s,v_t} \gets GetKeyVal(DT_s,k_s)$\r
+ \If{$\tuple{k_s,v_t} = \emptyset$}\r
+ \State $DT_s \gets DT_s \cup \{\tuple{k_s,v_s}\}$\r
+ \Else\r
+ \State $DT_s \gets (DT_s - \{\tuple{k_s,v_t}\}) \cup \r
+ \{\tuple{k_s,v_s}\}$\r
+ \EndIf\r
+ \EndIf\r
+\EndFor\r
+\State \Return{$DT_s$}\r
+\EndFunction\r
+\end{algorithmic}\r
+\r
+\begin{algorithmic}[1]\r
+\Function{GetKVPairs}{$s$}\r
+\State $SL_c \gets \Call{GetSlot}{s}$\r
+\State $MS_c \gets \emptyset$\r
+\State $\tuple{s_{c_{max}},sv_{c_{max}}} \gets MaxSlot(SL_c)$\r
+\State $s_{c_{max}} \gets SeqN(\tuple{s_{c_{max}},sv_{c_{max}}})$\r
+\State $\tuple{s_{c_{min}},sv_{c_{min}}} \gets MinSlot(SL_c)$\r
+\State $s_{c_{min}} \gets SeqN(\tuple{s_{c_{max}},sv_{c_{max}}})$\r
+%\For{$\{\tuple{s_c,sv_c} \mid \tuple{s_c,sv_c} \in SL_c\}$}\r
+\For{$s_c \gets s_{c_{min}}$ \textbf{to} $s_{c_{max}}$}\r
+ \State $\tuple{s_c,sv_c} \gets Slot(SL_c,s_c)$\r
+ \State $s_c \gets SeqN(\tuple{s_c,sv_c})$\r
+ \State $sv_c \gets SlotVal(\tuple{s_c,sv_c})$\r
+ \State $Dat_c \gets Decrypt(SK,sv_c)$\r
+ \State $s_{c_{in}} \gets GetSeqN(Dat_c)$\r
+ \If{$s_c \neq s_{c_{in}}$}\r
+ \State \Call{ReportError}{'Invalid sequence number'}\r
+ \EndIf\r
+ \If{$\neg \Call{ValidPrevHmac}{Dat_c,hmac_p}$}\r
+ \State \Call{ReportError}{'Invalid previous HMAC value'}\r
+ \EndIf\r
+ \If{$\neg \Call{ValidHmac}{Dat_c,SK}$}\r
+ \State \Call{ReportError}{'Invalid current HMAC value'}\r
+ \EndIf\r
+ \State $hmac_p \gets Hmac(Dat_c,SK)$\Comment{Update $hmac_p$ for next slot check}\r
+ \State $qs_c \gets \Call{GetQueSta}{Dat_c}$\Comment{Handle qs}\r
+ \If{$qs_c \neq \emptyset \land qs_c > max_c$}\r
+ \State $max_c \gets qs_c$\r
+ \EndIf\r
+ %Check for last s in Dat\r
+ \State $id_c \gets GetMacId(Dat_c)$\Comment{Handle last s}\r
+ \State $MS_c \gets \Call{UpdateLastSeqN}{id_c,s_c,MS_c}$\r
+ %Check for last s in DE in Dat\r
+ \State $\tuple{id_d,s_{d_{last}}} \gets \Call{GetSlotSeq}{Dat_c}$\Comment{Handle ss}\r
+ \If{$\tuple{id_d,s_{d_{last}}} \neq \emptyset$}\r
+ \State $MS_c \gets \Call{UpdateLastSeqN}{id_d,s_{d_{last}},MS_c}$\r
+ \EndIf\r
+ \State $DT \gets \Call{UpdateDT}{DT,Dat_c}$\r
+\EndFor\r
+\If{$m + |SL_c| \leq max_c$}\Comment{Check actual size against $max_c$}\r
+ \State $m \gets m + |SL_c|$\r
+\Else\r
+ \State \Call{ReportError}{'Actual queue size exceeds $max_c$'}\r
+\EndIf\r
+ \State $\Call{CheckLastSeqN}{MS_c,MS}$\r
+\State \Return{$DT$}\r
+\EndFunction\r
+\end{algorithmic}\r
+\r
+\begin{algorithmic}[1]\r
+\Function{GetValFromKey}{$k_g$}\r
+\State $\tuple{k_s,v_s} \gets \tuple{k,v}$ \textit{such that} $\tuple{k,v} \r
+ \in DT \land k = k_g$\r
+\State $v_s \gets GetVal(\tuple{k_s,v_s})$\r
+\State \Return{$v_s$}\r
+\EndFunction\r
+\end{algorithmic}\r
+\r
\subsection{Formal Guarantees}\r
\r
-Rahmadi should clean this section up.\r
+\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
-\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
that are in the transitive closure.\r
\end{theorem}\r
\begin{proof}\r
-Exercise for Rahmadi.\r
+\textit{TODO}\r
\end{proof}\r
\r
\begin{defn}[State of Data Structure]\r
Algorithm gives consistent view of data structure.\r
\end{theorem}\r
\begin{proof}\r
-Exercise for Rahmadi.\r
+\textit{TODO}\r
\end{proof}\r
\r
\subsection{Future Work}\r
\r
Idea is to separate subspace of entries... Shared with other cloud...\r
\end{document}\r
+\r
projects / iotcloud.git / blobdiff