text:
%\section{Impossibility of SNOW properties with two clients with restricted communication }\label{two-client}
\section{Two Client Open Question}
\label{sec:2c2s}
This section closes the open question of whether SNOW properties can be implemented with two clients. We first prove that SNOW remains impossible in a 2-client 2-server system if the clients cannot directly send messages to each other.
% We prove our result by showing
 %a contradiction.
 However, in the presence of client to client communication, it is possible to have all SNOW properties with two clients and at least two servers.
 %Fig~\ref{fig:architecture2a}.

 \subsection{No  SNOW Without C2C  Messages}
 \label{subsec:no_snow_no_c2c}

 In this section, we prove the following results that states it is impossible guarantee the SNOW properties in a transaction processing system with two clients, without client-to-client communication.
  \begin{theorem}\label{thm:two-snow}
  	The SNOW properties cannot be implemented in a system with two clients and two servers, where the clients do not communicate with each other.
  \end{theorem}

 We use the same system model as in Section~\ref{sec:formal_proof}: two servers $s_x$ and $s_y$ with two clients, a reader $r_1$ that issues only
\rots{} and a writer $w$ that issues only \wots{}. A \wot{} $W$ writes $(x_1, y_1)$ to $s_x$ and $s_y$, and a \rot{} $R$ reads both servers. We assume that there is a bi-directional communication channel between any pair of client and server and any pair of servers. There is no communication channel between clients. We assume that each transaction can be identified by a unique number, e.g., transaction identifier.

%We denote the automata for servers $s_x$ and $s_y$ by $s_x$ and $s_y$, respectively, and the automata for the clients  $r$ and $w$ by $r$ and $w$, respectively.
 %We denote by $S_1$  the subsystem consisting of $s_x$, $s_y$ and $w$,  and  by $S_1$  the  automata composed of  $s_x$, $s_y$ and $w$, i.e., $s_x \times s_y \times w$.
 %Also, we  denote by $\mathcal{A}$, which can also be interpreted as the algorithm, the automaton representing the entire system consisting of $S_1$ and $r$ (i.e., $s_x \times  s_y$ $ \times w$ $ \times r$).
% We assume that between any client $c$,
 %$c \in \{r, w \}$ and any server $s$,  $s \in \{s_x, s_y\}$ there are  channel automata $Channel_{c, s}$ and $Channel_{s, c}$.
%Again, with abuse of notation we denote by $\mathcal{S}$ the automata composed of the automatons $s_x$, $s_y$ and $w$. Also, by $\mathcal{T}$ we denote the composition of automaton $\mathcal{S}$ and $r$, i.e., represents the entire system.
%We used the notation $\writeop{o}{v}$ to mean a write operation with value $v$ on object $o$; and similarly, by $\readop{o}$ we mean a read operation on $o$.
%We  denote by $S_2$ the system, and also the  composed automaton,  consisting of  $s_x$, $s_y$, $r$ and  $w$, by composing the automatons $S_1$ and $r$, i.e., the automaton $S_1 \times r$.
%We assume that clients are non-faulty.
%Here, we consider only   executions of some algorithm ${\mathcal A}$ that satisfied SNOW properties.
%For contradiction, we  also assume that  any execution of $\mathcal{A}$  respects  the SNOW properties.
% Also, we assume that in an execution $\epsilon$ of $\mathcal{A}$  we can identify each transaction with a unique identifier.

%\sloppy Consider an execution of ${\mathcal A}$ with  two transactions in it as:   a \wot{}  $W \equiv $ $WRITE($$ (o_1, x_1),  (o_2, y_1) )$ invoked by  $w$, where $x_1 \neq x_0$ and $y_1 \neq y_0$; and a \rot{}   $R \equiv READ$$(o_1, o_2)$, invoked by $r_1$.
%Let us denote by
%$op_x^{r_1}$ and $op_y^{r_1}$  the read operations $\readop{o_1}$ and  $ \readop{o_2} $, respectively.
%Due to the wait-free requirement for  the \wots{}, $W$ completes, and we denote by $\INV{W}$ the invocation action and $\RESP{W}$ the response action in $\alpha$.
%
%\paragraph{Notations and Definitions:}
%We  introduce  the following notations and definitions in the context of an execution $\epsilon$, of $\mathcal{A}$, with transactions $R_1$ and $W$ in it.
%
%\begin{notation}
%We introduce the following notations for   actions relevant to $R$ in $\epsilon$,
% where  $ j \in \{1, 2\}$:
%\begin{enumerate}
%\item $\INV{R}$ and  $\RESP{R}$:  invocation and  response actions for  $R$,  at  $r$;
%\item $\INV{W}$ and   $\RESP{W}$: invocation and  response actions for  $W$, at $w$;

%\item $\send{m_j^{r}}{r, s_j}$: an  output action at $r$,  which sends a message $m_j^{r}$ from reader $r$ to server $s_j$, requesting the value for $o_j$;
%\item $\recv{m_j^{r}}{r, s_j}$: an input action at $s_j$, that receives the message $m_j^{r}$, sent from $r$;
%\item $\send{v_j}{ s_j, r}$: an output action at $s_j$,  that  sends value $v_j$, for   $o_j$, to $r$.
%\item $\recv{v_j}{ s_j, r}$: an input action at $r$,  to receive a message $v_j$ from $s_j$ at  $r$.
%
%\end{notation}
%
%\begin{definition}
%\item  \emph{Non-blocking fragments $\frag{i}{\epsilon}$, $i \in \{1, 2\}$.}
 %Suppose there is a fragment of  execution  in $\epsilon$  where the first action is   $recv(m_i^r)_{r, s_i}$ and  the last action is
 %$send(v_i)_{s_i, r}$ , both of which  occur  at $s_i$. Moreover, suppose there is
% no other input action at $s_i$ in this fragment. Then we call this execution fragment
  % a \emph{non-blocking response fragment} for $op_i^r$ at  $s_i$.  We use the notation  $\frag{i}{\epsilon}$ to denote this fragment of
  %execution of $\epsilon$. %Similarly, if such an execution fragment occurs  with $m_y^r$, $y$ and $s_y$ then we denote this by  $\frag{1,y}{\epsilon}$ and refer to it as a non-blocking response fragment for $op_2^r$ at  $s_y$.
 %\end{definition}

%\begin{notation}
 %\item  We use the notations $R(\epsilon)$ and $W(\epsilon)$ to denote the transactions $R$ and $W$, in $\epsilon$. When the underlying execution is clear from the context we simply use $R$ and $W$.
%\end{notation}

%\begin{notation}
% \item If the non-blocking fragment $\frag{1,x}{\epsilon}$ appears in $\epsilon$ such that $recv(m^{r_1}_2)_{r, s_y}$, at $s_y$,  does not occur before
% $\frag{1,x}{\epsilon}$ completes and $\epsilon$ is of the form
% $\finiteprefix{\ell-1}{\ell} \circ \frag{1,x}{\epsilon} \circ \frage{S}{\epsilon}{}$, where
%$\frage{S}{\epsilon}{}$ is any continuation of the execution, then we denote $\finiteprefix{\ell-1}{\ell} $ by $\prefix{\epsilon}$.

%\item \sloppy If $\epsilon$ is of the form
% $\finiteprefix{\ell-1}{\ell}  \circ \frag{1,x}{\epsilon} \circ \kappa \circ \frag{1,y}{\epsilon} , a_p, \sigma_p, \ldots$  or
% $\finiteprefix{\ell-1}{\ell}  \circ \frag{1,y}{\epsilon} \circ \kappa \circ \frag{1,x}{\epsilon} \circ \frage{S}{\epsilon}{}$, where
% $\ell$ is a positive integer,
% $\kappa$ is a segment of $\epsilon$,  possibly even of length zero and $\frage{S}{\epsilon}{}$ is any suffix part of the execution
% then we denote $\finiteprefix{\ell-1}{\ell} $ by $\prefix{\epsilon}$. Clearly,  we can write $\epsilon$ as $\prefix{\epsilon} \circ \frag{1,x}{\epsilon}\circ \kappa \circ \frag{1,y}{\epsilon} \circ \suffix{\epsilon}$ or $\prefix{\epsilon} \circ \frag{1,y}{\epsilon}\circ \kappa \circ \frag{1,x}{\epsilon} \circ \suffix{\epsilon}$.
%\end{notation}
%\end{enumerate}

 %However, unlike in the case of \rots{}, for \wots{} the SNOW properties do not impose strict conditions on the occurrence of external events at the clients or the servers.
%However,  the  W property guarantees termination of any \wot{}. Therefore, all we can claim is  $\RESP{W}$ eventually appears after  $\INV{W}$.

Our strategy is still proof by contradiction: We assume there exists some algorithm $\mathcal{A}$ that satisfies all SNOW properties, and then we show the existence of a sequence of executions of $\mathcal{A}$, eventually leading to an execution that contradicts  the S property.
 %If $\epsilon$ is an execution of $\mathcal{A}$, with \rot{} $R$.
%  We denote by  $\frag{1,x}{\epsilon}$ and $\frag{1,y}{\epsilon}$  the execution fragments of $\epsilon$  between  the actions $recv(x)_{ s_x, r}$ and  $send(m_x^r)_{r, s_x}$ at $s_x$; and   $recv(x)_{ s_x, r}$ and  $send(m_y^r)_{r, s_y}$ at $s_y$, respectively, and in  $\frag{1,x}{\epsilon}$ and $\frag{1,y}{\epsilon}$  no other internal actions occur at $s_x$ and $s_y$, respectively.
 First,  we show the existence of an execution $\alpha$ of $\mathcal{A}$ where
$R_1$ is invoked after $W$ completes, where the  send actions $send(m_x^{r_1})_{r_1, s_x}$ and $send(m_y^{r_1})_{r_1, s_y}$  at the  $r_1$  occur consecutively
in  $P(\alpha)$, which is a prefix of $\alpha$.
 Then we show that $\alpha$  can be written in the form
$\prefix{\alpha} \circ \frag{1,x}{\alpha}$ (Fig.~\ref{fig:execution1} $(a)$, Lemma~\ref{lem:exec_alpha}).
%\delete{where  the receive and response occurs at $s_x$ without any input action at $s_x$ between these two actions (Fig.~\ref{fig:execution1} $(a)$). }
 We then prove the existence of  another  execution $\beta$, which can be written in the form $\prefix{\beta} \circ \frag{1,x}{\beta} \circ \frag{1,y}{\beta}$ by extending $\alpha$ with an execution fragment $\frag{1,y}{\beta}$, such that $\frag{1,x}{\beta} \stackrel{s_x}{\sim} \frag{1,x}{\alpha}$
  (Fig.~\ref{fig:execution1} $(b)$; Lemma~\ref{lem:exec_beta}).
Note that in  any arbitrary extension of $\beta$, $R_1$ eventually returns $(x_1, y_1)$.
  %
Next, we show the existence of an execution $\gamma$ of the form  $\prefix{\gamma} \circ \frag{1,x}{\gamma} \circ \frag{1,y}{\gamma}$,
 where the send actions $send(m_x^{r_1})_{r_1, s_x}$ and $send(m_y^{r_1})_{r_1, s_y}$  at  $r_1$ occur before $W$ is invoked (Fig.~\ref{fig:execution1} $(c)$; $\gamma$), but
$\frag{1,x}{\gamma}$  and $\frag{1,y}{\gamma}$
occur after $\RESP{W}$ as in $\beta$.
%
%
Based on $\gamma$, we show the existence of an execution $\delta$
of the form  $\prefix{\eta} \circ \frag{1,x}{\eta} \circ \frag{1,y}{\eta}\circ \suffix{\eta}$, where
  $R_1$ responds with $(x_1, y_1)$.
%
 %of $\mathcal{A}$ such that, $R$ is invoked before $W$ is invoked and $R$ completes after $W$.
 % Additionally, in $\beta$ the servers
  %$s_x$ and $s_y$ receive the object value requests from $r$ after $W$ completes and $R$ responds with $(x_1, y_1)$
   %From $\gamma$, we show the existence of an execution  $\eta$ of $\mathcal{A}$ where $F_1$ occurs before $F_2$,   and eventually  $R$ responds with $(x_1, y_1)$.
   %
    Finally, starting with  $\eta$, we create a sequence of executions $\delta (\equiv \eta)$, $\delta^{(1)}$, $\cdots$ $\delta^{(f)}$, of $\mathcal{A}$,
     where in each of them $R_1$ responds with $(x_1, y_1)$  (Fig.~\ref{fig:execution2} $(e)$ and $(g)$; Lemma~\ref{thm:two-snow}). Additionally,  for any $\delta^{(i)}$, the fragments   $\frag{1,x}{\delta^{(i)}}$ and
    $\frag{1,y}{\delta^{(i)}}$  appear before $\delta^{(i-1)}$.
    % i.e., $\prefix{\delta^{(i)}}$ is a prefix of $\prefix{\delta^{(i-1)}}$.
    Based on $\delta^{(f)}$, we prove the existence of an execution $\phi$ (Fig.~\ref{fig:execution2} $(h)$), where $R_1$ returns
    $(x_1, y_1)$ even before $W$ begins, which violates the $S$ property.

  Now, we explain the relevant lemmas used by the main proof. Due to space constraints, we present their proof in Appendix~\ref{app:2c-no-c2c}. The first lemma states that there exists a finite execution of ${\mathcal A}$, where $R_1$ begins after
  $W$ completes, and the actions $send(m_x^{r_1})_{r_1, s_x}$ and $send(m_y^{r_1})_{r_1, s_y}$  occur
before either of the servers $s_x$ and  $s_y$
  receives $m_x^{r_1}$ or $m_y^{r_1}$ from $r_1$;  also,  server $s_x$ responds to $r_1$ in a non-blocking manner (execution $\alpha$ in Fig.~\ref{fig:execution1}).
\begin{lemma}\label{lem:exec_alpha}
There exists a finite execution $\alpha$ of $\mathcal{A}$ that contains transactions $R_1(\alpha)$
 and $W(\alpha)$ where $\INV{R}$ appears after $\RESP{W}$, and the following conditions hold:
\begin{enumerate}
\item[$(i)$] The actions $send(m_x^{r_1})_{r_1, s_x}$ and  $send(m_y^{r_1})_{r_1, s_y}$ appear consecutively in $trace(\alpha)|r_1$; and
\item[$(ii)$]   $\alpha$ contains the execution fragment  $\frag{1,x}{\alpha}$.
%, i.e., the actions  $recv(m_x^r)_{r, s_x}$ and  $send(x)_{r, s_x}$ appear in $trace(\alpha)|s_x$, where  there is no input action of  $s_x$  between these actions.
% \item[$(ii)$]  $R(\alpha)$ returns  $(x_1, y_1)$.
\end{enumerate}
\end{lemma}

\remove{
\begin{proof}
Consider a finite  execution fragment  of $\mathcal{A}$ with a completed transaction $W$, where  after $W$
completes  the adversary invokes $R$, i.e., $\INV{R_1}$ occurs.
 Note that each of the  read operations $op_1^{r_1}$ and $op_2^{r_1}$,  in $R_1$,  can be invoked by the adversary at any point in the execution.
 Following $\INV{R}$,  the adversary introduces the invocation action $\inv{op_1^r}$;  by the O property of the read operations of $\mathcal{A}$
the action $send(m_x^{r_1})_{r_1, s_x}$ eventually occurs. Next, the adversary introduces
 $\inv{op_2^{r_1}}$ and also, delays the arrival of  $m_x^{r_1}$ until  action $send(m_y^{r_1})_{r_1, s_y}$ eventually occurs,
 which  must occur in accordance with  the property O  of read operations. Let us call this finite execution $\alpha^0$.

 Next, suppose at the end of $\alpha^0$  the adversary delivers the message $m_x^{r_1}$, which has been delayed so far,
 via the action  $recv(m_x^{r_1})_{r, s_x}$,
 at  $s_x$,   but  it delays any  other input actions at $s_x$. Note that by the $N$ property of read operations $s_x$ eventually responds with  $send(x)_{s_x, r_1}$, with one value $x$ by o property,  where $x = x_1$ by the S property, since $R$ begins after $W$ completes.
 Let us call this execution $\alpha$. Note that $\alpha$ satisfies conditions $(i)$ and $(ii)$ by the design of the execution.
\end{proof}
}

% The following lemma states that starting from execution $\beta$ we show that there exists an execution of ${\mathcal A}$ such that $R$ initiates after $W$ completes  such that,  the send events from the reader occur first (see execution $\beta$ in Fig.~\ref{fig:execution1} $(b)$).
 %
 %{If $\alpha$ is an execution of $\mathcal{A}$, with \rot{} $R$. We denote by  $\frag{1,x}{\alpha}$ and $\frag{1,y}{\alpha}$  the execution fragments of $\alpha$  between  $recv(x)_{ s_x, r}$ and  $send(m_x^r)_{r, s_x}$ at $s_x$; and   $recv(x)_{ s_x, r}$ and  $send(m_y^r)_{r, s_y}$ at $s_y$, respectively. During  $\frag{1,x}{\alpha}$ and $\frag{1,y}{\alpha}$ no other internal actions occur at $s_x$ and $s_y$, respectively.}

   The following lemma states that there is an execution $\beta$ where $R$ begins after  $W$ completes, and the two send events at $r_1$ occurs before  $\frag{1,x}{\beta}$, which thus occurs before $\frag{1,y}{\beta}$ ($\beta$ in Fig.~\ref{fig:execution1}).

\begin{lemma}\label{lem:exec_beta}
There exists an  execution $\beta$ of $\mathcal{A}$ that contains transactions $R_1$ and $W$ where $\INV{R_1}$ appears after $\RESP{W}$ and the following conditions hold:
\begin{enumerate}
\item[$(i)$] The actions $send(m_x^{r_1})_{r_1, s_x}$ and  $send(m_y^{r_1})_{r_1, s_y}$ appear consecutively in $trace(\beta)|r_1$; and
\item[$(ii)$]   $\beta$ contains the execution fragment  $\frag{1,x}{\beta} \circ \frag{1,y}{\beta}$.
% $recv(m_x^r)_{r, s_x}$,  $send(x)_{r, s_x}$,  $recv(m_y^r)_{r, s_y}$,  $send(y)_{r, s_y}$, where  there is no external action, in $\beta$,  of  $s_x$ and $s_y$ between these actions.
% \item[$(iii)$] $R(\beta)$ returns $(x_1, y_1)$.
\end{enumerate}
\end{lemma}
\remove{
\begin{proof}
Consider the  execution $\alpha$ of $\mathcal{A}$ as constructed in Lemma~\ref{lem:exec_alpha}.
At the end of the execution fragment $\alpha$,  the adversary  delivers the previously delayed message
 $m_y^r$, which is sent via the action $send(m_y^r)_{r, s_y}$,  by  introducing the action $recv(m_y^r)_{r, s_y}$. The adversary then delays any other  input action in $\mathcal{A}$. By the N property,
server $s_y$ must respond to $r$, with some value $y$,  and hence
the output action $send(y)_{s_y, r}$ must eventually occur at $s_y$.
Let us call this finite execution as $\beta$. Note that $\beta$ satisfies the  properties $(i)$ and $(ii)$ in the statement of the lemma.
\end{proof}
}

 The following result shows  that starting with $\beta$  there is an execution
 $\gamma$, where  $R_1$ is invoked before $W$ is invoked while
  $send(m_x^{r_1})_{r_1, s_x}$ and  $send(m_y^{r_1})_{r_1, s_y}$  occur before $\INV{W}$ (Fig.~\ref{fig:execution1} $(c)$) and $m_x^{r_1}$ and $m_y^{r_1}$ from $r_1$ reach $s_x$ and $s_y$ after the action  $\RESP{W}$.

\begin{lemma}\label{lem:exec_gamma}
There exists an execution $\gamma$ that contains $R_1$ and $W$, where the action $\INV{R_1}$ appears before $\INV{W}$ and $\RESP{R_1}$ appears after  $\RESP{W}$, and the following conditions hold for $\gamma$:
\begin{enumerate}
\item[$(i)$] The actions $send(m_x^{r_1})_{r_1, s_x}$ and  $send(m_y^{r_1})_{r_1, s_y}$  appear before $\INV{W}$ and they appear consecutively in $trace(\gamma)|r_1$;
%\item[$(ii)$]   $trace(\beta)$ contains the sequence  $recv(m_x^r)_{r, s_x}$,  $send(x)_{r, s_x}$,  $recv(m_y^r)_{r, s_y}$,  $send(y)_{r, s_y}$.
\item[$(ii)$]   $\gamma$ contains the execution fragment  $\frag{1,x}{\gamma} \circ \frag{1,y}{\gamma}$; and
\item[$(iii)$] action $\RESP{W}$ occurs before $\frag{1,x}{\gamma}$.
\end{enumerate}
\end{lemma}

\remove{
\begin{proof}
Consider the execution $\beta$ of $\mathcal{A}$  as in Lemma~\ref{lem:exec_beta}. Note that $\beta$
is an execution of the composed automaton $\mathcal{A}$ ($\equiv S_1 \times r$).  In $\beta$,  the actions
 $send(m_x^r)_{r, s_x}$ and   $send(m_y^r)_{r, s_y}$ occur at $r$; and following that,  the actions
 $recv(m_x^r)_{r, s_x}$, $recv(m_y^r)_{r, s_y}$, $send(x)_{s_x, r}$ and  $send(y)_{s_y, r}$ occur at $S_1$.
 Consider the executions $\alpha_r \equiv \beta|r$ and  $\alpha_{S_1} \equiv \beta|S_1$. Let $s_{\beta}$ denote  $trace(\beta)$.

 In $s_{\beta}$, $send(m_x^r)_{r, s_x}$,  $send(m_y^r)_{r, s_y}$ appear after $\RESP{W}$, as in $trace(\beta)$. Let $s'_{\beta}$ be the sequence of
 external actions of $S_2$ which we construct from $s_{\beta}$ by moving $send(m_x^r)_{r, s_x}$,  $send(m_y^r)_{r, s_y}$ before $\INV{W}$, which  is also
 an external action of $\mathcal{A}$, and leaving the rest of the actions in $s_{\beta}$ as it is.

 In $\beta$,  $\INV{R}$, $recv(x)_{ s_x, r}$ and  $recv(y)_{s_y, r}$
  are the only input actions at $r$, therefore,   $s'_{\beta} |r= trace(\alpha_r)$.
  %
  On the other hand,  $recv(m_x^r)_{r, s_x}$, $recv(m_y^r)_{r, s_y}$ are the only input actions at $s_x$ ,
   therefore, $s'_{\beta} |S_1 = trace(\alpha_{S_1})$.  Now, by Theorem ~\ref{thm:paste}, there exists an execution
 $\gamma$ of $\mathcal{A}$ such that, $s'_{\beta} = trace(\gamma)$
 and $\alpha_r = \gamma|r$ and $\alpha_{S_1} = \gamma|S_1$. Therefore,
 in $\gamma$, $send(m_x^r)_{r, s_x}$,  $send(m_y^r)_{r, s_y}$ appear before
  $\INV{W}$ (condition $(i)$) and since $s'_{\beta} = trace(\gamma)$ condition $(ii)$  holds. Conditions $(iii)$ holds trivially.
\end{proof}
}

\remove{
In the following lemma we show  that in any   execution, of ${\mathcal A}$,  that is  an extension of either execution $\beta$ or execution  $\gamma$, as in  the preceding lemmas, $R_1$ eventually returns $(x_1, y_1)$.

\begin{lemma}\label{lem:exec_xi}
Let $\xi$  be an execution of $\mathcal{A}$ that is an   extension of the either  execution $\beta$ from Lemma~\ref{lem:exec_beta} or execution  $\gamma$ from Lemma~\ref{lem:exec_gamma},  then  $R(\xi)$  responds with $(x_1, y_1)$.
\end{lemma}

\begin{proof}
Note that in executions $\beta$ and $\gamma$,  the traces $trace(\beta)|s_x$  is a prefix of $trace(\gamma)|s_x$, since  $\beta$ ends with
$\frag{1,x}{\beta}$ and $\gamma$ ends with $\frag{1,y}{\gamma}$
Therefore, in both $\beta$ and $\gamma$, the  respective $send(x)_{s_x, r}$ actions have the same value for their  $x$'s.
Now, in  any extended  execution $\eta$ of $\mathcal{A}$, which starts
with $\beta$ or $\gamma$, by the properties $N$ and $O$ the transaction $R$ completes;  and  by the property $S$,   $R$ returns  $(x_1, y_1)$.
Therefore,  $R_1(\xi)$  returns $(x_1, y_1)$.
\end{proof}
}

 In the following lemma, we show there exists an    execution $\eta$  of
$\mathcal{A}$  of the form
$\prefix{\eta}\circ \frag{1,x}{\eta} \circ \frag{1,y}{\eta} \circ \suffix{\eta}$
where  $\RESP{R}$ appears in  $\suffix{\eta}$  (Fig.~\ref{fig:execution1} $(d)$) and
$R(\eta)$ returns $(x_1, y_1)$.

\begin{lemma}\label{lem:exec_delta}
There exists an execution $\eta$ of $\mathcal{A}$ that contains transactions $R$ and $W$ where $\INV{R}$ appears before $\INV{W}$;  $\RESP{R_1}$ appears after  $\RESP{W}$ and the following conditions hold for $\eta$:
\begin{enumerate}
\item[ $(i)$] $\eta$ can be written in the form $\prefix{\eta}\circ \frag{1,x}{\eta} \circ \frag{1,y}{\eta} \circ \suffix{\eta}$, for some
   $\prefix{\eta}$ and $\suffix{\eta}$;
\item[$(ii)$] The actions $send(m_x^r)_{r_1, s_x}$ and  $send(m_y^{r_1})_{r_1, s_y}$
appear before  $\INV{W}$ and they appear consecutively in $trace(\eta)|r_1$;
\item[$(iii)$] action $\RESP{W}$ occurs before $\frag{1,x}{\eta}$; and
 \item[$(iv)$] $R_1(\eta)$ returns $(x_1, y_1)$.
\end{enumerate}
\end{lemma}

\remove{
\begin{proof}
Let $\gamma$ be an execution of $\mathcal{A}$, as described in Lemma~\ref{lem:exec_gamma}.
%Without loss of generality, suppose   $recv(m_x^r)_{r, s_x}$ occurs in $\gamma$ before  $recv(m_y^r)_{r, s_y}$.
 Let $\gamma^0$ be the execution fragment of $\gamma$
up to the action $send(y)_{s_y, r}$. Now, by Theorem~\ref{thm:extension} (1), there exists an execution $\gamma^0 \circ \mu$, of
$\mathcal{A}$, where $\mu$ denotes the extended portion of the execution.

% with the empty sequence for $\beta$, in the theorem statement.  Now, due to the N and O properties of an execution of $\mathcal{A}$ the
%action $send(x)_{r, s_x}$ occurs in $\gamma^0 \circ \mu$ (in $\mu$, to be precise).
%Let $\mu^0$ be the prefix of $\mu$ with its last output action as  $send(x)_{r, s_x}$. Again, using Theorem~\ref{thm:extension} (3), with $\beta$ consisting of only $recv(m_y^r)_{r, s_y}$, we create an execution of $\mathcal{A}$ that starts with $\gamma^0 \circ \mu^0$.
 Clearly, by the N and O properties,
%executions of $\mathcal{A}$
the actions  $\resp{op_1^r}$ and $\resp{op_2^r}$ must eventually occur in $\gamma^0 \circ \mu$.
%We can write $\nu$ as $\nu^0\circ \eta^0$ such that it ends with the action  $send(y)_{r, s_y}$.
 Now,  identify $\eta$ as $\gamma^0 \circ \mu$,  where $\prefix{\eta} \circ \frag{1,x}{\eta} \circ \frag{1,y}{\eta}$  is $\gamma^0$,   and $\mu$ is $\suffix{\eta}$, thereby, proving condition $(i)$.

Note the condition $(ii)$ is satisfied by $\eta$ because $\RESP{W}$ appears in $\prefix{\eta}$, therefore, the execution $\gamma$ is equivalent to the execution fragment of $\prefix{\eta}$ up to the event $\INV{W}$, and  also,
$\gamma$ satisfies condition $(ii)$ as stated in Lemma~\ref{lem:exec_gamma}.

Condition $(iii)$ is true because $\frag{1,x}{\eta}$ begins with action $recv(m_x^r)_{r, s_x}$, which occurs after $\RESP{W}$.
Condition $(iv)$ is satisfied by $\eta$ because $\eta$ is an extension of $\gamma$ and due to  the result of Lemma~\ref{lem:exec_xi}.
\end{proof}
}

  %Next we define another execution fragment $\gamma$, of  $S_2$, as follows. Consider the execution fragment $\prefix{\alpha}{ \RESP{W}}$, i.e.,  up to the point in $\alpha$ when $W$ completes. Now we create an execution fragment $t$ of $S_2$, such that
  %$t|S_2 = \prefix{\alpha}{ \RESP{W}}$ and does not contain any output action of  $R$. Next we create execution fragment  $\gamma$ from $t$, by  adding action $\INV{R}$ at $r$ to $t$,  before $\INV{T_w}$,as in the case of $\beta$.

\remove{
  \begin{figure}[!ht]
      \centering
         %\includegraphics[scale=0.60]{figures/fig4.pdf}
         %KMK\includegraphics[width=4in]{figures/fig4.png}
         \vspace{-2.0em}
         \caption{
\small{Schematic representation of executions $\alpha$, $\beta$, $\gamma$ and $\eta$,
          of ${\mathcal A}$ with transactions $R$ and $W$. The executions evolve from left to right.
          The dots denote external events at clients.
          The up-arrow marks denote external actions at $s_x$. The down-arrow marks denote external actions at $s_y$.}} \label{fig:execution1}
 \end{figure}

\begin{figure}[!ht]
      \centering
         %\includegraphics[width=1.00\textwidth]{figures/fig5.pdf}
         %KMK\includegraphics[width=4in]{figures/fig5.png}
         \vspace{-2.0em}
        \caption{\small{Executions $\delta^{(k+1)}$, $\epsilon$, and $\delta^{(k)}$, which show a progressive sequence of executions that are built on execution $\eta$ in Fig.~\ref{fig:execution1}.}}
         %\caption{\small{From execution $\eta$ of $\mathcal{A}$,  the construction of the progressive sequence of executions
         %$\delta, \delta', \ldots$,  of  $\mathcal{A}$, of the form $\prefix{\cdot } \circ \frag{1,x}{\cdot}\circ \frag{1,y}{\cdot} \circ \suffix{\cdot}$.
%The final execution $\phi$ of $\mathcal{A}$ to contradict the S property.}}
      \label{fig:execution2}
\vspace{-1em}
 \end{figure}
}

\begin{figure*}[t]
	%\centering
	\hspace*{-0.7cm}
	\begin{subfigure}{0.49\textwidth}
		\centering
	\includegraphics[width=1.2\linewidth]{figures/fig4.png}
	\end{subfigure}
	\hspace*{0.0m}
	\begin{subfigure}{0.49\textwidth}
		\centering
	\includegraphics[width=1.2\linewidth]{figures/fig5.png}
	\end{subfigure}
	         \caption{
	         	\small{Schematic representation of executions $\alpha$, $\beta$, $\gamma$ and $\eta$,
	         		of ${\mathcal A}$ with transactions $R$ and $W$. The executions evolve from left to right.
	         		The dots denote external events at clients.
	         		The up-arrow marks denote external actions at $s_x$. The down-arrow marks denote external actions at $s_y$.}} \label{fig:execution1}
\end{figure*}

\remove{
\begin{figure}[t]
\centering
\begin{subfigure}{1.0\columnwidth}
\centering
  \includegraphics[width=1.0\linewidth]{figures/fig4-1.pdf}
\end{subfigure}
\begin{subfigure}{1.0\columnwidth}
\centering
  \includegraphics[width=1.0\linewidth]{figures/fig4-2.pdf}
\end{subfigure}
\begin{subfigure}{1.0\columnwidth}
\centering
  \includegraphics[width=1.0\linewidth]{figures/fig4-3.pdf}
\end{subfigure}

\caption{\small{try graphs}}
%% High level performance comparison between \eigermoon and Eiger with latency-throughput graph and comparisons on system overall throughput with varying degrees of skewness and write fractions.
%% Throughput comparison when varying system load and latency comparison of read-only transactions. Data staleness is measured by comparing \eigermoon to a linearizable baseline.}
\label{fig:latency}
\end{figure}
}

  The following proof proves Theorem~\ref{thm:two-snow}. In the proof we start with an execution $\eta$ and create a sequence of executions of
  $\mathcal{A}$, where each one is of the form $\prefix{\cdot} \circ \frag{1,x}{\cdot}\circ \frag{1,y}{\cdot}\circ \suffix{\cdot}$, with progressively shorter $\prefix{\cdot}$ until we have a final execution that contradicts the $S$ property.
\remove{
 \begin{theorem}\label{thm:two-snow}
 The SNOW properties cannot be implemented in a system with two clients and two servers, where the clients do not communicate with each other.
\end{theorem}
}

\begin{proof}
\sloppy Consider an execution $\delta^{(\ell)}$  of $\mathcal{A}$ as in Lemma~\ref{lem:exec_delta}, and let $\prefix{\delta^{(\ell)}}$  be the execution fragment
$\finiteprefix{\ell-1}{\ell}$.
%, where $\ell$ is some positive integer, and $\sigma_i$'s and $a_i$'s denote states and actions, respectively.
By  Lemma~\ref{lem:exec_delta}, $\RESP{R_1(\delta^{(\ell)})}$  returns
 $(x_1, y_1)$ and $\delta^{(\ell)}$ is also of the form
$\finiteprefix{\ell-1}{\ell} \circ \frag{1,x}{\delta^{(\ell)}} \circ \frag{1,y}{\delta^{(\ell)}} \circ \suffix{\delta^{(\ell)}}$.
%Below we will show that from $\delta$ we can create another execution $\delta^{(\ell-1)}$ of the form $\finiteprefix{\ell-2}{\ell-1} \circ \frag{1,x}{\delta^{(\ell-1)}} \circ \frag{1,y}{\delta^{(\ell-1)}} \circ \suffix{\delta^{(\ell-1)}}$ where   $\RESP{R(\delta^{(\ell-1)})}$  returns $(x_1, y_1)$. Note that $\prefix{\delta^{(\ell-1)}}$ ($\equiv  \finiteprefix{\ell-2}{\ell-1} $) is a prefix of $\prefix{\delta^{(\ell)}}$.

Next, we inductively prove the existence of a finite sequence of executions of $\mathcal{A}$---i.e., by proving the existence of a new execution based on the existence of a previous one---as $\delta^{(\ell)}, \delta^{(\ell-1)}, \cdots \delta^{(i)}, \delta^{(i-1)},  \cdots \delta^{(f)}$,
for some positive integer $f$, with the following properties: $(a)$ Each of the execution in
the sequence can be written in the form  $\finiteprefix{i-1}{i} \circ \frag{1,x}{\delta^{(i)}} \circ \frag{1,y}{\delta^{(i)}} \circ \suffix{\delta^{(i)}}$ (or $\prefix{\cdot}\circ \frag{1,x}{\cdot}\circ \frag{1,y}{\cdot}\circ\suffix{\cdot}$); $(b)$ for each $i$, $f \leq i  < \ell$, we have  $\prefix{\delta^{(i)}}$ to be a prefix of $\prefix{\delta^{(i+1)}}$; and $(c)$ $R_1(\delta^{(f)})$  returns  $(x_0, y_0)$, and for any $i$,  $f <  i \leq \ell$,  we have   $R_1(\delta^{(i)})$  that returns  $(x_1, y_1)$.  Note that there is a final execution of the form $\delta^{(f)}$  because of the initial values of $x_0$ and $y_0$  and the \wot{}  $W$.

%and $(d)$  the $\frag{1,x}{\delta^{(f)}}\circ \frag{1,y}{\delta^{(f)}}$   occurs before $\INV{W}$ in $\delta^{(f)}$.

%The claims $(a)$, $(b)$ and $(c)$ is due to Lemma~\ref{two:induction}, and $(d)$ follows from the fact that $\prefix{\delta^{(\ell)}}$ is a finite prefix.

%\end{proof}

%\begin{proof}
 %Consider  $\delta$ which is of the form
%$\finiteprefix{k}{k +1} \circ \frag{1,x}{\delta} \circ \frag{1,y}{\delta} \circ \suffix{\delta}$, where   transaction
%$R(\delta)$ responds with
%$(x_1, y_1)$.
Clearly, there exists an integer $k$,  $ f \leq  k < \ell$, such that $\frage{R}{\delta^{(k)}}{}$ returns $(x_0, y_0)$ and $\frage{R_1}{\delta^{(k+1)}}{}$ returns $(x_1, y_1)$. Now we start with execution
$\delta^{(k+1)}$ and construct an execution $\delta^{(k)}$ as described in the rest of the proof. The following argument will show that  $\frage{R}{\delta^{(k)}}{}$ must also return $(x_1, y_1)$, which contradicts the assumption of having the $S$ property.

Consider the execution $\delta^{(k+1)}$ of the form
$\finiteprefix{k}{k +1} \circ \frag{1,x}{\delta^{(k+1)}} \circ \frag{1,y}{\delta^{(k+1)}} \circ \suffix{\delta^{(k+1)}}$.
 The action  $a_{k+1}$ can  occur at any of the automata $r$, $w$, $s_x$, and $s_y$. Therefore, we consider the following four possible cases.
%

\emph{ \underline{Case (i) $a_{k+1}$ occurs at $w$:}} The execution fragments
 $\frag{1,x}{\delta^{(k+1)}}$ and $\frag{1,y}{\delta^{(k+1)}}$ do not contain any input action  at $s_x$ or $s_y$. $a_{k+1}$ does not occur at $s_x$ or $s_y$.
 %Therefore, the action $a_{k+1}$ cannot have any impact on them.
 Therefore,
 the asynchronous network can
  delay the occurrence of $a_{k+1}$ at $w$ to create the
   finite execution
$\finiteprefix{k-1}{k } \circ \frag{1,x}{\delta^{(k+1)}} \circ \frag{1,y}{\delta^{(k+1)}}$,
 of. Also, there exists an execution $\delta^{(k)}$ that
 is an extension of the above finite execution, where $R_1$ completes in $\delta^{(k)}$.
%
  Clearly, $\delta^{(k)}$ can be written as
 $\finiteprefix{k-1}{k } \circ \frag{1,x}{\delta^{(k)}} \circ \frag{1,y}{\delta^{(k)}} \circ \suffix{\delta^{(k)}}$, where $ \suffix{\delta^{(k)}}$ is the tail of the execution resulting from the extension. Moreover,
  $\frag{1,x}{\delta^{(k+1)}}$   is indistinguishable  from
  $\frag{1,x}{\delta^{(k)}}$ at $s_x$, i.e.,
      $\frag{1,x}{\delta^{(k+1)}} \stackrel{s_x}{\sim} \frag{1,x}{\delta^{(k)}}$.
% \footnote{We drop the superscript $A$, such as $s_x$ to $s_x$,  from the symbol above $\sim$ for formatting reasons, when necessary.}
   Therefore, $send(x)_{s_x, r_1}$ has the same object value
   $x$ in both fragments, which means $R_1$ returns $x_1$, and thus $R_1(\delta^{(k)})$ must return $(x_1, y_1)$ by the property $S$.
   % By the liveness property of a \rot{},  deduced from  O and N properties of the underlying read operations,  $R$ completes in $\delta'$.

\emph{ \underline{Case (ii) $a_{k+1}$ occurs at $r$:}} Similar to Case $(i)$.

\emph{ \underline{Case (iii) $a_{k+1}$ occurs at $s_x$:}} Observe that the two execution fragments
   $a_{k+1} \sigma_{k+1} \circ \frag{1,x}{\delta^{(k+1)}}$ and $\frag{1,y}{\delta^{(k+1)}}$ occur at separate  automata, i.e., at $s_x$ and $s_y$ respectively.
    Also, the  execution fragments  $a_{k+1} \sigma_{k+1} \circ \frag{1,x}{\delta^{(k+1)}}$ and $\frag{1,y}{\delta^{(k+1)}}$ do not contain any  input actions at $s_x$ or $s_y$.
    Therefore,
    %by Claim~\ref{claim:reorder},
    we can create an execution $\epsilon$, which  can be expressed as
    $\finiteprefix{k-1}{k }  \circ \frag{1,y}{\epsilon}\circ a_{k+1}, \sigma_{k+1} \circ \frag{1,x}{\epsilon} \circ \suffix{\epsilon}$. Clearly,
     $\frag{1,x}{\epsilon} \stackrel{s_x}{\sim} \frag{1,x}{\delta^{(k+1)}}$ and
     $\frag{1,y}{\epsilon} \stackrel{s_y}{\sim} \frag{1,y}{\delta^{(k+1)}}$.
     %
     %
     %$\suffix{\epsilon} \stackrel{s_y}{\sim} \suffix{\delta}$.
   %
%Below we argue that  we can create the execution $\epsilon$, of ${\mathcal A}$, where the two fragments are swapped with respect two their ordering in $\delta$.
% If there are no output actions in the fragments then we can simply use the result Claim~\ref{claim:reorder} to swap
 % the fragments in the execution to create the new  trace and from this,  by using Theorem~\ref{thm:trace} we create a new execution $\epsilon$. Otherwise,  in Theorem~\ref{thm:paste}  we consider sequence
 % of actions $\beta$, as defined in the lemma,  where output actions corresponding to the fragments are swapped and then by the %result of the lemma      we realize  the existence of the execution $\epsilon$.
  Because $send(x)_{s_x, r_1}$ occurs in both $\frag{1,x}{\epsilon}$ and
     $\frag{1,x}{\delta^{(k+1)}}$, it sends the same value $x_1$ to $r_1$. Therefore, $R$ returns $(x_1, y_1)$.

   Now let us denote the execution fragment  $\finiteprefix{k-1}{k }  \circ \frag{1,y}{\epsilon}$ by $\epsilon'$, which  is simply a finite prefix of $\epsilon$.
     Allowed by the asynchronous network, we append $recv(m_x^{r_1})_{r_1, s_x}$ to $\epsilon'$, and create a finite execution $\epsilon''$ as
        $\finiteprefix{k-1}{k }\circ \frag{1,y}{\epsilon''}, recv(m_x^{r_1})_{r_1, s_x}$, and delay any input action at $s_y$.
        %Now, by Theorem~\ref{thm:extension} (1), there exists

        Let $\epsilon'''$ be an extension of $\epsilon''$. Clearly,
             $\frag{1,y}{\epsilon'''} \stackrel{s_y}{\sim} \frag{1,y}{\epsilon''}$, and thus $send(y )_{s_y, r_1}$ sends the same value $y_1$ in $\epsilon''$ and $\epsilon'''$.
             By the $N$ property, $send(x)_{s_x, r_1}$ eventually occurs, and by the $O$ property $x$ is send to $r_1$. Therefore, $R_1$ completes in
$\epsilon'''$, which implies that
             $R(\epsilon''')$ must return $(x_1, y_1)$.

             Note that the execution fragment of $\epsilon'''$ has no input actions of $s_x$ between $ recv(m_x^{r_1})_{r_1, s_x}$ and $send(x)_{s_x, r_1}$, which can be identified as $\frag{1,x}{\epsilon'''}$. Therefore, $\epsilon'''$ can be written as      $\finiteprefix{k-1}{k }  \circ \frag{1,y}{\epsilon'''} \circ \frag{1,x}{\epsilon'''} \circ \suffix{\epsilon'''}$.

    Next, since $\frag{1,x}{\epsilon'''}$ and $\frag{1,y}{\epsilon'''}$ contain actions of different automata,
    %by  Claim~\ref{claim:reorder},
    we can create an execution prefix  $\epsilon^{(iv)}$ as
    $\finiteprefix{k-1}{k }  \circ \frag{1,x}{\epsilon^{(iv)}} \circ \frag{1,y}{\epsilon^{(iv)}}$,
     where
     $\frag{1,x}{\epsilon^{(iv)}}$ appears before $\frag{1,y}{\epsilon^{(iv)}}$. Next,
     % by using Theorem~\ref{thm:extension} $(1)$
     we create an execution $\delta^{(k)}$ as an extension of
       $\epsilon^{(iv)}$, which can be written   as $\finiteprefix{k-1}{k } \circ \frag{1,x}{\delta^{(k)}} \circ \frag{1,y}{\delta^{(k)}}\circ \suffix{\delta^{(k)}}$.
       Then by the $O$ and $N$ properties, $R_1$ completes in $\delta^{(k)}$.
       Since $\frag{1,x}{\epsilon^{(iv)}} \stackrel{s_x}{\sim} \frag{1,x}{\epsilon'''}$, $send(x)_{s_x, r_1}$ returns $x_1$ in $\epsilon^{(iv)}$.
    Similarly, because
      $\frag{1,x}{\delta^{(k)}} \stackrel{s_x}{\sim} \frag{1,x}{\epsilon^{(iv)}}$, $send(x)_{s_x, r_1}$ returns $x_1$ in $\delta^{(k)}$. So,
     $R_1(\delta^{(k)})$ returns $(x_1, y_1)$.
  %

\emph{ \underline{Case (iv) $a_{k+1}$ occurs at $s_y$:}} Because $a_{k+1}$ occurs at server $s_y$ and $\frag{1,x}{\delta^{(k+1)}}$ occurs at server $s_x$ (different automata),
%then by applying  Claim~\ref{claim:reorder}  as in the previous cases
we can create a new execution $\epsilon$ of $\mathcal{A}$ (Fig.~\ref{fig:execution2} $(f)$)  as
             $\finiteprefix{k-1}{k } \circ \frag{1,x}{\epsilon} \circ a_{k+1}, \sigma_{k+1} \circ
        \frag{1,y}{\epsilon}\circ \suffix{\epsilon}$, such that $\frag{1,x}{\epsilon} \stackrel{s_x}{\sim}\frag{1,x}{\delta^{(k+1)}}$, where
         $a_{k+1}, \sigma_{k+1} $
       occurs after $\frag{1,x}{\delta^{(k+1)}}$ and
         $R(\epsilon)$ returns $(x_1, y_1)$.

     Now, consider the finite execution   $\finiteprefix{k-1}{k }\circ \frag{1,x}{\epsilon}$ at the end of which we append $recv(m_y^{r_1})_{r_1, s_y}$ to create a finite execution of $\mathcal{A}$ as
        $\finiteprefix{k-1}{k }\circ \frag{1,x}{\epsilon}, recv(m_y^{r_1})_{r_1, s_y}$.
        %Now, by Theorem~\ref{thm:extension} (1),
        Then, there exists
        an execution $\epsilon'$ of $\mathcal{A}$, where
              the network delays the input actions at $s_y$. By the $N$ and $O$ properties, $send(y)_{s_y, r_1}$ occurs in $\epsilon'$. Clearly, since   $\frag{1,x}{\epsilon'} \stackrel{s_x}{\sim} \frag{1,x}{\epsilon}$, $send(x)_{s_x, r_1}$ sends the same value in $\epsilon$ and $\epsilon'$. Therefore,  $R_1$ returns $(x_1, y)$.

              In $\epsilon'$, we denote the fragment that begins with $recv(m_y^{r_1})_{r_1, s_y}$ and ends with
              $send(y)_{s_y, r_1}$ by $\frag{1,y}{\epsilon'}$ to have $\epsilon'$ as
              $\finiteprefix{k-1}{k } \circ \frag{1,x}{\epsilon'}  \circ
        \frag{1,y}{\epsilon'}$.
        %Now using Theorem~\ref{thm:extension} (1), we know
        Then, there exists
        an execution $\delta^{(k)}$ of $\mathcal{A}$, which is an extension of $\epsilon'$. Clearly, $\delta^{(k)}$ can be written as
     $\finiteprefix{k-1}{k }  \circ \frag{1,x}{\delta^{(k)}} \circ \frag{1,y}{\delta^{(k)}} \circ \suffix{\delta^{(k)}}$, where $\suffix{\delta^{(k)}}$ is the tail of the extended execution.  Clearly,  $\frag{1,x}{\delta^{(k)}} \stackrel{s_x}{\sim} \frag{1,x}{\epsilon'}$. Therefore,  $R_1(\delta^{(k)})$ returns $x_1$ in $\delta^{(k)}$, which implies $R_1(\delta^{(k)})$ must return $(x_1, y_1)$.
\end{proof}

\remove{

 \begin{figure}[!ht]
      \centering
         %kmk\includegraphics[width=0.50\textwidth]{figures/architecture3_1.png}  \vspace{-2.5em}
         \caption{
\small{The architecture of a typical web service with clients, servers, and
         % The external requests and responses  at the clients  to and from the end-users are represented as invocation and responses for the transaction.
         the communication channels, between every pair of processes, inside a datacenter is modeled as a collection of I/O automata. Note that, unlike the architecture in Fig.~\ref{fig:architecture2a}, in this setup there are communication channels between every pair of clients.}}
         \label{fig:architecture2c}
 \end{figure}

}


text:
\section{Debugging with GDB}

Use \textbf{bt} to get a backtrace.
Example:
\begin{verbatim}
#0  0x00007ffff48daf7c in std::string::assign(std::string const&) () from /usr/lib/gcc/x86_64-pc
-linux-gnu/4.7.3/libstdc++.so.6
Python Exception <type 'exceptions.IndexError'> list index out of range:
#1  0x00005555555925a7 in image_psb::ImageSolver::doImageDisplay (this=0x7fffffffcb40, mapFiles= std::map with 2 elements,
    sImageRoot="../test_media/") at /home/andesil/PSB/src/./image2.cpp:489
#2  0x0000555555591c99 in image_psb::ImageSolver::renderImages (this=0x7fffffffcb40, sImageRoot=
"../test_media/",
    vIf=std::vector of length 3, capacity 3 = {...}, cImagePath=0x55555563e50a "/image/") at /home/andesil/PSB/src/./image2.cpp:417
#3  0x0000555555585b4b in main (argc=5, argv=0x7fffffffd888) at /home/andesil/PSB/src/main.cpp:201
\end{verbatim}

Here, each number is called a \textit{frame}. You can inspect each frame by
typing ``\textbf{info frame \#n}'', where \#n is the number of the frame. To get a local
inspection (set scope), type ``\textbf{set frame \#n}''.
Then it makes more sense to type commands like ``\textbf{info locals}'' and ``\textbf{info args}''.

To only show some items in the backtrace, type ``\textbf{bt -n}'', where n is the number of
frames, from bottom that you want to include.

ext: tex

max_stars_repo_name: andsild/NotusVitae

max_issues_repo_name: andsild/NotusVitae

max_forks_repo_name: andsild/NotusVitae


text:
\section{API}
This section covers implementation details for the API of \serviceName.

\subsection{Backend Language}
ExpressJS was chosen to be the backend language of choice for \serviceName.  The reasons why are numerous:
\begin{itemize}
    \item written in JS
    \item simple, flexible, extensible
    \item "One language to rule them all"
\end{itemize}

\subsection{Authentication}
PassportjS will be used for Authentication.

\subsection{Routes}
At the very least, the necessary routes are:
\begin{itemize}
    \item login: goes through Instagram's auth flow
    \item query: takes in a query object, returns a list of users
\end{itemize}

\section{User Interface}
This section covers implementation details of the UI portion of \serviceName. \serviceName will primarily be web-based. ReactJS will be used as the UI framework. Rationale:
\begin{itemize}
    \item It is the framework I know best
    \item Fits into "one language to rule them all" paradigm
\end{itemize}

max_stars_repo_name: steevejoseph/phineas

max_issues_repo_name: steevejoseph/phineas

max_forks_repo_name: steevejoseph/phineas


text:
% \section{201812-2}

% \input{problem/15/201812-2-p.tex}

max_stars_repo_name: lxlonlyn/CSP-Project

max_issues_repo_name: lxlonlyn/CSP-Project

max_forks_repo_name: lxlonlyn/CSP-Project


text:
%
% Luminescence: nwHacks 2017
% Backend Specification
%
% Author: Jeffrey Leung
%

\documentclass[10pt, oneside, letterpaper, titlepage]{article}
\usepackage[utf8]{inputenc}

\usepackage[ampersand]{easylist} % For 8-level simulations of itemize using easylist
	\ListProperties(
		Progressive*=5ex,
		Space=5pt,
		Space*=5pt,
		Style1*=\textbullet\ \ ,
		Style2*=\begin{normalfont}\begin{bfseries}\textendash\end{bfseries}\end{normalfont} \ \ ,
		Style3*=\textasteriskcentered\ \ ,
		Style4*=\textperiodcentered\ \ ,
		Style5*=\textbullet\ \ ,
		Style6*=\begin{normalfont}\begin{bfseries}\textendash\end{bfseries}\end{normalfont}\ \ ,
		Style7*=\textasteriskcentered\ \ ,
		Style8*=\textperiodcentered\ \ ,
		Hide1=1,
		Hide2=2,
		Hide3=3,
		Hide4=4,
		Hide5=5,
		Hide6=6,
		Hide7=7,
		Hide8=8 )
\usepackage{geometry}
	\geometry{margin=1.2in}
\usepackage{graphicx}
	\graphicspath{ {img/} }
\usepackage[colorlinks=true, linkcolor=blue]{hyperref}
\usepackage{listings}
\usepackage{verbatim}

\renewcommand{\arraystretch}{1.2}

% Font-related commands:
\usepackage[T1]{fontenc} % Allows the use of symbols in LMSS such as the braces
\usepackage[default, osfigures]{opensans}
\usepackage{textcomp} % Allows the use of symbols in LMSS such as textasterisk and textbullet
\renewcommand{\familydefault}{\sfdefault}

\title{Luminescence: nwHacks 2017 \\ \large Backend Specification v0.1}
\author{Jeffrey Leung}
\date{March 18, 2017}

\begin{document}

	\maketitle
	\clearpage

	\section{Patient Information}

	Each patient is uniquely identified by a patient ID.

	\subsection{Retrieve patient data}

		Patient data is retrieved primarily through the patient ID and secondarily through the tag ID.

		\subsubsection*{Request}

		Path:

		\begin{verbatim}
GET /patient
		\end{verbatim}

		\noindent
		Parameters:
		\begin{itemize}
			\item \verb|patientId|: Unique ID of the patient
			\begin{itemize}
				\item Required if \verb|tagId| is not provided
			\end{itemize}
			\item \verb|tagId|: Unique ID of the tag
			\begin{itemize}
				\item Required if \verb|patientId| is not provided
			\end{itemize}
		\end{itemize}

		\subsubsection*{Response}

		\begin{verbatim}
{
  "id" : "8cfb5ca9-83b3-41d2-9044-3ea01780242",
  "information" : {
    "fullName" : "Jacky Chao",
    "gender" : "m",
    "address" : "1234 University Drive, Burnaby, BC, Canada",
    "birth" : {
      "day" : 29,
      "month" : 12,
      "year" : 1993
    }
  },
  "emergencyContact" : {
    "fullName" : "Carlson Chan",
    "phone" : "604-301-9592"
  },
  "history" : [
  ],
  "medication" : [
  ]
}
		\end{verbatim}

\end{document}


text:
% ==============================================================================
%
%                             U S E R   G U I D E
%
% ==============================================================================

% ==============================================================================
%
%                                  S E T U P
%
% ==============================================================================
\chapter{Setup} % <<< -------------------------------------------------------- %
\label{ch:userguide:setup}
% ---------------------------------------------------------------------------- %

Initializing the system and using  the oscilloscope is mostly straightforward,
even for beginners. A few notes on the  initial setup are outlined here to get
the reader started. The next chapter then  presents the general concept of the
user interface.

Getting the system  up and running requires two  basic steps: Initializing the
STEMlab  itself,  and  connecting  to  it  from  a  web  browser  to  run  the
oscilloscope.  Assuming the  STEMlab board at hand has been  delivered with an
SD card  containing the correct Linux  image from this project,  the procedure
for this is as follows:
\begin{enumerate}
    \item
        Insert the SD card coming  with the board (\emph{Note:} Check that the
        SD card has the right side up to make pin contact).
    \item
        Connect the board physically to the network.
    \item
        Connect the board to the power supply.
    \item
        Call    the    board's    IP    address    and    the    right    port
        (eg.    \code{https://10.84.130.54:50090})    in    a    browser    of
        your   preference   (for   best    results   use   Chrome   61.0   and
        above). Figure~\ref{fig:userguide:url} shows  an example  how to
        do this.
    \item
        A  notice   that  a  popup   menu  has  been  blocked   should  appear
        (Figure~\ref{fig:userguide:popup:warn}). Select   \emph{Always   allow
        popups from  this application}  or similar  and reload  the previously
        called   page. Figure~\ref{fig:userguide:popup:yes}  illustrates   the
        necessary setting.
    \item
        A popup tab should now contain  the scope and automatically connect to
        the  STEMlab's  webserver. Figure~\ref{fig:userguide:running} shows  a
        running scope.
\end{enumerate}

If it  is unknown  whether the SD  card was delivered  with a  prebuilt image,
it  can  be  assumed  that  it  was  and  the  board  can  be  powered  on. If
the  orange  LED  farthest away  from  the  ports  (RJ45,  SD card,  \ldots  )
flashes  at \SI{2}{\Hz},  the  SD card  is  fine.   If the  SD  card does  not
contain a  prebuilt image,  Section~\ref{sec:devguide:fpga_toolchain:linux} in
the Developer's Guide explains how one can be acquired or built.

\begin{figure}
    \centering
    \includegraphics[width=0.85\textwidth]{images/userguide/url}
    \caption[Entering the URL]{%
        Using a browser and the correct URL to run the scope application on
        the STEMlab%
    }
    \label{fig:userguide:url}
\end{figure}

\begin{figure}
    \centering
    \includegraphics[width=0.85\textwidth]{images/userguide/popup_warn}
    \caption[The popup warn popup]{%
        The browser warns about a popup the site has tried to open.
    }
    \label{fig:userguide:popup:warn}
\end{figure}

\begin{figure}
    \centering
    \includegraphics[width=0.85\textwidth]{images/userguide/popup_yes}
    \caption[Accept popups in the future]{%
        Let the browser accept popups in the future%
    }
    \label{fig:userguide:popup:yes}
\end{figure}

\begin{figure}
    \centering
    \includegraphics[width=0.85\textwidth]{images/userguide/running}
    \caption[Running the scope]{%
        The running scope after everything has been set up properly%
    }
    \label{fig:userguide:running}
\end{figure}

%>>>
% ==============================================================================
%
%                              O P E R A T I O N
%
% ==============================================================================
\chapter{Operation} % <<< ---------------------------------------------------- %
\label{ch:userguide:operation}
% ---------------------------------------------------------------------------- %

Once the oscilloscope  is running, interaction is done via  its graphical user
interface. Its  most important  features  are summarized  here.   It has  been
designed  with high  discoverability in  mind, so  a complete  guide on  every
single last button and menu is considered beyond the scope of this document.

Figure~\ref{fig:userguide:screenshot}  shows a  screenshot  of the  interface.
The UI's most important functions are:
\begin{description}
    \item[Zooming and Panning:]
        To zoom,  use the  vertical and horizontal  scrolling function  of the
        mouse or  trackpad.  To  pan, click  and drag  the signal. If  you are
        dragging a time trace it will automatically move the trigger location.
        The two arrow buttons in the general preference pane resize the signal
        to the visible area.
    \item[Triggering:]
        To set the trigger level, move the drawn trigger level by clicking and
        dragging it  or enter the level  in numbers on the  preference pane of
        the triggering time trace.
    \item[Markers:]
        There are four  markers by default. Two mark the start  and end of the
        area  over which  power  is  integrated and  two  mark  the area  that
        contains the signal for the automatic SNR calculation.

        Markers can be dragged and  moved by clicking and dragging. The number
        at the bottom of each marker shows the frequency it is at.

        The plus button in  the general pref pane adds a  new marker which can
        be used to mark certain frequencies.

        To move the SNR  markers, the SNR mode has to  be set from \emph{auto}
        to \emph{manual} mode in the corresponding FFT trace preference pane.
    \item[Sampling Rate:]
        To configure the  sampling rate, use the drop-down menu  at the top of
        the general preference pane.
    \item[Line Width:]
        To  improve  readability,  some  people  might  like  a  thicker  line
        width. To set the line width, use the  input at the top of the general
        pref pane.
\end{description}

\begin{figure}
    \centering
    \includegraphics[width=1\textwidth]{images/gui/scope}
    \caption[The Scope Application]{%
        The scope application in its current state, displaying time and FFT data%
    }
    \label{fig:userguide:screenshot}
\end{figure}

%>>>

%^^A vim: foldenable foldcolumn=4 foldmethod=marker foldmarker=<<<,>>>

max_stars_repo_name: alpenwasser/pitaya

max_issues_repo_name: alpenwasser/pitaya

max_forks_repo_name: alpenwasser/pitaya


text:
%
% API Documentation for API Documentation
% Module datk.tests.networks_tests
%
% Generated by epydoc 3.0.1
% [Sat Dec 19 01:14:33 2015]
%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%                          Module Description                           %%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

    \index{datk \textit{(package)}!datk.tests \textit{(package)}!datk.tests.networks\_tests \textit{(module)}|(}
\section{Module datk.tests.networks\_tests}

    \label{datk:tests:networks_tests}
Network Test Suite

Tests Netwoks defined in networks.py by visual inspection

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%                               Variables                               %%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

  \subsection{Variables}

    \vspace{-1cm}
\hspace{\varindent}\begin{longtable}{|p{\varnamewidth}|p{\vardescrwidth}|l}
\cline{1-2}
\cline{1-2} \centering \textbf{Name} & \centering \textbf{Description}& \\
\cline{1-2}
\endhead\cline{1-2}\multicolumn{3}{r}{\small\textit{continued on next page}}\\\endfoot\cline{1-2}
\endlastfoot\raggedright i\-p\- & \raggedright \textbf{Value:}
{\tt get\_ipython()}&\\
\cline{1-2}
\raggedright D\-R\-A\-W\-\_\-R\-A\-N\-D\-O\-M\- & \raggedright \textbf{Value:}
{\tt None}&\\
\cline{1-2}
\raggedright D\-R\-A\-W\-\_\-H\-U\-G\-E\-\_\-R\-A\-N\-D\-O\-M\- & \raggedright \textbf{Value:}
{\tt None}&\\
\cline{1-2}
\raggedright D\-R\-A\-W\-\_\-U\-N\-I\-\_\-R\-I\-N\-G\- & \raggedright \textbf{Value:}
{\tt None}&\\
\cline{1-2}
\raggedright D\-R\-A\-W\-\_\-B\-I\-\_\-R\-I\-N\-G\- & \raggedright \textbf{Value:}
{\tt None}&\\
\cline{1-2}
\raggedright D\-R\-A\-W\-\_\-C\-O\-M\-P\-L\-E\-T\-E\-\_\-G\-R\-A\-P\-H\- & \raggedright \textbf{Value:}
{\tt None}&\\
\cline{1-2}
\raggedright D\-R\-A\-W\-\_\-U\-N\-I\-\_\-L\-I\-N\-E\- & \raggedright \textbf{Value:}
{\tt None}&\\
\cline{1-2}
\raggedright D\-R\-A\-W\-\_\-B\-I\-\_\-L\-I\-N\-E\- & \raggedright \textbf{Value:}
{\tt None}&\\
\cline{1-2}
\raggedright T\-I\-M\-E\-O\-U\-T\- & \raggedright \textbf{Value:}
{\tt 5}&\\
\cline{1-2}
\raggedright \_\-\_\-p\-a\-c\-k\-a\-g\-e\-\_\-\_\- & \raggedright \textbf{Value:}
{\tt \texttt{'}\texttt{datk.tests}\texttt{'}}&\\
\cline{1-2}
\end{longtable}

    \index{datk \textit{(package)}!datk.tests \textit{(package)}!datk.tests.networks\_tests \textit{(module)}|)}

max_stars_repo_name: manna/datk

max_issues_repo_name: manna/datk

max_forks_repo_name: manna/datk


text:
\documentclass[12pt,a4paper]{article}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{../task-report}
\author{Geraldo Xexéo}
\title{My tasks}

\begin{document}
\maketitle

\section{Model Task}
\trtask[status]{name}{date assigned}{The Boss}{The Worker}{Why you need}{data done}{Extra text, comments and etc.}

\section{New state waiting is teal}

\traddstatecolor{waiting}{cordeburroquandofoge}
\trtask[waiting]{Drink a coffe}{\today}{The Boss}{The Worker}%
{To keep awake}{\today}{Coffe must be strong and add 1 spoon of sugar}

\end{document}

max_stars_repo_name: xexeo/task-report

max_issues_repo_name: xexeo/task-report

max_forks_repo_name: xexeo/task-report


text:
\subsection{Euclidean division}\label{subsec:euclidean_division}

\begin{definition}\label{def:commutative_ring_division}
  Let \( a, b \in R \). We say that \( b \) is a \term{divisor} of \( a \) or that \( a \) is a \term{factor} of \( b \) and write \( b \mid a \) if there exists \( c \in R \) such that \( a = bc \).

  We say that \( b \) is a \term{trivial} divisor of \( a \) if \( a = bc \) and either \( b \) or \( c \) is invertible.
\end{definition}

\begin{definition}\label{def:modulo}
  Fix an ideal \( I \) of \( R \).

  If for some \( a, b \in R \) we have \( a - b \in I \), we say that \( a \) and \( b \) are \term{congruent modulo} \( I \) and write
  \begin{equation*}
    a \cong b \pmod I.
  \end{equation*}

  If the ideal \( I \) is generated by the single element \( n \) and if \( a = b \mod I \), we say that \( a \) and \( b \) are congruent modulo \( n \) and write
  \begin{equation*}
    a \cong b \pmod n.
  \end{equation*}
\end{definition}

\begin{definition}\label{def:greatest_common_denominator}
  The \term{greatest common denominator}  of \( a \) and \( b \) is defined, if it exists and is unique, as
  \begin{equation*}
    \gcd(a, b) \coloneqq \max_{\cdot \mid \cdot} \{ c \in R : c \mid a \wedge c \mid b \},
  \end{equation*}
  where the maximum is taken with respect to the divisibility partial order.
\end{definition}

\begin{definition}\label{def:factorization_in_ring}
  A factorization of \( x \in R \) is a finite sequence \( p_1, \ldots, p_n \) of \hyperref[def:irreducible_ring_element]{irreducible} elements with multiplicities \( k_1, \ldots, k_n \), so that
  \begin{equation*}
    x = e p_1^{k_1} p_2^{k_2} \cdots p_n^{k_n},
  \end{equation*}
  where \( e \) is a unit in \( R \).
\end{definition}

\begin{definition}\label{def:euclidean_domain}\mcite{nLab:euclidean_domain}
  Let \( R \) be an integral \hyperref[def:semiring/integral_domain]{domain}. Multiplication is not invertible in general, but we can instead define \term{Euclidean division} with remainders.

  We endow \( R \) with an additional function \( \delta: R \to \BbbZ_{\geq 0} \). Let \( a, b \in R \). If there exists a pair \( (q, r) \) such that
  \begin{equation*}
    a = bq + r
  \end{equation*}
  holds and either \( r = 0 \) or \( \delta(r) < \delta(b) \), we say that \( (R, \delta) \) is an \term{Euclidean domain}.

  We say that \( b \) \term{divides} \( a \) with \term{quotient} \( q \) and \term{remainder} \( r \).

  If the pair \( (q, r) \) is unique, we use the special notation
  \begin{balign*}
    q & = \quot(a, b),                    \\
    r & = \rem(a, b) = a - b \quot(a, b).
  \end{balign*}
\end{definition}

\begin{algorithm}\label{alg:euclidean_algorithm}
  Let \( R \) be an Euclidean domain. Fix \( a, b \in R \) with \( b \neq 0 \). The \term{Euclidean algorithm} for finding \( \gcd(a, b) \) proceeds as follows:
  \begin{thmenum}
    \thmitem{alg:euclidean_algorithm/initialization} Define \( r_0 \coloneqq a \) and \( r_1 \coloneqq b \).
    \thmitem{alg:euclidean_algorithm/step} Starting with \( i = 2 \), obtain \( q_i \) and \( r_i \) from \hyperref[def:semiring/euclidean_domain]{division}
    \begin{equation*}
      r_{i-2} = r_{i-1} q_i + r_i.
    \end{equation*}

    If \( r_i = 0 \), halt the algorithm with result \( \gcd(a, b) = r_i \).

    Otherwise, proceed by incrementing \( i \) and repeating this step.
  \end{thmenum}
\end{algorithm}
\begin{proof}
  Euclidean division ensures that \( \delta(r_i) < \delta(r_{i-1}) \) on every step. Thus, the algorithm terminates at some point. Denote by \( n \) the (minimum) number of steps necessary to obtain \( r_n = 0 \).

  We show by induction on \( k < n \) that \( r_n \) divides \( r_{n-k} \). The case \( k = 0 \) is obvious since \( r_n \) divides itself.

  Assume that \( r_n \) divides \( r_{n-i} \) for \( 0 < i < k \). Now since
  \begin{equation*}
    r_{n-k} = r_{n-(k-1)} q_{n-(k-2)} + r_{n-(k-2)}
  \end{equation*}
  and both of the terms on the right-hand side are factors of \( r_n \), the left-hand side \( r_{n-k} \) is also a factor.

  We conclude that \( r_n \) divides both \( r_{n-(n-1)} = r_1 = b \) and \( r_{n-n} = r_0 = a \).

  Furthermore, \( r_n \) is the greatest common divisor of \( a \) and \( b \). Indeed, assume that there exists \( d \in R \) such that \( r_n \mid d \) and both \( d \mid a \) and \( d \mid b \) hold. But he have
  \begin{equation*}
    a = b q_2 + r_2,
  \end{equation*}
  hence \( d \mid r_2 \). Proceeding by induction, we obtain that \( d \mid r_n \). But we assumed that \( r_n \mid d \), therefore \( r_n = d \) and \( r_n \) is the greatest common divisor of \( a \) and \( b \).
\end{proof}

\begin{proposition}\label{thm:euclidean_domain_is_pid}
  Every Euclidean \hyperref[def:semiring/euclidean_domain]{domain} is a principal ideal \hyperref[def:semiring/principal_ideal_domain]{domain}.
\end{proposition}
\begin{proof}
  Fix an ideal \( I \) of the Euclidean domain \( R \). By \fullref{thm:natural_numbers_are_well_ordered}, the set \( \delta(I) \) has a minimum. Choose an element \( m \in I \) such that \( \delta(m) = \min \delta(I) \). We will prove that \( I = \braket m \).

  Let \( x \in I \). We divide it by \( m \) to obtain
  \begin{equation*}
    x = mq + r,
  \end{equation*}
  such that either \( r = 0 \) or \( \delta(r) < \delta(m) \). Since both \( x \) and \( m \) are in \( I \), we have \( r = mq - x \in I \). But \( m \) minimizes \( \delta \) over \( I \), thus \( \delta(m) \leq \delta(r) \), which contradicts \( \delta(r) < \delta(m) \). Therefore, \( r = 0 \) and
  \begin{equation*}
    x = mq,
  \end{equation*}
  which implies that \( x \in \braket m \). This proves \( I \subseteq \braket m \).

  Let \( x \in \braket m \), that is, \( x = mq \) for some \( q \in R \). Since \( I \) is an ideal and \( m \in I \), all multiples of \( m \) are in \( I \) and thus \( x \in I \). This proves \( \braket m \subseteq I \).

  We have now obtained \( \braket m = I \). Since \( I \) was an arbitrary ideal, we conclude that every ideal in \( R \) is principal.
\end{proof}

\begin{proposition}\label{thm:pid_is_ufd}
  Every principal ideal \hyperref[def:semiring/principal_ideal_domain]{domain} is a unique factorization \hyperref[def:semiring/unique_factorization_domain]{domain}.
\end{proposition}

\begin{theorem}[Bezout's identity]\label{thm:bezout_identity}
  Let \( R \) be a principal ideal domain. Let \( a, b \in R \) with \( b \neq 0 \). Then \( \gcd(a, b) \) exists and, furthermore, there exist \( x, y \) such that
  \begin{equation*}
    ax + by = \gcd(a, b).
  \end{equation*}
\end{theorem}
\begin{proof}
  We will first prove the existence of \( \gcd(a, b) \). Define the ideal
  \begin{equation*}
    I \coloneqq \braket{a, b}.
  \end{equation*}

  Since every ideal is principal, there exists \( g \in I \) such that \( I = \braket g \). Let \( x, y \in R \) such that
  \begin{equation*}
    g = ax + by.
  \end{equation*}

  Note that \( g \) is a divisor of both \( a \) and \( b \) because \( a \in I \) and \( b \in I \). We will show that it is the greatest divisor. Let \( d \) be another divisor of both \( a \) and \( b \) such that \( g \mid d \) (or, equivalently, \( d \in \braket g \)).

  Let \( a = da' \) and \( b = db' \). We have
  \begin{equation*}
    g = ax + by = d(a'x + b'y),
  \end{equation*}
  which implies that \( d \mid g \). Thus, \( g = d \) and \( g \) is a greatest common denominator.
\end{proof}

\begin{algorithm}\label{alg:extended_euclidean_algorithm}
  Let \( R \) be an Euclidean domain. Fix \( a, b \in R \) with \( b \neq 0 \). We will explicitly find \( x \) and \( y \), so that \fullref{thm:bezout_identity} is satisfied:
  \begin{equation*}
    \gcd(a, b) = ax + by.
  \end{equation*}

  Let \( r_0, r_1, \ldots, r_n \) be the sequence of remainders from \fullref{alg:euclidean_algorithm}. The \term{extended Euclidean algorithm} proceeds as follows:

  \begin{thmenum}
    \thmitem{alg:extended_euclidean_algorithm/initialization} For \( i = 2 \), define
    \begin{balign*}
      x_2 & \coloneqq 1,    \\
      y_2 & \coloneqq -q_2.
    \end{balign*}

    \thmitem{alg:extended_euclidean_algorithm/step} For \( i = 2, \ldots, n \), define
    \begin{balign*}
      x_i & \coloneqq x_{i-2} - x_{i-1} q_i, \\
      y_i & \coloneqq y_{i-2} - y_{i-1} q_i.
    \end{balign*}

    \thmitem{alg:extended_euclidean_algorithm/completion} Halt the algorithm with result
    \begin{balign*}
      x & \coloneqq x_n, \\
      y & \coloneqq y_n.
    \end{balign*}
  \end{thmenum}
\end{algorithm}
\begin{proof}
  We will prove with induction on \( i = 2, \ldots, n \) that
  \begin{equation*}
    r_i = ax_i + by_i.
  \end{equation*}

  \begin{refenum}
    \refitem{alg:extended_euclidean_algorithm/initialization} For \( i = 2 \), we have
    \begin{balign*}
      r_0       & = r_1 q_2 + r_2, \\
      a         & = b q_2 + r_2,   \\
      a - b q_2 & = r_2,
    \end{balign*}
    that is, \( r_2 = a + b (-q_2) \).

    \refitem{alg:extended_euclidean_algorithm/step} For \( i = 3, \ldots, n \), we have
    \begin{balign*}
      r_{i-2}                                               & = r_{i-1} q_i + r_i,                 \\
      a x_{i-2} + b y_{i-2}                                 & = (a x_{i-1} + b y_{i-1}) q_i + r_i, \\
      a (x_{i-2} - x_{i-1} q_i) + b (y_{i-2} - y_{i-1} q_i) & = r_i.
    \end{balign*}

    \refitem{alg:extended_euclidean_algorithm/completion} Since \( r_n = \gcd(a, b) \), we conclude that
    \begin{equation*}
      \gcd(a, b) = a x_n + b y_n.
    \end{equation*}
  \end{refenum}
\end{proof}

max_stars_repo_name: v--/notebook

max_issues_repo_name: v--/notebook

max_forks_repo_name: v--/notebook


text:
\section*{Web Appendix D}

In this appendix we illustrate the relationship between the fixed effects publication bias and \emph{p}-hacking models, discussed in Section 2.4, using an example. Recall the definition of the fixed effects one-sided discrete p-hacking model,
\[
f_{\textrm{ph}}(x\mid\theta,\sigma)=\sum_{j=1}^{J}\pi_{j}\phi_{[c_{j},\infty)}(x\mid\theta,\sigma^{2}).
\]
Consider this model with mixture probabilities and underlying standard
normal distribution. The components of the mixture together with the
\emph{p}-hacking model are displayed in Figure \ref{fig:p-hacking plots}
for $\pi=(0.4,0.2,0.4)$.

Using Proposition $1$, we can write the publication bias model as
\begin{eqnarray*}
f_{\textrm{pb}}(x\mid\theta,\sigma) & = & \sum_{j=1}^{J}\pi_{j}^{\star}\phi_{[c_{j},c_{j-1})}(x\mid\theta,\sigma^{2})
\end{eqnarray*}
where $\pi_{j}^{\star}$ are mixture probabilities that depend on
$\rho_{j}$.

The publication bias and \emph{p}-hacking models are, in this case, equivalent. To illustrate, consider the fixed effects
\emph{p}-hacking model with $\pi=(0.4,0.2,0.4)$ and underlying standard
normal distribution. It is quite easy to verify that the \emph{p}-hacking
model is equivalent to the publication bias model with selection probabilities$\rho\approx(1,0.3,0.03)$
and $\pi^{\star}=(0.38,0.11,0.51)$. To see why, notice that we can
write
\[
\pi_{j}^{\star}=a_{j}^{\star}\sum_{i=j}^{J}\frac{\pi_{j}}{a_{j}}
\]
where $a_{j}=1-\Phi(c_{j},\theta,\sigma^{2})$ and $a_{j}^{\star}=\Phi(c_{j-1},\theta,\sigma^{2})-\Phi(c_{j},\theta,\sigma^{2})$.
The we can use the expressions for $\pi_{i}^{\star}$ of Proposition
$1$ to formulate and solve a linear system for $\rho$ in terms of
$\pi^{\star}$.

In this particular case,
\begin{eqnarray*}
\pi_{3}^{\star} & = & \pi_{3}a_{3}^{\star}=0.4\cdot0.95=0.38,\\
\pi_{2}^{\star} & = & 0.025\cdot(\pi_{3}+\pi_{2}/0.05)=0.11,\\
\pi_{1}^{\star} & = & 0.025\cdot(\pi_{3}+\pi_{2}/0.05+\pi_{1}/0.025)=\pi_{1}+\pi_{2}^{\star}=0.51.
\end{eqnarray*}
The $\rho$s can be solved for numerically to obtain $\rho\approx(1,0.3,0.03)$,
see the $\mathtt{R}$ file $\texttt{translating.R}$ for more details.

\begin{figure}
\noindent \begin{centering}
\includegraphics[scale=0.5]{plots/p-hacking}
\par\end{centering}
\caption{\label{fig:p-hacking plots}Illustration of the mixture components
of the \emph{p-}hacking model.}

\end{figure}

The publication bias model and the \emph{p}-hacking models are equivalent
under the fixed effects meta-analysis model, as formalized by the
following Lemma.
\begin{lem}
\label{lem:equivalence}Let $\{\sigma_{i}\}_{i=1}^{n}$ be
a collection of standard deviations and $\theta\in\mathbb{R}$ be
an underlying mean. Then there is a bijective function $g(\pi)=\pi^{\star}$
so that $\prod f_{\textrm{ph}}(x_{i}\mid\theta,\sigma_{i},\pi)=\prod f_{\textrm{pb}}(x_{i}\mid\theta,\sigma_{i},g(\pi))$
for any collection $\{x_{i}\}_{i=1}^{n}$ of observations.
\end{lem}

\begin{proof}
It suffices to show there is a bijective function function $g(\pi)=\pi^{\star}$
so that $f_{\textrm{ph}}(x_{i}\mid\theta,\sigma_{i},\pi)=f_{\textrm{pb}}(x_{i}\mid\theta,\sigma_{i},g(\pi))$
that is independent of $\sigma_{i}$. To do this, define $g(\pi)$
by $\pi_{j}^{\star}=a_{j}^{\star}\sum_{i=j}^{J}\frac{\pi_{j}}{a_{j}}$
to make a bijective function between $\pi$ and $\pi^{\star}$. Now
observe that both $a_{j}^{\star}$ and $a_{j}$ are independent of
$\sigma_{i}$ when $\theta$ is fixed. Thus $g(\pi)$ is independent
of $\sigma_{i}$ and the proof is done.
\end{proof}
You may use this lemma to transform the $\pi$s on the \emph{p}-hacking
form into $\pi^{\star}$ on the publication bias form and vice versa.

max_stars_repo_name: JonasMoss/p-hacking

max_issues_repo_name: JonasMoss/p-hacking

max_forks_repo_name: JonasMoss/p-hacking


text:
\documentclass[reprint,onecolumn,%endfloats*,
amsmath,amssymb,aip,apl]{revtex4-1}

\usepackage{graphicx}% Include figure files
\usepackage{dcolumn}% Align table columns on decimal point
\usepackage{bm}% bold math
\usepackage{hyperref}% add hypertext capabilities
\usepackage{comment}
\usepackage[version=4]{mhchem}
\usepackage{color}

%\usepackage{float}

\usepackage{siunitx}
\DeclareSIPostPower\tothefourth{4}
\usepackage[english]{babel}
\usepackage{esdiff} % for differentiation
\usepackage{mathtools}
\DeclarePairedDelimiter\abs{\lvert}{\rvert} % for absolute values

\begin{document}
	\title{RCSJ model using python3}
	\author{Felix E. Schmidt}
	\author{Mark D. Jenkins}
	\affiliation{Kavli Institute of NanoScience, Delft University of Technology, Lorentzweg 1, 2628 CJ, Delft, The Netherlands.}
	\date{\today}

	\begin{abstract}
		This script is based on Tinkham's "Introduction to superconductivity"\cite{tinkham} and Gross' "Applied superconductivity", chapter 3 \cite{gross}.
		All simulations were done using \texttt{python3} and the \texttt{rcsj} module written by Felix \cite{rcsj}.
	\end{abstract}

	\maketitle
	\tableofcontents

	\section{Current biasing}
	\subsection{Junction model and ODE}
	We model the Josephson junction in the simplest way possible:
	A series network of a resistor $R$, a capacitor $C$ and a nonlinear inductor.
	The total current running through the network is
	\begin{eqnarray}
	I(t) =& I_s(t) + I_R(t) + I_C(t) \\%
	I(t) =& I_c\sin(\phi) + \frac{V}{R} + C\diff{V}{t} \\%
	V(t) =& \frac{\hbar}{2e}\diff{\phi}{t}, \; \diff{V}{t} = \frac{\hbar}{2e} \diff[2]{\phi}{t} \\%
	\rightarrow I(t) =& I_c\sin(\phi)+\frac{\hbar}{2eR}\diff{\phi}{t}+\frac{\hbar C}{2e}\diff[2]{\phi}{t}
	\label{eq:ODE}
	\end{eqnarray}
	Note that for this equation, the resistance in reality depends both on temperature and the voltage across the junction due to quasiparticle tunneling:
	\begin{eqnarray}
	R(V,T) = \begin{cases}
	R_{sg}(T) \; &{\rm for \;} \abs{V} \leq 2\Delta(T)/e \\%
	R_{n} \; &{\rm for \;} \abs{V} \geq 2\Delta(T)/e \\%
	\end{cases}
	\end{eqnarray}
	where typically $R_{sg} \gg R_n$.
	The characteristic voltage of the junction is accordingly defined as $V_c=I_c R_n$.
	There are two approaches to simplifying equation \ref{eq:ODE} in terms of normalization.
	We here call them the \textbf{Tinkham approach}\cite{tinkham} and the \textbf{Gross approach}\cite{gross}.

	\subsubsection{Tinkham approach}
	The equation is simplified with normalized time via the plasma frequency, $\tau=\omega_p t$:
	\begin{eqnarray}
	\omega_p=\frac{1}{\tau_p}=\frac{1}{\sqrt{L_c C}}=\sqrt{\frac{2eI_c}{\hbar C}} \\%
	{\rm d}t=\frac{1}{\omega_p}{\rm d}\tau \rightarrow \diff[n]{}{t}=\omega_p^n \diff[n]{}{\tau} \\%
	\frac{I}{I_c}-\sin(\phi) = \underbrace{\frac{\hbar}{2eI_cR}\sqrt{\frac{2eI_c}{\hbar C}}}_{\sqrt{\frac{\hbar C}{2eI_c}}\frac{1}{RC}\equiv Q^{-1}}\diff{\phi}{\tau}+\underbrace{\frac{\hbar C}{2eI_c}\frac{2eI_c}{\hbar C}}_{1}\diff[2]{\phi}{\tau}
	\end{eqnarray}
	Hence the final ODE is
	\begin{eqnarray}
	\diff[2]{\phi}{\tau}=\frac{I}{I_c}-\sin(\phi)-\frac{1}{Q}\diff{\phi}{\tau}
	\label{eq:tinkham}
	\end{eqnarray}

	\subsubsection{Gross approach}
	This approach is different in that it seems more intuitive, but the time scale and damping are different:
	We normalize the time not by the plasma frequency, but the $L_c/R_n$ time constant that yields the characteristic junction frequency:
	\begin{eqnarray}
	\omega_c=\frac{1}{\tau_c}=\frac{R_n}{L_c}=\frac{2e}{\hbar}I_cR_n=\frac{\Phi_0}{2\pi}V_c \\%
	\tau=\frac{t}{\tau_c}, \; \tau_c=\frac{\hbar}{2e I_cR} \\%
	{\rm d}t=\tau_c{\rm d}\tau \rightarrow \diff[n]{}{t}=\frac{1}{\tau_c^{n}}\diff[n]{}{\tau}
	\end{eqnarray}
	The above ODE then can be resorted into
	\begin{eqnarray}
	I-I_c\sin(\phi)=\frac{\hbar\tau_c}{2eR}\diff{\phi}{\tau}+\frac{\hbar C \tau^2}{2e}\diff[2]{\phi}{\tau} \\%
	i-\sin(\phi)=\underbrace{\frac{\hbar}{2eRI_c}\left(\frac{2eI_cR}{\hbar}\right)}_{1}\diff{\phi}{\tau}+\underbrace{\frac{\hbar C}{2e}\left(\frac{2eI_cR}{\hbar}\right)^2}_{\frac{2eI_cR^2C}{\hbar}=\beta_c} \diff[2]{\phi}{\tau} \\%
	\diff[2]{\phi}{\tau} = \frac{1}{\beta_c}\left(i-\sin(\phi)-\diff{\phi}{\tau}\right)
	\label{eq:gross}
	\end{eqnarray}
	Note that $\beta_c\equiv Q^2\equiv\tau_c RC$.
	For this ODE it is much easier to distinguish between $\beta_c\gg1$ and $\beta_c\ll1$, simply because of its form.
	However, it is important to keep in mind that the timescales are different!

	\subsection{Unit discussion}
	We consider first $\tau_c$.
	The units of $\hbar/(2e)=\Phi_0/(2\pi)$ are \si{Wb}=\si{\kilogram\meter\squared\per\second\squared\per\ampere}.
	Critical current is in \si{\ampere}, resistance in \si{\ohm}=\si{\kilogram\meter\squared\per\second\cubed\per\ampere\squared}.
	Therefore
	\begin{eqnarray}
	\left[\tau_c\right]=\left[\frac{\hbar}{2e}\frac{1}{I_c}\frac{1}{R}\right] = \frac{\si{\kilogram\meter\squared}}{\si{\second\squared\ampere}}\frac{1}{\si{\ampere}}\frac{\si{\second\cubed\ampere\squared}}{\si{\kilogram\meter\squared}} = \si{\second} \\%
	\rightarrow \left[\tau\right]=\left[\frac{t}{\tau_c}\right]=\frac{\si{\second}}{\si{\second}}=1
	\end{eqnarray}
	Now the same for the plasma frequency:
	Capacitance is given in units of \si{F}=\si{\second\tothefourth\ampere\squared\per\meter\squared\per\kilogram}
	\begin{eqnarray}
	\left[\omega_p\right]=\left[\sqrt{\frac{2e}{\hbar}\frac{I_c}{C}}\right]=\sqrt{\frac{\si{\second\squared\ampere}}{\si{\kilogram\meter\squared}}\si{\ampere}\frac{\si{\meter\squared\kilogram}}{\si{\second\tothefourth\ampere\squared}}}=\sqrt{\frac{1}{\si{\second\squared}}}=\frac{1}{\si{\second}} \\%
	\rightarrow \left[\tau\right]=\left[\omega_p t\right]=\frac{\si{\second}}{\si{\second}}=1
	\end{eqnarray}

	\subsection{Damping and hysteresis}
	We consider eq. \ref{eq:gross} for simplicity.
	For \textbf{very weak damping}, i.e. $\beta_c\gg1$, the left hand side of the ODE can be set to zero.
	The result is a linear IVC on the retrapping branch, with $I_r\leq I_c$:
	\begin{eqnarray}
	\diff[2]{\phi}{\tau}=0 \rightarrow \langle V(t)\rangle=IR_n \\%
	\frac{I_r}{I_c}\approx\frac{4}{\pi\sqrt{\beta_c}}\equiv\frac{4}{\pi Q}
	\end{eqnarray}
	An open question is why Gross (and others) report significant hysteresis $I_r/I_c\approx0.85$ already for $\beta_c=1$, while we achieve at least $I_r/I_c=0.95$ for the implemented python simulations.

	For \textbf{very strong damping}, i.e. $\beta_c\ll1$, the right hand side of the ODE is zero:
	\begin{eqnarray}
	\diff{\phi}{\tau}=i-\sin(\phi) \rightarrow \langle V(t) \rangle=I_c R\sqrt{\left(I/I_c\right)^2-1}
	\end{eqnarray}
	without hysteresis.
	See also Fig. \ref{fig:hysteresis} for the resulting simulations of the two cases.

	\begin{figure}
		\centering
		\includegraphics[width=0.49\linewidth]{figs/ivcs_updown}\hfill
		\includegraphics[width=0.49\linewidth]{figs/hysteresis_loglin}
		\caption{(a) Current-voltage curves for various damping cases.
			As predicted by theory, high damping ($Q\ll1$) corresponds to a square-root like IVC with no hysteresis, while low damping ($Q\gg1$) results in strong hystersis with a almost linear retrapping branch. (b) Hysteresis as a function of damping in terms of the Steeqart-McCumber parameter. For low damping, $\beta_c\gg1$, the hysteresis can be approximated by $4/(\pi Q)$.}
		\label{fig:hysteresis}
	\end{figure}

	\subsection{Frequency analysis}

	\subsection{Notes on simulation}
	Some things I noted during simulations:
	\begin{itemize}
		\item The initial conditions for each iteration are extremely important!
		\begin{itemize}
			\item Currently (\today), after letting the system evolve for a certain number of time steps (adjusted for each Q), the voltage is calculated by averaging over the last cycle.
			If there is no voltage cycle the voltage gets set to zero.
			The initial condition of the next run is the final state of the system from the previous run.
			\item Another option would be to set the maximum phase change of the previous run as initial condition.
			If we do this, the system jumps to the normal branch much earlier than at $i=1$.
			In frequency space, this leads to fancy wave patterns.
			\item Probably the most correct approach would be to set the maximum phase change of the last cycle as initial condition.
			Or should it be the minimum?
			Does this have influence on ramping speed as well?
		\end{itemize}

		\item $Q$ versus $\beta_c$
		\begin{itemize}
			\item The package is now optimized for the use of $Q$ for damping.
			Using $\beta_c$ is finally also implemented, but not yet tested. \textbf{TODO!!}
		\end{itemize}
		\item Subgap resistance
		\begin{itemize}
			\item \textbf{TODO!!}
		\end{itemize}
	\end{itemize}

	\section{Voltage biasing}
	The system equation only slightly changes.
	What remains to be seen is the normalization and the exact values needed to achieve voltage biasing.

	\bibliography{cited.bib}

\end{document}

max_stars_repo_name: feschmidt/rcsj

max_issues_repo_name: feschmidt/rcsj

max_forks_repo_name: feschmidt/rcsj


text:
\section{Vectors in 3-Dimentional Euclidean Space}
A vector is a quantity with magnitude (length/size) and direction.
Examples: Force, momentum, electric \& magnetic fields, etc.
All these examples are modelled on position.
In this chapter, we adopt a geometric approach to position vectors in $\mathbb R^3$ based on the Euclidean notions of geometry (points, lines, planes, lengths, angles, etc.)\\
We choose a point $O$ as origin, then points $A$ and $B$ have position vectors
$$\underline{a}=\overrightarrow{OA}, \underline{b}=\overrightarrow{OB}$$
We define the magnitude of a vector by $|\underline{a}|=|\overrightarrow{OA}|$ and we denote $O$ by $\underline{0}$.
\subsection{Vector addition and Scalar Multiplication}
Given vectors $\underline{a},\underline{b}$ denoting points $A,B$, we construct the parallelogram $OACB$, so we define $\underline{a}+\underline{b}=\underline{c}$ where $\underline{c}=\overrightarrow{OC}$.
One should note that we have already used the parallel postulate here.\\
Given $\underline{a}$ which is the position vector of point $A$ and a scalar $\lambda\in\mathbb R$, $\lambda\underline{a}$ is the position of point on the straight line $OA$ where $|\lambda\underline{a}|=|\lambda||\underline{a}|$.
It changes direction if and only if $\lambda$ is negative.
Note that $\{\lambda\underline{a}:\lambda\in\mathbb R\}$ is the set of all points on the straight line $OA$.
\begin{proposition}
    For any $\underline{a}$, $\underline{a}+\underline{0}=\underline{0}+\underline{a}=\underline{a}$.\\
    For any $\underline{a}$, $\underline{a}+(-\underline{a})=(-\underline{a})+\underline{a}=\underline{0}$.\\
    Also, vector addition is associative and commutative.
    That is, the set of vectors gives an abelian group under vector addition.
\end{proposition}
\begin{proof}
    Trivial. Consider a parallelopiped for associativity.
\end{proof}
\begin{proposition}
    $\lambda(\underline{a}+\underline{b})=\lambda\underline{a}+\lambda\underline{b}$.\\
    $(\lambda+\mu)\underline{a}=\lambda\underline{a}+\mu\underline{a}$.\\
    $\lambda(\mu\underline{a})=(\lambda\mu)\underline{a}$
\end{proposition}
\begin{proof}
    Trivial.
\end{proof}
\subsection{Linear Combination and Span}
$\alpha\underline{a}+\beta\underline{b}$ where $\alpha,\beta\in\mathbb R$ is called a linear combination of $\underline{a},\underline{b}$.
We can easily extend this definition to an arbitrary set of vectors.
\begin{definition}
    We define $\operatorname{span}(S)$ to be the collection of all linear combinations of vectors in $S$.
\end{definition}
We say $\underline{a},\underline{b}$ are parallel if $\underline{a}=\lambda \underline{b}$ or $\underline{b}=\lambda\underline{a}$ for some $\lambda\in\mathbb R$.
In this case, we write $\underline{a}\parallel\underline{b}$\\
If $\underline{a}\nparallel\underline{b}$, then $\operatorname{span}(\{\underline{a},\underline{b}\})$ is a plane.
\subsection{Scalar Dot Product}
\begin{definition}
    Let $\theta$ be the angle betweeen $\underline{a},\underline{b}$, then
    $$\underline{a}\cdot\underline{b}=|\underline{a}||\underline{b}|\cos\theta$$
    If either of them is $\underline{0}$, then their dot product is $\underline{0}$.
\end{definition}
\begin{proposition}
    $\underline{a}\cdot\underline{b}=\underline{b}\cdot\underline{a}$.\\
    $\underline{a}\cdot\underline{a}=|\underline{a}|^2\ge 0$ and the equality sign applies if and only if $\underline{a}=0$.\\
    Also $(\lambda\underline{a})\cdot\underline{b}=\lambda(\underline{a}\cdot\underline{b})$ and $\underline{a}\cdot(\underline{b}+\underline{c})=\underline{a}\cdot\underline{b}+\underline{a}\cdot\underline{c}$
\end{proposition}
\begin{proof}
    Trivial.
\end{proof}
\begin{definition}
    We say $\underline{a}$ and $\underline{b}$ are perpndicular, written as $\underline{a}\perp\underline{b}$ if $\underline{a}\cdot\underline{b}=0$
\end{definition}
Considering the case $\underline{a}\neq\underline{0}$, then
$$\frac{\underline{a}\cdot\underline{b}}{|\underline{a}|}=|b|\cos\theta=\underline{u}\cdot\underline{b}, \underline{u}=\frac{1}{|\underline{a}|}\underline{a}$$
which is the component of $\underline{b}$ along $\underline{a}$.
\subsection{Orthonormal Basis}
Choose vectors $\underline{e_1},\underline{e_2},\underline{e_3}$ that are orthonormal, which means that any two of them are perpendicular to each other and that their magnitudes are all $1$.
Note that this is equivalent to the choice of Cartesian axes along the three directions..
Also $\{\underline{e}_i\}$ is a basis, so any vector can be expressed as some linear combination of them.
$$\underline{a}=a_1\underline{e_1}+a_2\underline{e_2}+a_3\underline{e_3}$$
Also, each component is uniquely determined.
$$\underline{a}\cdot\underline{e_i}=a_i$$
So we can describe each vector as a row or column vector $\underline{a}=(a_1,a_2,a_3)$.
Note as well that $\underline{a}\cdot\underline{b}=\sum_i(a_ib_i)\underline{e_i}$, so $|\underline{a}|^2=\sum_ia_i^2$.
We write $\underline{e_1}=\underline{i},\underline{e_2}=\underline{j}, \underline{e_3}=\underline{k}$.
\subsection{Vector/Cross Product}
\begin{definition}
    Given nonparallel vectors $\underline{a},\underline{b}$.
    Let $\theta$ be the angle between them, measured in the sense that it is relative to a unit normal $\underline{n}$ to the plane they span by the ``right-handed sense'', then we define
    $$\underline{a}\times\underline{b}=|\underline{a}||\underline{b}|\sin(\theta)\underline{n}$$
    This is called the vector product or cross product of $\underline{a}$ and $\underline{b}$.
\end{definition}
Here $\underline{n}$ can only be defined when $\underline{a}\nparallel\underline{b}$.
We define $\underline{a}\times\underline{b}=0$ otherwise, since neither $\theta$ nor $\underline{n}$ is well defined in this case.
Note as well that changing sign of $\underline{n}$ does not change $\sin\theta$.
\begin{proposition}[Properties of cross product]
    1. $\underline{a}\times\underline{b}=-\underline{b}\times\underline{a}$.\\
    2. $\lambda(\underline{a}\times\underline{b})=(\lambda\underline{a})\times\underline{b}=\underline{a}\times(\lambda\underline{b})$.\\
    3. $\underline{a}\times(\underline{b}+\underline{c})=\underline{a}\times\underline{b}+\underline{a}\times\underline{c}$.\\
    4. $\underline{a}\times\underline{b}=0\iff\underline{a}\parallel\underline{b}$.\\
    5. $\underline{b}\perp(\underline{a}\times\underline{b})\perp\underline{a}$.
\end{proposition}
\begin{proof}
    Trivial.
\end{proof}
\begin{remark}
    $\underline{a}\times\underline{b}$ is the vector area of the parallelogram $\underline{0},\underline{a},\underline{b},\underline{a}+\underline{b}$.
    Its magnitude is the scalar area of that parallelogram.
    The direction of it then specified the orientation of this parallelogram in space.
    This gives the significance of vector product.
\end{remark}
We fix $\underline{a},\underline{x}$ such that they are perpendicular.
$\underline{a}\times\underline{x}$ scales $\underline{x}$ by a factor of $|\underline{a}|$ in a different direction.\\
For easier calculation, we introduce a component expression of the vector product.
We consider an orthogonal basis $\underline{i},\underline{j},\underline{k}$ which by ordering we have
$$\underline{i}\times\underline{j}=\underline{k},\underline{j}\times\underline{k}=\underline{i},\underline{k}\times\underline{i}=\underline{j}$$
This is called an orthonormal right-hand set (basis).\\
Now, for $\underline{a}=a_1\underline{i}+a_2\underline{j}+a_3\underline{k},\underline{b}=b_1\underline{i}+b_2\underline{j}+b_3\underline{k}$, we have
$$\underline{a}\times\underline{b}=
\begin{vmatrix}
    \underline{i}&\underline{j}&\underline{k}\\
    a_1&a_2&a_3\\
    b_1&b_2&b_3
\end{vmatrix}
$$
\subsection{Triple Products}
\subsubsection{Scalar Triple Product}
\begin{definition}
    The scalar triple product of $\underline{a},\underline{b},\underline{c}$ is defined as $\underline{a}\cdot(\underline{b}\times\underline{c})$.
\end{definition}
The interpretation of the scalar triple product is that $|\underline{c}\cdot(\underline{a}\times\underline{b})|$ is the volume of parallelopiped constructed by the frame $\underline{a},\underline{b},\underline{c}$.
This can be shown easily by consider the geometric definitions of dot and cross products.
The sign of taht expression removing the modulus sign could be interpreted as the sign of volume.
We say $\underline{a},\underline{b},\underline{c}$ is a right-handed set if $\underline{c}\cdot(\underline{a}\times\underline{b})>0$.
Note that $\underline{c}\cdot(\underline{a}\times\underline{b})=0$ if and only if $\underline{a},\underline{b},\underline{c}$ are coplanar.\\
Again, we can write the triple product by the components.
That is, if $\underline{a}=a_1\underline{i}+a_2\underline{j}+a_3\underline{k},\underline{b}=b_1\underline{i}+b_2\underline{j}+b_3\underline{k},\underline{c}=c_1\underline{i}+c_2\underline{j}+c_3\underline{k}$, then
$$\underline{a}\cdot(\underline{b}\times\underline{c})=
\begin{vmatrix}
    a_1&a_2&a_3\\
    b_1&b_2&b_3\\
    c_1&c_2&c_3
\end{vmatrix}
$$
\subsubsection{Vector Triple Product}
\begin{definition}
    $$\underline{a}\times(\underline{b}\times\underline{c})=(\underline{a}\cdot\underline{c})\underline{b}-(\underline{a}\cdot\underline{b})\underline{c}$$
    $$(\underline{a}\times\underline{b})\times\underline{c}=(\underline{a}\cdot\underline{c})\underline{b}-(\underline{b}\cdot\underline{c})\underline{a}$$
    This is called the vector triple product of vectors $\underline{a},\underline{b},\underline{c}$.
\end{definition}
We can check the above works by components by brute force, but we will establish a notation which make things easier later.
\begin{example}
    Suppose $\underline{a}=(2,0,-1),\underline{b}=(7,-3,5)$.
    So $\underline{a}\times\underline{b}=(-3,-17,-6)$.\\
    We can use the scalar triple product to design a test for coplanarity.
    Let $\underline{3,-3,7}$ then we do have $\underline{c}\cdot(\underline{a}\times\underline{b})=0$
\end{example}
The application of vector triple products, however, will be seen below.
\subsection{Lines, Planes and Vector Equations}
\subsubsection{Lines}
We can think of vectors as displacements between points.
The displacement between vectors can be found by vector substraction.
So the general point on a line through $\underline{a}$ in the direction $\underline{u}\neq\underline{0}$ have the form
$$\underline{r}=\underline{a}+\lambda\underline{u},\lambda\in\mathbb R$$
This called the parametric form of a line.\\
The alternative form of a straight line without a parameter is taken by a cross product
$$\underline{u}\times(\underline{r}-\underline{a})=\underline{0}$$
Which literally means that $\underline{r}-\underline{a}=\lambda\underline{u}$ for some real $\lambda$.\\
Now consider $\underline{u}\times\underline{r}=\underline{c}$.
So we have $\underline{u}\cdot\underline{c}=0$.
So if we have $\underline{u}$ and $\underline{c}$ where $\underline{u}\cdot\underline{c}\neq 0$, then it is a contradiction.
Conversely, if it is really $0$, then we can consider $\underline{u}\times (\underline{u}\times\underline{c})=-|u|^2\underline{c}$.\\
So it is just a line.
\subsubsection{Plane}
The general form of a plane through some position $\underline{a}$ to directions $\underline{u},\underline{v}$ (with $\underline{u}\times\underline{v}\neq\underline{0}$) is
$$\underline{r}=\underline{a}+\lambda\underline{u}+\mu\underline{v}, \lambda,\mu\in\mathbb R$$
This is called the parametric form of a plane.\\
Alternatively, we can ditch the parameters:
$$(\underline{r}-\underline{a})\cdot(\underline{u}\times\underline{v})=0$$
Or
$$\underline{r}\cdot(\underline{u}\times\underline{v})=\kappa$$
where $\kappa=\underline{a}\cdot(\underline{u}\times\underline{v})$ is a constant.\\
This form of equation is actually saying that the vector $\underline{r}-\underline{a}$ is always perpendicular to some given normal $\underline{n}=\underline{u}\times\underline{v}$.
\subsubsection{Vector equations}
We can have some more general vector equations.
More generally, a vector equation is some equation of the form $f(\underline{r})=0$.\\
These can often be solved by dotting or crossing with constant vectors.
\begin{example}
    $\underline{r}+\underline{a}\times(\underline{b}\times\underline{r})=\underline{c}$
    We first expand the vector triple product there,
    $$\underline{r}+(\underline{a}\cdot\underline{r})\underline{b}-(\underline{a}\cdot\underline{b})\underline{r}=\underline{c}$$
    Also we have
    $$\underline{a}\cdot\underline{r}=\underline{a}\cdot\underline{c}$$
    Note that this is weaker here.
    Putting it back in the previous equation,
    $$(1-\underline{a\cdot\underline{b}})\underline{r}+(\underline{a}\cdot\underline{c})\underline{b}=\underline{c}$$
    So if $\underline{a}\cdot\underline{b}\neq 1$,
    $$\underline{r}=\frac{\underline{c}-(\underline{a}\cdot\underline{c})\underline{b}}{1-\underline{a\cdot\underline{b}}}$$
    Otherwise, there is no solution if $\underline{c}-(\underline{a}\cdot\underline{c})\underline{b}\neq 0$.
    But if it equals $0$, then there are infinitely many solutions.
\end{example}
Sometimes more systematically, we look for a solution of the form $\alpha\underline{a}+\beta\underline{b}+\gamma\underline{c}$ where $\underline{a},\underline{b},\underline{c}$ are linearly independent.
However, sometimes the dotting and crossing method is quicker.\\
There are many cases when the vector equation may not be linear.
\begin{example}
    $\underline{r}\cdot\underline{r}+\underline{r}\cdot\underline{a}=k$.
    We can try completing the square to get
    $(\underline{r}+\underline{a}/2)^2=k+\underline{a}^2/4$
\end{example}
\subsection{Index/Suffix Notation and the Summation Convention}
\subsubsection{Index Notation}
Write vectors $\underline{a},\underline{b},\underline{c},\ldots$ in terms of components $a_i,b_i,c_i,\ldots$ wrt an orthonormal right-handed basis
$$\underline{e_1},\underline{e_2},\underline{e_3}$$
The indices $i,j,k,l,p,q,\ldots$ will take value $1,2,3$.
So
$$\underline{c}=\alpha\underline{a}+\beta\underline{b}\iff c_i=\alpha a_i+\alpha b_i$$
$$\underline{x}=\underline{a}+(\underline{b}\cdot\underline{c})\underline{d}\iff x_i=a_j+\sum_kb_kc_kd_j$$
\begin{definition}
    The Kronecker $\delta$ is defined as
    $$\delta_{ij}=\begin{cases}
        1\text{, if $i=j$}\\
        0\text{, otherwise}
    \end{cases}$$
\end{definition}
Then note that $\underline{e_i}\cdot\underline{e_j}=\delta_{ij}$ and that $\underline{a}\cdot\underline{b}=(\sum_ia_i\underline{e_i})\cdot(\sum_ja_j\underline{e_j})=\sum_{i,j}a_ib_j\delta_{ij}=\sum_ia_ib_i$.\\
Now, cross products,
\begin{definition}
    The Levi-Civita $\epsilon$ is defined as
    $$\epsilon_{ijk}=
    \begin{cases}
        1\text{, if $(i,j,k)$ is an even permutation of $(1,2,3)$}\\
        -1\text{, if $(i,j,k)$ is an odd permutation of $(1,2,3)$}\\
        0\text{, otherwise}
    \end{cases}$$
\end{definition}
$\epsilon_{ijk}=-\epsilon_{jik}=-\epsilon_{ikj}=-\epsilon_{kji}$.
Note that $\underline{e_i}\times\underline{e_j}=\sum_k\epsilon_{ijk}\underline{e_k}$.\\
Now we consider $\underline{a}\times\underline{b}$, we have
\begin{align*}
    \underline{a}\times\underline{b}
    &=(\sum_ia_i\underline{e_i})\times(\sum_ja_j\underline{e_j})\\
    &=\sum_{i,j}a_ib_je_i\times e_j\\
    &=\sum_{i,j,k}a_ib_j\epsilon_{i,j,k}\underline{e_k}
\end{align*}
One can check that it is equivalent to our original form of cross product.
\subsubsection{Summation Convention}
Indices that appear twice are usually summed.
In the summation convention, we could just ignore the sum signs.
That is, the sum is understood.
\begin{example}
    $a_i\delta_{ij}=\sum_ia_i\delta_{ij}=a_j$, so $a_i\delta_{ij}=a_j$\\
    $\underline{a}\cdot\underline{b}=a_ib_j\delta_{ij}$.\\
    $\underline{a}\times\underline{b}=a_ib_j\epsilon_{ijk}\underline{e_k}$.\\
    $\underline{a}\cdot(\underline{b}\times\underline{c})=$.\\
    $\delta_{ii}=3$.
\end{example}
Genuine rules of the convention are as follows.\\
1. An index appear exactly once must appear in very term of the expression, and every value of it appears.
This is called a free index.\\
2. An index occuring exactly twice in a given term is summed over, and is called a repeated/contracted/dummy index.\\
3. No index appear more than twice.\\
One application of this notation is to prove the vector triple product identity.
\begin{lemma}[$\epsilon-\epsilon$ identity]
    $\epsilon_{ijk}\epsilon_{pqk}=\delta_{ip}\delta_{jq}-\delta_{iq}\delta_{jp}$
\end{lemma}
\begin{proof}
    Both sides are anti-symmetric, and if any two are the same, then it vanishes.\\
    So it is enough to consider a particular case.\\
    If $i=p=1,j=q=2$, the identity hold.\\
    If $i=q=1,j=p=2$, the identity hold.\\
    All other index combinations giving nonzero results work similarly.
\end{proof}
\begin{proposition}
    $$\underline{a}\times(\underline{b}\times\underline{c})=(\underline{a}\cdot\underline{c})\underline{b}-(\underline{a}\cdot\underline{b})\underline{c}$$
\end{proposition}
\begin{proof}
    Note that $\epsilon_{ijk}\epsilon_{pqk}=\delta_{ip}\delta_{jq}-\delta_{iq}\delta_{jp}$
    \begin{align*}
        [\underline{a}\times(\underline{b}\times\underline{c})]_i
        &=\epsilon_{ijk}a_j(\underline{b}\times\underline{c})_k\\
        &=\epsilon_{ijk}a_j\epsilon_{kpq}b_pc_q\\
        &=\epsilon_{ijk}\epsilon_{pqk}a_jb_pc_q\\
        &=(\delta_{ip}\delta_{jq}-\delta_{iq}\delta_{jp})a_jb_pc_q\\
        &=\delta_{ip}\delta_{jq}a_jb_pc_q-\delta_{iq}\delta_{jp}a_jb_pc_q\\
        &=(a_jc_j)b_i-(a_jb_j)c_i
    \end{align*}
    So the theorem is proved.
\end{proof}
We notice one other thing:
If we simplify things by letting two indices matching up,  then $\epsilon_{ijk}\epsilon_{pjk}=2\delta_{ip}$.
Further, $\epsilon_{ijk}\epsilon_{ijk}=6$.

max_stars_repo_name: david-bai-notes/IA-Vectors-and-Matrices

max_issues_repo_name: david-bai-notes/IA-Vectors-and-Matrices

max_forks_repo_name: david-bai-notes/IA-Vectors-and-Matrices