Adding server algorithm

diff --git a/doc/iotcloud.tex b/doc/iotcloud.tex
index a571c065ce58dc235bfcf1bd901de9b8649053cc..c0aaf1b4f52ae1d7dae325f0fdcd9674c4cb3058 100644 (file)
--- a/doc/iotcloud.tex
+++ b/doc/iotcloud.tex
@@ -2,6 +2,7 @@
 \newcommand{\tuple}[1]{\ensuremath \langle #1 \rangle}\r
 \usepackage{color}\r
 \usepackage{amsthm}\r
+\usepackage{algpseudocode}\r
 \newtheorem{theorem}{Theorem}\r
 \newtheorem{defn}{Definition}\r
 \newcommand{\note}[1]{{\color{red} \bf [[#1]]}}\r
@@ -22,61 +23,6 @@ hash2(user id | password)
 Server has finite length queue of entries + max\_entry\_identifier +\r
 server login key\r
 \r
-\textbf{Login}\r
-\note{Look at formal algorithm descriptions elsewhere, this is just informal prose...  It really needs to be more precise...}\r
-\r
-\begin{enumerate}\r
-\item In the beginning, there are $d$ devices. Each of the \r
-devices has a randomly/user-chosen self-generated $m$-bit user \r
-identification $i$ and $n$-bit password $p$.\note{All devices being known in the beginning seems unreasonable...How about 1 device initially, and devices can be added at any time...}\r
-\item Each device registers these $i$ and $p$ with the server. \r
-The server appends ‘salt’ values, $k$-bit random strings $s1$ \r
-and $s2$, and generate hash values $j=h(i+s1)$ and \r
-$o=h(p+s2)$ for each $i$ and $p$. All $s1$, $s2$, $j$ and $o$ \r
-are then stored in the database.\note{Are these the same $i$ and $p$ as below, if so, you just gave away the password}\r
-\item Device to server validation is done by checking the hash values \r
-$j\textsc{\char13}$ and $o\textsc{\char13}$ from $i\textsc{\char13}$ and \r
-$p\textsc{\char13}$ that are given by users at login time against \r
-$i$ and $p$ that are stored in the database.\r
-\end{enumerate}\r
-\r
-\textbf{Symmetric Keys}\r
-\note{The user uses the same username/key to log into all devices}\r
-\begin{enumerate}\r
-\item In the beginning, there are $d$ devices. Each of the \r
-devices has a randomly/user-chosen self-generated $m$-bit user \r
-identification $i$ and $n$-bit password $p$. These $i$ and $p$ \r
-are used for device login on server.\r
-\item All of $d$ agree on a hash function $h$ that is not known by \r
-the server.\note{Doesn't make sense to agree on a hash function...People have a shared key.}\r
-\item A symmetric key for each device is generated by applying $h$\r
-to the value $(i + p)$ that gives $SK=h(i + p)$.\r
-\item This value $SK$ is pre-known and pre-stored by all other \r
-devices prior to operation of the data structure.\r
-\end{enumerate}\r
-\r
-\textbf{Data Structure on Server}\r
-\note{Define server state as an appropriate tuple and then give pseudocode here for updating that tuple...}\r
-\begin{enumerate}\r
-\item Server maintains a finite length $q$-entry FIFO queue \r
-$Q=\{0, 1, …, q-1\}$. It has a head and a tail pointers that keep track \r
-of head and tail slots.\r
-\item Server records a max entry identifier $max$ as a limit for $q$. \r
-It keeps track that $q \leq max$ at all times. When $q=max$, the queue \r
-mechanism allows this sequence of events when there is a new slot added:\r
-\begin{enumerate}\r
-\item Pointer for entry $0$ now points to entry $1$, making it the new \r
-entry $0$.\r
-\item Entry $0$ is expunged from the queue.\r
-\item New entry is added to the end of the queue, making it entry $q$.\r
-\item Pointer for entry $q-1$ is advanced to entry $q$, making it the new \r
-entry $q-1$.\r
-\end{enumerate}\r
-\item For client login, server maintains a table with values $i$, $p$,\r
-$s1$, and $s2$ that are generated when device registers itself on server \r
-for the first time.\r
-\end{enumerate}\r
-\r
 \subsection{Entry layout}\r
 Each entry has:\r
 \begin{enumerate}\r
@@ -177,6 +123,48 @@ Client can make a request to resize the queue. This is done as a write that comb
   (a) a slot with the message, and\r
        (b) a request to the server\r
 \r
+\subsection{Server Algorithm}\r
+\begin{algorithmic}[1]\r
+\Function{Server}{$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 = latest sequence number 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{// 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 := \{Slot_{s}, Slot_{s+1}, \dots, Slot_{t_n}\} \forall Slot_i \in Q$\r
+\Else\r
+\State $Data := \emptyset$\r
+\EndIf\r
+\ElsIf{$m = write$}\r
+\If{$s = t_n + d$ \textbf{and} $n \leq max$ \textbf{and} $Data.length = 1$}\r
+\State $newSlot := Data[1]$\r
+\If{$n = max$}\r
+\State $DeleteFirst(Q)$\r
+\Else\r
+\State // $n < max$\r
+\State $n := n + 1$\r
+\EndIf\r
+\State $Data := Append(newSlot,Q)$\r
+\Else\r
+\State $Data := \emptyset$\r
+\EndIf\r
+\ElsIf{$m = resize$}\r
+\State $Data := Resize(max)$\r
+\EndIf\r
+\State \Return{$Data$}\r
+\EndFunction\r
+\end{algorithmic}\r
+\r
 \subsection{Formal Guarantees}\r
 \r
 \textit{To be completed ...}\r