text:
\documentclass{article}
\usepackage[utf8]{inputenc}
\usepackage[english]{babel}
\usepackage[a4paper, total={7in, 9in}]{geometry}
\usepackage{graphicx}
\usepackage{float}
\usepackage{verbatim}
\usepackage{fancyvrb}
\usepackage[bottom]{footmisc}
\PassOptionsToPackage{hyphens}{url}\usepackage{hyperref}
\usepackage[style=numeric]{biblatex}
\usepackage{csquotes}
\usepackage[title]{appendix}
\usepackage{xcolor}
\usepackage{minted}

\addbibresource{references.bib}

\newcommand{\question}[1]{
    {\large \textbf{Q: #1}}
    \\
}

\newcommand{\titleRule}{
    \rule{\linewidth}{0.5mm} \\ [0.25cm]
}

\begin{document}

{
\center
\textsc{\Large Universidade do Minho} \\ [0.5cm]
\textsc{\Large Masters in Computer Engineering} \\ [0.5cm]
\textsc{\large Parallel Algorithms} \\ [0.5cm]

{\LARGE \bfseries Parallel Gauss-Seidel method} \\[0.2cm]
{\LARGE \bfseries for solving the heat transfer problem} \\[0.5cm]

\begin{tabular}{c c}
    José Carlos Lima Martins & Miguel Miranda Quaresma \\
    A78821 & A77049  \\
\end{tabular} \\[0.5cm]

\today \\[1cm]
}

\section{Introduction}

The heat transfer problem, in a two dimensional space (2D), deals with determining how the temperature at each point of a surface evolves over time
until a steady state is reached, at which point the temperature remains constant (equilibrium temperature).
Each point starts at a certain temperature which changes due to the action of heat sources located at the boundaries of the plane, that cause heat to
disperse across the surface.

\subsection{Problem Modelling}
The heat transfer problem, as previously mentioned, deals with the diffusion of heat in a surface over time until it reaches a steady state (equilibrium).
In a 2 dimensional plane, with coordinates $(x,y)$, the problem can be modeled by the \textbf{heat equation} as follows:

$$\frac{\partial u}{\partial t} = \frac{\partial^2u}{\partial x^2} + \frac{\partial^2u}{\partial y^2}$$

which represents the variation of temperature ($u(x,y)$) at a certain point.

Since the objective is to determine the temperature of each point when steady state is reached \textbf{i.e.} when heat transfer no longer
occurs ($=0$), the problem can be described by the following equation:

$$\frac{\partial u}{\partial t} = 0 \Rightarrow \frac{\partial^2u}{\partial x^2} + \frac{\partial^2u}{\partial y^2} = 0$$

A caveat of the steady-state equation is that it doesn't imply that every point on the plane is at the same temperature, allowing for temperature gradients to be
present in the plate. However, given the heat sources remain constant, the temperature gradients will remain constant after steady state is reached.

To determine the temperature at any given point in a plate it's then necessary to apply the presented equation to each point of the plate. One obvious way of
doing this is using a system of linear equations where each line is the steady state temperature at a point.

Taking the previous equation we can now determine the temperature at a certain point when steady state is reached using the following expression:

$$\frac{\partial^2u}{\partial x^2} + \frac{\partial^2u}{\partial y^2} \\
\Rightarrow \frac{u(x+h/2, y) + u(x-h/2, y) - 2u(x,y)}{h^2} + \frac{u(x, y+k/2) + u(x, y-k/2) - 2u(x,y)}{k^2}$$

To calculate the temperature difference between two points, different steps, $h$ and $k$, can be used for each of the coordinates $x$ and $y$, leading to an error
of magnitude $O(h^2)$ and $O(k^2)$ respectively.

\subsection{Approach}
The use of iterative methods to solve computational problems is motivated by the need to solve large scale problems such as systems of linear equations with
a considerable number of variables. In this cases, the use of a direct method, while providing an exact solution, would require a considerable
amount of computing power and time to execute, making iterative methods more suitable for such scenarios. One example of such method is the
Gauss-Seidel iterative method that works by continuously updating a matrix containing the coefficients of each equation in each line where each element is
updated as follows:

$$x_i^{k+1} = \frac{b_i - \sum_{j=1}^{i-1} a_{ij}x_j^{k+1} - \sum_{j=i+1}^n a_{ij}x_j^k}{a_{ii}}$$

where $k$ is the current iteration. \\
The method halts when the differences between iterations are under a predefined threshold/tolerance.
This improves on the Jacobi method by using the values of the elements that have already been computed to update the current element, resulting in a higher
convergence rate as well dispensing the need for storing two vectors as only the most recent values are needed. However, by using the most recent
values, this method introduces data dependencies in each iteration, making it harder to develop in a parallel paradigm (as we will see in a later section,
this can be overcome by applying a strategy known as Red-Black strategy).

Another important factor to take into consideration when solving large scale problems is the use of matrix-free methods. Such approaches don't require
the (coefficient) matrix to be explicitly stored in memory, as that would require a large amount of memory and computing time, accessing the coefficients
by using matrix-vector products.
However, for the sake of simplicity, the implementations developed in the present work use a matrix to store the coefficients of each equation in each
line of the matrix.

\subsection{Discretization}
Calculating the temperature at every point in a 2D plane in a continuous domain would be infeasible as it would require an infinite amount of points.
As such, it becomes necessary to transfer the domain from a continuous one to a discrete one through a process known as discretization.
This process works by applying a mesh to the continuous domain and taking the value of the function (being studied) at each point of the mesh. In the case of the heat
equation the mesh is composed of four boundaries, called heat sources, with known temperature values, and a set of internal points whose temperature
is unknown. The process of discretization introduces a truncation error due to the fact that less points than the initial problem are used to describe the 2D
plane. As such, the truncation error is inversely proportional to the amount of points in the mesh.

\begin{figure}[H]
    \centering
    \includegraphics[width=10cm]{Pictures/Discretization.png}
    \caption{Discretization on a 2D plane with a five-point stencil}
    \label{fig:discretization}
\end{figure}

This truncation error in a mathematical perspective it's a swap of partial derivatives for stencils (approximation), i.e. use of finite differences. As such,
each point will be updated according to a five-point stencil, using the the arithmetic average of the four neighbouring points and the central point as the
new value. In other words, with a centered finite differences approach the truncation error will be $O(h^2)$ where $h$ is the distance between two
consecutive points in the mesh ($h=1$ when using Gauss-Seidel).

\section{Benchmark Platform}
In order to better understand the benchmark results gathered a brief description of the conditions in which the benchmarks were
executed will be presented.

\subsection{Statistical Methods}
A sample size of one was used for each benchmark because the number of iterations required don't change between different executions
of the same benchmark.

\subsection{Hardware Platform}
The benchmarks hereby mentioned were executed on a cluster node, from the SeARCH Computing Infrastructure. The node used, r641,
presents the following hardware specifications~\cite{cpu,search}:
\begin{itemize}
    \item \textbf{CPU}: Intel Xeon E5-2650v2 @2.6GHz, 16 cores
    \item \textbf{Cache Size}:
    \begin{itemize}
        \item L1d (per core): 32 KiB
        \item L1i (per core): 32 KiB
        \item L2 (per core): 256 KiB
        \item L3 (per package): 20 MiB
    \end{itemize}
    \item \textbf{RAM}: 64GB
    \item \textbf{Network}: Ethernet, \textit{myrinet}
\end{itemize}

\section{Sequential Implementation}
When implementing problems such as the heat transfer problem that deal with large quantities of data, and operations per
element/unit of data, it's important to consider an approach that allows for easy parallelization. However, in order to better understand the
problem being solved, a sequential implementation of the problem was developed initially, from which the pseudo-parallel (or parallel-ready)
implementation was based off.

The sequential implementation (see \ref{seqImp}) begins by defining a tri-dimensional matrix made up of two \texttt{N} by \texttt{N} matrices
that store the temperature values of the plate at each iteration. It begins by initializing the top, left and right boundaries of the plate
at 100 and the bottom one with 0 while the internal points are initialized with a value of 50.
Based on the size of the plate \textbf{i.e.} number of points in the mesh(N), a tolerance is set for the difference between temperatures
in consecutive iterations.
The function \texttt{poissongs} implements the Gauss-Seidel method on the matrix and halts the loop when the stopping criteria is met:
$$|| u^{k+1} - u^k|| \leq TOL$$
At each iteration, the last temperature values are stored in the matrix indexed as \texttt{plate[last]}.
Additionally, the biggest difference between consecutive temperatures in a point, is stored in \texttt{dif} which is used to check whether
the stopping criteria has been met.

\section{Sequential Implementation with Red-Black Strategy}
Based on the sequential implementation, a parallel-ready implementation was developed (see \ref{seqRBImp}) using the Red-Black strategy for dealing
with data dependencies in each iteration. This strategy works by interleaving the updated points in each loop so that it's possible for
the loop load to be distributed amongst different processes without needing to deal with data dependencies. It achieves this by updating the matrix in two
different loops, one for updating the odd points(Red) and the other for updating the even points(Black). Even though there are no dependencies in
each of the loops, the order at which the loops are executed must be preserved (Red-Black). A \textit{caveat} to this mechanism is the fact that the Red
points stencil uses the old values for temperature:
$$x_i^{k+1} = \frac{b_i - \sum_{j=1}^n a_{ij}x_j^k}{a_{ii}}$$
while the Black points stencil uses the current temperature values of it's neighboring elements:
$$x_i^{k+1} = \frac{b_i - \sum_{j=1}^n a_{ij}x_j^{k+1}}{a_{ii}}$$
This property results in a bigger number of iterations needed as the method tends to converge at a slower rate. The stop criteria is the same as
the previously stated.

\section{Parallel Implementation (MPI) with Red-Black Strategy}
The development of parallel applications is usually divided into two different paradigms the shared memory paradigm and the distributed memory paradigm.
The choice between the two is influenced not only by the characteristics of the work load, but also by the intended result. The development of
parallel applications using a distributed memory paradigm via libraries such as OpenMPI allows for a thorough theoretical analysis of the expected
behaviour of the algorithm, which is useful for identifying possible bottlenecks before developing the application.
The parallel implementation developed uses OpenMPI and distributes the load between each process. Due to the characteristics of OpenMPI, this (initial)
distribution doesn't require a broadcast of any values to each process as their memory is copied from the parent process, which contains the matrix with the
initial temperatures for each point in the mesh. The load distribution process begins by calculating the number of lines assigned to each process, which
is given by the expression: $\frac{N-2}{number\_processes}$  where $N$ is the number of lines. The process with rank $P-1$ is assigned with the remaining
lines \textbf{i.e.} $ (N-2) \bmod P$:

\begin{figure}[H]
    \centering
    \includegraphics[width=10cm]{Pictures/MatrixDraw.png}
    \caption{Load distribution}
    \label{fig:lineDiv}
\end{figure}

Each process then invokes the \texttt{phase} function which updates a group of rows of the mesh based on the process rank. To ensure the order at which
the mesh points are updated complies with the Red-Black scheme, the function \texttt{updateValues} is called after updating the Red points, and each process
exchanges one line with the two neighbouring processes (rank-1 and rank+1):

\begin{figure}[H]
    \centering
    \includegraphics[width=13cm]{Pictures/IterationCommunication.png}
    \caption{Function \texttt{updateValues}}
    \label{fig:commuLines}
\end{figure}

At the end of each iteration, the function \texttt{updateValues} is invoked again and every process communicates the biggest difference
between two consecutive temperatures for a given point to the parent process (with rank 0), which then determines the biggest value
between all this differences. This value is then communicated back to each process which use it to check whether the method has reached an
acceptable solution. After all iterations are executed, it is necessary to collect (communicate) the data from all the processes, which
is gathered by the parent process.

\begin{figure}[H]
    \centering
    \includegraphics[width=13cm]{Pictures/FinalCommunication.png}
    \caption{Result gathering}
    \label{fig:commuLines}
\end{figure}

The total amount of data exchanged between processes can be estimated as a function of the mesh size $N$, the number of processes $P$
and the number of iterations $it$ by the following expression:

$$ it * ( 2*2N*(P-1) + 2(P-1) ) + \frac{N-2}{P}*N*(P-1)$$

where:

\begin{itemize}
    \item $2*2N*(P-1)$ corresponds to the amount of data transferred in each iteration
    \item $2(P-1)$ corresponds to the amount of data needed to determine the biggest difference between two consecutive temperature values
    \item $\frac{N-2}{P}*N*(P-1)$ corresponds to the amount of data gathered after all iterations are executed
\end{itemize}

From this expression it's obvious that the amount of data transferred is of order $O(N^2)$ based on the mesh size.

\newpage

\section{Analysis and comparison of the different approaches}

To understand the behaviour of each implementation, and more specifically, how the Red-Black strategy affects the number of iterations needed
to obtain an acceptable solution, each implementation was run with 3 different parameters for the mesh size (10, 100, 1000) as well as different
tolerance values: $TOL=\frac{1}{N^2}$. The following chart shows the number of iterations needed, for each implementation, to reach an acceptable
solution based on this parameters:

\begin{figure}[H]
    \centering
    \includegraphics[width=16cm]{Pictures/Results.png}
    \caption{Results}
    \label{fig:results}
\end{figure}

One noticeable aspect of the results is the fact that the Red-Black strategy requires a higher number of iterations to obtain an acceptable solution,
which comes as a consequence of the fact that the Red points are updated using old values for it's neighbouring points which are then used by the Black
points, resulting in a slower convergence rate. Additionally, an increment on the size of the mesh, $N$, leads to a higher number of iterations until
the stop criteria is met. This is to be expected as the tolerance value is a function of the mesh size, becoming more restrictive as this value increases.
Thus, the convergence rate is lower for bigger $N$ values, while the the cost of each iteration increases since there are more elements to be updated.
The number of iterations increases proportional to a logarithmic scale.
Finally, the use of a parallel version via MPI, which distributes the load between more than one process (Parallel with RB), while requiring the same number
of iterations as it's sequential counterpart (Sequential with RB), will result in a reduced execution time.

\section{Conclusion}
The experiments on this work show that the usage of strategy such as Red-Black, in conjunction with an iterative method such as Gauss-Seidel, for solving
the heat dispersion problem is indeed advantageous for dealing with data dependencies that would, otherwise, make parallelization infeasible.
This remains true even with an increase in the number of iterations needed to reach an acceptable solution as the workload distribution outweighs
this increase when it comes to performance and execution time.
Additionally, the use of an iterative method such as Guass-Seidel, allows for an acceptable solution to be obtained for linear systems that would
otherwise take a considerable amount of execution time and computing power to solve.

\printbibliography

\newpage
\begin{appendices}

\section{Code}

\subsection{Auxiliar Code (utils)}
\begin{framed}
\begin{minted}{c}
#include "utils.h"

/**
 * Initialize heat plate with temperature values
 */
void initPlate(float plate[][N][N]){
    for(int i = 0; i < N; i ++){
        plate[0][0][i] = 100.0f;
        plate[0][i][0] = 100.0f;
        plate[0][i][N-1] = 100.0f;
        plate[0][N-1][i] = 0.0f;

        plate[1][0][i] = 100.0f;
        plate[1][i][0] = 100.0f;
        plate[1][i][N-1] = 100.0f;
        plate[1][N-1][i] = 0.0f;
    }

    for(int i = 1; i < N-1; i ++)
        for(int j = 1; j < N-1; j ++)
            plate[0][i][j] = 50.0f;

    plate[0][N-1][0] = 0.0f;
    plate[1][N-1][0] = 0.0f;
}

void initPlateForMPI(float plate[][N*N]){
    for(int i = 0; i < N; i ++){
        plate[0][0*N+i] = 100.0f;
        plate[0][i*N+0] = 100.0f;
        plate[0][i*N+N-1] = 100.0f;
        plate[0][(N-1)*N+i] = 0.0f;

        plate[1][0*N+i] = 100.0f;
        plate[1][i*N+0] = 100.0f;
        plate[1][i*N+N-1] = 100.0f;
        plate[1][(N-1)*N+i] = 0.0f;
    }

    for(int i = 1; i < N-1; i ++)
        for(int j = 1; j < N-1; j ++){
            plate[0][i*N+j] = 50.0f;
            plate[1][i*N+j] = 50.0f;
        }

    plate[0][(N-1)*N+0] = 0.0f;
    plate[1][(N-1)*N+0] = 0.0f;
}
\end{minted}
\end{framed}

\subsection{Sequential Implementation}\label{seqImp}
\begin{framed}
\begin{minted}{c}
#include "utils.h"

/*
 * Returns the number of iterations performed
 */
int poissongs(float plate[][N][N], float tol){
    int it = 0, last=0;
    float dif = tol + 1.0f, temp;

    while(dif > tol){
        dif = 0.0f;             //differences at the borders are 0.0f
        for(int i = 1; i < N-1; i ++)
            for(int j = 1; j < N-1; j ++){
                plate[!last][i][j] = (plate[!last][i-1][j] + plate[!last][i][j-1]
                                    + plate[last][i][j+1] + plate[last][i+1][j]) / 4.0f;
                temp = fabs(plate[!last][i][j] - plate[last][i][j]);
                if(temp > dif) dif = temp;
            }
        it ++;
        last = !last; //update matrix
    }
    return it;
}

int main(int argc, char *argv[]){
    float plate[2][N][N];
    float tol = 1.0f / (N*N);
    int it;

    initPlate(plate);

    it = poissongs(plate, tol);
    printf("Sequential Poisson GS\n Iteration Count: %d\n", it);

    return 0;
}
\end{minted}
\end{framed}

\subsection{Sequential Implementation with Red-Black Strategy}\label{seqRBImp}
\begin{framed}
\begin{minted}{c}
#include "utils.h"

/*
 * Returns the number of iterations performed
 */
int poissongs(float plate[][N][N], float tol){
    int it = 0, last=0;
    float dif = tol + 1.0f, temp;

    while(dif > tol){
        dif = 0.0f;             //differences at the borders are 0.0f
        //Black
        for(int i = 1; i < N-1; i ++)
            for(int j = 2 - i%2; j < N-1; j +=2){
                plate[!last][i][j] = (plate[last][i-1][j] + plate[last][i][j-1]
                                    + plate[last][i][j+1] + plate[last][i+1][j]) / 4.0f;
                temp = fabs(plate[!last][i][j] - plate[last][i][j]);
                if(temp > dif) dif = temp;
            }

        //Red
        for(int i = 1; i < N-1; i ++)
            for(int j = 1 + i%2; j < N-1; j +=2){
                plate[!last][i][j] = (plate[!last][i-1][j] + plate[!last][i][j-1]
                                    + plate[!last][i][j+1] + plate[!last][i+1][j]) / 4.0f;
                temp = fabs(plate[!last][i][j] - plate[last][i][j]);
                if(temp > dif) dif = temp;
            }

        it ++;
        last = !last; //update matrix
    }

    return it;
}

int main(int argc, char *argv[]){
    float plate[2][N][N];
    float tol = 1.0f / (N*N);
    int it;

    initPlate(plate);

    it = poissongs(plate, tol);

    printf("Sequential Poisson GS with Red-Back strategy\n Iteration Count: %d\n", it);

    return 0;
}
\end{minted}
\end{framed}

\subsection{Parallel Implementation (MPI) with Red-Black Strategy}\label{parRBImp}
\begin{framed}
\begin{minted}[fontsize=\footnotesize]{c}
#include <mpi.h>
#include "utils.h"

void updateValues(float plate[][N*N], int last, int offset, int rows, int rank, int no_procs, MPI_Status status){
    if(!rank){
        MPI_Recv( &(plate[last][(rows+1)*N]), N, MPI_FLOAT, rank+1, 2, MPI_COMM_WORLD, &status );
        MPI_Send( &(plate[last][rows*N]), N, MPI_FLOAT, rank+1, 2, MPI_COMM_WORLD);
    }else{
        MPI_Send( &(plate[last][(offset+1)*N]), N, MPI_FLOAT, rank-1, 2, MPI_COMM_WORLD);

        if(rank!=no_procs-1)
            MPI_Recv( &(plate[last][offset*N + (rows+1)*N]), N, MPI_FLOAT, rank+1, 2, MPI_COMM_WORLD, &status );

        if(rank!=no_procs-1)
            MPI_Send( &(plate[last][offset*N + rows*N]), N, MPI_FLOAT, rank+1, 2, MPI_COMM_WORLD);

        MPI_Recv( &(plate[last][offset*N]), N, MPI_FLOAT, rank-1, 2, MPI_COMM_WORLD, &status );
    }
}

float phase(float plate[][N*N], int last, int offset, int rows, int rank, int no_procs, MPI_Status status){
    float dif, temp;
    dif = 0.0f;

    //Black
    for(int i = offset+1; i < offset + 1 + rows; i ++)
        for(int j = 2 - i%2; j < N-1; j +=2){
            plate[!last][i*N+j] = (plate[last][(i-1)*N+j] + plate[last][i*N+j-1]
                                + plate[last][i*N+j+1] + plate[last][(i+1)*N+j]) / 4.0f;
            temp = fabs(plate[!last][i*N+j] - plate[last][i*N+j]);
            if(temp > dif) dif = temp;
        }

    updateValues(plate, !last, offset, rows, rank, no_procs, status);

    //Red
    for(int i = offset+1; i < offset + 1 + rows; i ++)
        for(int j = 1 + i%2; j < N-1; j +=2){
            plate[!last][i*N+j] = (plate[!last][(i-1)*N+j] + plate[!last][i*N+j-1]
                                + plate[!last][i*N+j+1] + plate[!last][(i+1)*N+j]) / 4.0f;
            temp = fabs(plate[!last][i*N+j] - plate[last][i*N+j]);
            if(temp > dif) dif = temp;
        }

    updateValues(plate, !last, offset, rows, rank, no_procs, status);

    if(rank){
        MPI_Send( &dif, 1, MPI_FLOAT, 0, 1, MPI_COMM_WORLD);
        MPI_Recv( &dif, 1, MPI_FLOAT, 0, 1, MPI_COMM_WORLD, &status);
    }else{
        for(int i=1; i<no_procs; i++){
            MPI_Recv( &temp, 1, MPI_FLOAT, i, 1, MPI_COMM_WORLD, &status);
            if(temp > dif) dif = temp;
        }
        for(int i=1; i<no_procs; i++){
            MPI_Send( &dif, 1, MPI_FLOAT, i, 1, MPI_COMM_WORLD);
        }
    }
    return dif;
}

/*
 * Returns the number of iterations performed
 */
int poissongs(float plate[][N*N], float tol, int rank, int no_procs, MPI_Status status){
    int it = 0, last=0, rows_per_proc, remaining_rows, work_load = N-2, begin, offset;
    float dif = tol + 1.0f;

    rows_per_proc = work_load/(no_procs-1);      //truncates result
    remaining_rows = work_load % (no_procs-1);   //remaining rows

    offset = rank * rows_per_proc;

    while(dif > tol){
        if(rank==no_procs-1)
            dif = phase(plate, last, offset, remaining_rows, rank, no_procs, status);
        else
            dif = phase(plate, last, offset, rows_per_proc, rank, no_procs, status);

        it ++;
        last = !last; //update matrix
    }

    //collect data
    if(!rank){
        begin = (rows_per_proc+1)*N;

        for(int i=1; i<no_procs-1; i++, begin+=rows_per_proc*N)
            MPI_Recv(&(plate[last][begin]), rows_per_proc*N, MPI_FLOAT, i, 3, MPI_COMM_WORLD, &status);

        MPI_Recv(&(plate[last][begin]), remaining_rows*N, MPI_FLOAT, no_procs-1, 3, MPI_COMM_WORLD, &status);

        //copy of process 0 result
        for(int i=1; i<rows_per_proc+1; i++)
            for(int j=0; j<N; j++)
                plate[last][i*N+j]=plate[!last][i*N+j];

    }else if(rank == no_procs-1) {
        MPI_Send( &(plate[!last][(offset+1)*N]), remaining_rows*N, MPI_FLOAT, 0, 3, MPI_COMM_WORLD);
    }else{
        MPI_Send( &(plate[!last][(offset+1)*N]), rows_per_proc*N, MPI_FLOAT, 0, 3, MPI_COMM_WORLD);
    }

    return it;
}

int main(int argc, char *argv[]){
    float plate[2][N*N];
    float tol = 1.0f / (N*N);
    int it, rank, no_procs;

    initPlateForMPI(plate);

    //Move MPI process creation to poissongs
    MPI_Status status;
    MPI_Init(&argc, &argv);
    MPI_Comm_size(MPI_COMM_WORLD, &no_procs);
    MPI_Comm_rank( MPI_COMM_WORLD, &rank );

    it = poissongs(plate, tol, rank, no_procs, status);

    MPI_Finalize();

    if(rank == 0)
        printf("Parallel Poisson GS with Red-Back strategy\n Iteration Count: %d\n", it);

    return 0;
}
\end{minted}
\end{framed}

\end{appendices}

\end{document}


text:
\section{Well-founded relations}\label{Wellfounded}

This library gives definitions and results about well-founded relations.

ext: tex

max_stars_repo_name: mzp/coq-for-ipad

max_issues_repo_name: mzp/coq-for-ipad

max_forks_repo_name: mzp/coq-for-ipad


text:
\subsection*{Sample selection}
Bulk RNA-seq from a curated set of 1,139 flash frozen colorectal tissue samples was re-processed and analyzed for the presence of unannotated HERV transcripts \citep{Dampier2020}.
For discovery of associations between tissue phenotypes and HERV expression, paired-end sequencing from 833 colon biopsies was used.
Of those biopsies, 462 were from healthy, 62 were from tumor adjacent normal, and 309 were from tumor tissue.
This set of samples is referred to as the discovery cohort.

For validation of discovered associations, two cohorts of samples from independent subjects were used.
The first (independent cohort \#1) included single-end sequencing from 276 colon biopsies of which 12 were healthy, 56 were tumor adjacent, and 208 were tumor.
The second (independent cohort \#2) included paired-end sequencing from 30 pairs of tumor and matched adjacent normal biopsies (i.e. 15 samples of both tissue phenotypes paired by subject).
To permit valid inference from regular linear models, only one tissue phenotype was used per subject in the discovery cohort and independent cohort \#1 (i.e. all samples were from independent subjects).

Samples were originally gathered from publicly available RNA-seq datasets hosted on the Genomic Data Commons and Sequence Read Archive as well as from a recently generated dataset of healthy mucosal biopsies obtained during screening colonoscopies at the Catalan Institute of Oncology in Barcelona, Spain \citep{Dampier2020, DiezObrero2020}.
A complete description of sample selection and cohort construction for the curated dataset is available in Dampier et al. (2020) \citep{Dampier2020}, and preliminary bioinformatic processing is described in the Supplementary Methods.

Although race was not analyzed in this study, we report that the discovery cohort included 37 Asian, 83 Black, and 660 White subjects, while the race of 53 others was not available.
Independent cohort \#1 included 12 Asian, 4 Black, and 17 White subjects, while the race of 243 others was not available.
Independent cohort \#2 included 7 Asian, 1 Black, and 7 White subjects.
Although no human subjects were recruited during this study, all previous studies from which data was used followed experimental protocols approved by institutional review committees and met the guidelines of relevant governmental agencies.

\subsection*{Human endogenous retrovirus annotation}
HERVs were identified using the genomic coordinates (GRCh38) and feature names of spliced transcripts of HERV elements from a recently published human cancer transcriptome annotated with the GENCODE v24 basic gene model \citep{Frankish2018} and a model of genome-wide repeat elements \citep{Attig2019}.
The cancer transcriptome was assembled from RNA-seq reads of 24 subjects from each of 32 cancer types obtained from The Cancer Genome Atlas (TCGA), as previously described \citep{Attig2019}.
Names and coordinates of repeat elements were generated using RepeatMasker \citep{Smit2015} configured with nhmmer \citep{Wheeler2013} in sensitive mode using the Dfam 2.0 library (v150923) \citep{Hubley2015}, as previously described \citep{Attig2017}.
The method relies on profile hidden Markov models representing known human repeat families to classify repeat elements throughout the genome.
Previously unannotated HERV transcripts were selected for the current study in multiple steps described in the Supplementary Methods.

\subsection*{Transcript quantification}
Transcript quantification was performed with Salmon v1.2.1 \citep{Patro2017} in mapping-based mode with the \verb|--gcBias| and \verb|--validateMappings| flags set.
Inputs to the Salmon \verb|quant| command were RNA-seq reads in FASTQ format and a custom Salmon index including unannotated HERV transcripts.
Creation of the Salmon index is described in the Supplementary Methods.

\subsection*{Proviral locus expression analysis}
Associations between HERV locus expression and tissue phenotype were tested using the \emph{Bioconductor} suite of genomics analysis packages \citep{bioc} in the R statistical programming language \citep{R}.
Data processing and analysis steps are described in detail in the Supplementary Methods.
Briefly, transcript expression estimates were converted to gene counts using \emph{tximport} \citep{Soneson2015}, confounding variables were estimated using \emph{sva} \citep{sva}, and expression levels were modeled using \emph{DESeq2} \citep{Love2014}.

Counts of all HERV loci with sufficient expression were modeled with phenotype and latent factors as explanatory variables.
Due to missing information for some samples, effects of demographic and technical factors were not modeled directly but instead captured with latent factors as described in the Supplementary Methods.
Significant associations between locus counts and tissue phenotype were identified by testing whether the absolute value of the effect of phenotype was at least two fold change for a given locus.
Multiple hypothesis testing correction was performed using a false discovery rate of 5\%.
All figures were produced with \emph{ggplot2} \citep{Wickham2016} as described in the Supplementary Methods.

\subsection*{Biomarker performance assessment}
Expression levels of select HERV loci were used as binary classifiers to distinguish tumor from non-tumor samples.
Classification was performed by logistic regression using the \verb|glm| function in R.
Transcript per million abundance estimates from Salmon were used as predictors of tissue phenotype.
The performance of each classifier was assessed by calculating the area under the receiver operating characteristic curve using the \emph{pROC} \citep{pROC} package.

All code is available on GitHub (https://github.com/dampierch/herv).

max_stars_repo_name: dampierch/herv

max_issues_repo_name: dampierch/herv

max_forks_repo_name: dampierch/herv


text:
% !TEX root = ../main.tex
% !TEX spellcheck = en_GB

\chapter{Boundaries}
\label{sec:Boundaries}
To limit the scope of this project, a MoSCoW analysis has been used to define and prioritise features of the product.

\begin{itemize}
	\item Must
	\begin{itemize}
		\item Communicate with a server using GSM
		\item Retrieve positional data from a GPS module
		\item Send GPS position to server
	\end{itemize}
	\item Should
	\begin{itemize}
		\item Save GPS data to SD-card
		\item Send GPS data to server in bursts to conserve power
	\end{itemize}
	\item Could
	\begin{itemize}
		\item Allow for wireless updates
		\item Communicate with an accelerometer
	\end{itemize}
\end{itemize}

max_stars_repo_name: lsangild/ETLYAK

max_issues_repo_name: lsangild/ETLYAK

max_forks_repo_name: lsangild/ETLYAK


text:
\documentclass[12pt]{article}

\title{CSC 455 - Assignment 3}
\author{Robert Krency}
\date{\today}

\usepackage{tikz}
\usepackage{amsmath}
\usepackage{graphicx}
\usepackage{tabularx}
\usepackage{multicol}
\usepackage{algpseudocode}
\usepackage{algorithm}
\usepackage{setspace}

% Geometry
\usepackage{geometry}
\geometry{letterpaper, left=20mm, top=20mm, right=20mm, bottom=20mm}

% Add vertical spacing to tables
\renewcommand{\arraystretch}{1.4}

\onehalfspacing

% Macros
\newcommand{\definition}[1]{\underline{\textbf{#1}}}

\newenvironment{rcases}
  {\left.\begin{aligned}}
  {\end{aligned}\right\rbrace}

% Begin Document
\begin{document}

\maketitle

\section{Question 1}

\begin{enumerate}

    \item $<var>[1].actual\_type \leftarrow$ look-up(B) Rule(4)
    \item $<expr>.expected\_type \leftarrow <var>.actual\_type$ Rule(1)
    \item $<var>[2].expected\_type \leftarrow$ look-up(B) Rule(1) \\
          $<var>[3].expected\_type \leftarrow$ look-up(A) Rule(1)
    \item $<expr>.expected\_type \leftarrow$ type will be real Rule(2)
    \item $<expr>.expected\_type == <expr>.actual\_type$ false, type mismatch Rule(2)
\end{enumerate}

This will not be a valid statement. The right side will evaluate to a Real variable, following rule 2.
A real value cannot be assigned to an int variable.

\pagebreak

\section{Question 2}

\begin{enumerate}

    \item Find the weakest precondition of the expression $a = a + 2 *\b - 1, \{ a > 1 \}$
    \begin{flalign*}
        & a > 1 && \\
        & a + 2 * b - 1 > 1 && \\
        & a + 2 * b > 2 &&
    \end{flalign*}

    \item Find the weakest precondition of the expressions
    \begin{flalign*}
        & a = 2 * b + 1 && \\
        & b = a - 3 && \\
        & \{ b < 0 \} &&
    \end{flalign*}

    \begin{flalign*}
        & b < 0 && \\
        & a - 3 < 0 && \\
        & a < 3 && \\
        & 2 * b + 1 < 3 && \\
        & 2 * b < 2 && \\
        & b < 1 &&
    \end{flalign*}

\end{enumerate}

\end{document}


text:
\clearpage
\phantomsection
\addcontentsline{toc}{subsection}{STTS}
\label{insn:stts}
\subsection*{STTS: Store a value into thread local storage}

\subsubsection*{Format}

\textrm{STTS \%rd, \%r1, \%r2}

\begin{center}
\begin{bytefield}[endianness=big,bitformatting=\scriptsize]{32}
\bitheader{0,7,8,23,24,31} \\
\bitbox{8}{0x2D}
\bitbox{8}{variable}
\bitbox{8}{rd}
\end{bytefield}
\end{center}

\subsubsection*{Description}

The \instruction{stts} instruction takes the value stored in
\registerop{rd} and stores it directly, or by reference into a thread
local variable.  The \verb|DIF_TF_BYREF| flag is used to determine the
appropriate lookup.

\subsubsection*{Pseudocode}

\begin{verbatim}
var = %rd
\end{verbatim}

\subsubsection*{Constraints}

\subsubsection*{Failure modes}

This instruction has no run-time failure modes beyond its constraints.

max_stars_repo_name: bsdbcr/documentation

max_issues_repo_name: bsdbcr/documentation

max_forks_repo_name: bsdbcr/documentation


text:
\chapter{Application features and manual}

\section{Add new tabs}

After starting the application the window looks like this: \\
\includegraphics[width=1\textwidth]{img/startup_window} \\

To start drawing you have to add tab with \textbf{File $\rightarrow$ New Tab} \\
\includegraphics[width=1\textwidth]{img/add_new_tab_1} \\
\includegraphics[width=1\textwidth]{img/add_new_tab_2}

The presented options in the dialog modifiy the drawing space:
\begin{itemize}
    \item \textbf{show intersections:}
        Displays a small red circle on the intersection point of two shapes
    \item \textbf{show coordinates:}
        Draws a coordinate system instead of the plain white background
    \item \textbf{show shape names:}
        Writes the name of each drawn shape besides it
\end{itemize}

After pressing \textbf{OK} a new tab appears. \\
\includegraphics[width=1\textwidth]{img/add_new_tab_3}

\section{Drawing shapes}

\includegraphics[width=1\textwidth]{img/drawing_shape}

\section{Edit drawn shapes}

\textbf{Set stroke width and color:} \\
\includegraphics[width=1\textwidth]{img/set_stroke} \\

\textbf{Move shape around:} \\
\includegraphics[width=1\textwidth]{img/move_shape} \\

\textbf{Resize shape (not possible with Freedraw):} \\
\includegraphics[width=1\textwidth]{img/resize_shape}

\section{Merge tabs}

When merging tabs all drawn shapes of the target tab are copied to the current tab.

\includegraphics[width=1\textwidth]{img/merge_tabs}

\section{Undo actions}

It is possible to undo following actions:
\begin{itemize}
    \item Delete shape
    \item Create shape
    \item Edit shape
    \item Merging of tabs
\end{itemize}

On way to undo actions is to use the menu \textbf{Edit $\rightarrow$ Undo}: \\
\includegraphics[width=1\textwidth]{img/undo_action_1} \\

The other way to undo actions is to use the \textbf{Commands} panel on the right side and click on the actions you want to undo: \\
\includegraphics[width=1\textwidth]{img/undo_action_2}

\section{Save and Load}

You can save and load the currently selected tab with \textbf{File $\rightarrow$ Save/Load}: \\
\includegraphics[width=1\textwidth]{img/save} \\
\includegraphics[width=1\textwidth]{img/load} \\

\section{Network tab}

Besides drawing locally it is possible to draw with two or more people onto the same drawing pane over network.
The first step to do so is to start \textit{reshapes.network.ReshapesServer} with two command line arguments.
Both arguments specifiy the port the server listens to for new clients and updates. \\
After the server is started the client can connect to the server with \textbf{File $\rightarrow$ New network tab}: \\
\includegraphics[width=1\textwidth]{img/new_network_tab}

The first three fields defines the hostname and ports of the server and the field \textbf{Client listener port} specifies the port to which the server sends updates.

max_stars_repo_name: FelixGail/REScala

max_issues_repo_name: FelixGail/REScala

max_forks_repo_name: FelixGail/REScala


text:
\chapter{Tiamat}

\begin{enumerate}
	\item Go to the clan hall, talk to Montblanc to get a lot of items.
	\item Buy Traveler
\end{enumerate}
\begin{liscense}
	Check Spreadsheet

	R1	Rd1
	Stv2
	R1	Rd1
	Stv2
	Shld1... HA3					R1
	LA5/HA4
	L1					Headsman
	R1	Poach				R1
	Traveler
	GM1
	L1	L1				Bm3
	BM3	L1
	Acc5... Acc8	L1?
\end{liscense}

\begin{shop}{2\,500}
	\sell{All weapons but Staves, Escutcheon, Bangle, Tourmaline Ring}
	\buy{Brigadeen, Red Cap \textit{if you have 23k Gil}}
	Can delay this to get the Shielded Armor instead of the Brigadeen next time you're in Jahara.
\end{shop}
\begin{enumerate}
	\item Get on Chocobo. When you get off, check for chest, and try to Berserk \basch\ with \penelo\ and then \vaan, then get back on the Chocobo. If you land it, take him out of the part for \balthier.
	\item Get on chocobo again, can repeat the berserk before the loading zone.
	      \vaanf Protect \vaan\ while running, make sure it's up for Tiamate. Larsa has healing gambits, so can stop \flee\ if anyone is below 50\%
	\item Cast Traveler, open the Menu to check Step Count. Turn Battle Speed to Min.
	\item Battle Speed to Max. Berserk \basch
\end{enumerate}
\begin{battle}{Tiamat}
	\begin{itemize}
		\item \vaan, \balthier, \basch, Larsa
		      \vaanf Dark Twice, equip Magicite
		      \vaanf Phoenix Down x2 Tiamat to draw Tiamat Aggro
		      \balthierf Check your step counter to make sure that the last 2 digits don't go above whatever you had before, then use Traveler when he flashes Red
	\end{itemize}
\end{battle}

max_stars_repo_path: Final Fantasy XII/Sections/tiamat.tex

max_issues_repo_path: Final Fantasy XII/Sections/tiamat.tex

max_forks_repo_path: Final Fantasy XII/Sections/tiamat.tex


text:
\documentclass[a4paper,twocolumn]{article}

\usepackage[utf8]{inputenc}
\usepackage[english]{babel}
\usepackage[T1]{fontenc}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{dsfont}
\usepackage{graphicx}
\usepackage{color}

\newcommand{\N}{\mathbf{N}}
\newcommand{\Z}{\mathbf{Z}}
\newcommand{\Q}{\mathbf{Q}}
\newcommand{\R}{\mathbf{R}}
\newcommand{\C}{\mathbf{C}}

\author{Florian Fontan}
\title{Advanced Models and Methods in Operations Research \\ Project: Unrelated parallel machines scheduling}
\date{2021--2022}

\begin{document}

\maketitle

For each problem considered, instances and a code skeleton containing an instance parser and a solution checker are provided in the \texttt{data/} and \texttt{python/} folders of the project.

The algorithms must be implemented in the provided files between the tags \texttt{TODO START} and \texttt{TODO END}.

They must be tested on all the provided instances with the command:
\texttt{python3 problem.py -i instance.json -c certificate.json}

And each solution file must be validated by the provided checker:
\texttt{python3 problem.py -a checker -i instance.json -c certificate.json}

The results must be reproducible.

\bigskip

The delivrable must contain:
\begin{itemize}
  \item A \emph{short} report describing and justifying the proposed algorithms
  \item The code implementing the algorithms
  \item The solution files obtained on the provided instances
\end{itemize}

\section{Dynamic Programming}

We consider the Single machine order acceptance and scheduling problem with objective Total weighted completion time:
\begin{itemize}
  \item Input:
    \begin{itemize}
      \item $n$ jobs with ($j = 1, \dots, n$)
        \begin{itemize}
          \item processing time $p_j \in \N^+$
          \item weight $w_j \in \N^+$
          \item profit $v_j \in \N^+$
        \end{itemize}
    \end{itemize}
  \item Problem: find a sub-sequence of jobs
  \item Objective: maximize the total profit minus the total weighted completion time of the scheduled job
\end{itemize}

Propose and implement an algorithm based on Dynamic Programming for this problem.

For a job $j$ starting at $s$, its completion time is equal to:
\begin{displaymath}
  C_j = s_j + p_j
\end{displaymath}
and its weighted completion time is equal to:
\begin{displaymath}
  w_j C_j = w_j (s_j + p_j)
\end{displaymath}

\section{Heuristic Tree Search}

We consider the Single machine order acceptance and scheduling problem with objective Total weighted tardiness:
\begin{itemize}
  \item Input:
    \begin{itemize}
      \item $n$ jobs with ($j = 1, \dots, n$)
        \begin{itemize}
          \item processing time $p_j \in \N^+$
          \item due date $d_j \in \N^+$
          \item profit $v_j \in \N^+$
          \item weight $w_j \in \N^+$
        \end{itemize}
    \end{itemize}
  \item Problem: find a sub-sequence of jobs
  \item Objective: maximize the total profit minus the total weighted tardiness of the scheduled job
\end{itemize}

For a job $j$ starting at $s$, its weighted tardiness is equal to:
\begin{displaymath}
  w_j T_j = w_j \max \left\{ 0, C_j - d_j \right\}
\end{displaymath}

Propose and implement an algorithm based on Heuristic Tree Search with Dynamic Programming for this problem.

\section{Column Generation \\ + Dynamic Programming}

We consider the Unrelated parallel machine scheduling problem with objective Total weighted completion time
\begin{itemize}
  \item Input:
    \begin{itemize}
      \item $m$ machines
      \item $n$ jobs with ($j = 1, \dots, n$)
        \begin{itemize}
          \item processing time $p_j^i \in \N^+$ for each machine $i = 1, \dots, m$
          \item weight $w_j \in \N^+$
        \end{itemize}
    \end{itemize}
  \item Problem: find a schedule for each machine such that
    \begin{itemize}
      \item each job is scheduled exactly once
    \end{itemize}
  \item Objective: minimize the total weighted completion time of the schedule
\end{itemize}

Propose an exponential formulation and implement an algorithm based on a Column Generation heuristic for this problem.

\section{Column Generation \\ + Heuristic Tree Search}

We consider the Unrelated parallel machine scheduling problem with objective Total weighted tardiness:
\begin{itemize}
  \item Input:
    \begin{itemize}
      \item $m$ machines
      \item $n$ jobs with ($j = 1, \dots, n$)
        \begin{itemize}
          \item processing time $p_j^i \in \N^+$ for each machine $i = 1, \dots, m$
          \item due date $d_j \in \N^+$
          \item weight $w_j \in \N^+$
        \end{itemize}
    \end{itemize}
  \item Problem: find a schedule for each machine such that
    \begin{itemize}
      \item each job is scheduled exactly once
    \end{itemize}
  \item Objective: minimize the total weighted tardiness of the schedule
\end{itemize}

Propose an exponential formulation and implement an algorithm based on a Column Generation heuristic for this problem.

\end{document}

max_stars_repo_path: 2021-2022 - M2 ORCO - Advanced OR/Projects/Parallel scheduling/subject/main.tex


text:
\begin{frame}{\ft{3D Graphics Sent to MeshLab}}
\section{Research Slide 2}

\doubleFrame{... Once the 3D tissue sample is constructed by 3DimViewer's algorithms,
an A3R inter-application networking protocol (implemented
as an extension to both components) allows 3DimViewer to
export the model to MeshLab so that it may be studied in a
more comprehensive 3D viewing environment.}

\begin{tikzpicture}
\nodeincludegraphicsTR{2.7cm}{2cm}{pics/RAD-3.png}

% \node [anchor=west,fill=brown!20!white,inner sep=7, text width=14cm]
%  (longnote) at (5.5,7) {%  %{\color{rb!85!red}{
%  {\cframedbox{\large \textbf{EC3}}}};

\end{tikzpicture}

\end{frame}

max_stars_repo_name: ScignScape-RZ/ntxh

max_issues_repo_name: ScignScape-RZ/ntxh

max_forks_repo_name: ScignScape-RZ/ntxh


text:
\section{Evaluation}
\label{sec:evaluation}
% 10. Describe how you have (or would have if given more time) evaluated your
%    language.

We evaluated the effectiveness of DeckBuild language as a game design tool for
both programmers and non-programmers by considering game designer productivity.

For this class project, we used ourselves as test subjects and performed an
informal evaluation of how easy it is to design cards using DeckBuild. We used
our DeckBuild language to describe all the existing cards from the base set of
Dominion \cite{DomCardList}. We found that specifying cards in our language was
easy and straightforward.

Given the limited scope of the semester, we could not attempt a more formal
evaluation of our language. If we had the time, there are a couple of possible
paths we could take. First, we could release the language, tools and runtime
system to game designers for them to use. We could gather an evaluation of our
current design and implementation by soliciting bug reports and feature
requests. This method of evaluation allows us to incrementally improve the
design that using the target users' wishes. In this scenario, we would measure
the success of our design in terms of the rate of adoption by our target users.

Another possible evaluation method would be to conduct more formal user studies.
We would identify one or more competing technologies and use this as a basis for
comparison. While this is more principled in theory, in practice we think that
this would be little benefit for a lot of effort. Finding suitable subjects
would be difficult as DeckBuild has a very niche target market.

max_stars_repo_name: cronburg/deckbuild-lang

max_issues_repo_name: cronburg/deckbuild-lang

max_forks_repo_name: cronburg/deckbuild-lang


text:
\section{System responses}
\subsection{}

\begin{frame}\mccz
\frametitleTC{Foreword}
\framesubtitleTC{}
\myPause
 \begin{columns}
  \column[T]{0.35\textwidth}
   \only<2->{\centering\includegraphics[height=6cm]{./Unit-04/img/response-intro_cc0.jpg}}\myPause%
  \column[T]{0.65\textwidth}
   \begin{itemize}[<+-| alert@+>]
   \item We know how to describe a (DT LTI) dynamic system
         \begin{itemize}[<+-| alert@+>]
         \item in the state space with $(A,b,c,d)$
         \item and with a transfer function $G(z)$.
         \end{itemize}
   \item But how do these descriptions relate to the way\\
         the system responds to a certain \emph{stimulus}?
   \item Specifically for our purpose, can we somehow\\
         relate a transfer function to its\\
         \TC{time (domain) responses}?
   \item \vspace{3mm} Of course we can.
   \item Let us see first how and then why.
   \end{itemize}
 \end{columns}
\end{frame}

\begin{frame}
\frametitleTC{Foreword}
\framesubtitleTC{An introductory case}
\myPause
 \begin{itemize}[<+-| alert@+>]
 \item We showed that as long as a system has only real eigenvalues, its transfer function can be
       expressed as sum/product of elementary first order terms in the form
       \begin{displaymath}
        g(z) = \frac{\mu}{z-p}
       \end{displaymath}
 \item NOTE: if all eigenvalues are distinct, a sum (no products) of terms\\
       like the above suffices.
 \item Given the linearity of the system, responses will sum together the\\
       same way as elementary terms in the transfer function do.
 \item We therefore start by analysing the responses of $g(z)$ above\\
       to a unit impulse and a unit step.
 \item We deal with TI systems, hence in the following everything starts\\
       at $k=0$.
 \end{itemize}
\end{frame}

\begin{frame}
\frametitleTC{An introductory case}
\framesubtitleTC{Impulse response of $g(z)$}
\myPause
 \begin{itemize}[<+-| alert@+>]
 \item Recalling the meaning of $z$, $g(z)$ in the time domain means
       \begin{displaymath}
        y(k) = p y(k-1) + \mu u(k-1).
       \end{displaymath}
 \item Set now $u(k)=imp(k)$, i.e., the sequence $\{1,0,0,0,\ldots\}$. We assume no action on the system
       before $k=0$, consistently with the definition of impulse. We also assume the system at rest, otherwise
       there is free motion and we don not see ONLY the response to $u$, hence $y=0$ for $k<0$.
 \item This said, we get
       {\small
       \begin{displaymath}
        \begin{array}{lclclclclcl}
         y(0) &=& p y(-1) + \mu u(-1) &=& p \cdot 0     + \mu \cdot 0 &=& 0       \\
         y(1) &=& p y(0)  + \mu u(0)  &=& p \cdot 0     + \mu \cdot 1 &=& \mu     \\
         y(2) &=& p y(1)  + \mu u(1)  &=& p \cdot \mu   + \mu \cdot 0 &=& \mu p   \\
         y(3) &=& p y(2)  + \mu u(2)  &=& p \cdot \mu p + \mu \cdot 0 &=& \mu p^2 \\
         \ldots
        \end{array}
       \end{displaymath}
       }
 \item \vspace{-4mm}i.e., the sequence $\{0,\mu,\mu p,\mu p^2,\mu p^3,\ldots\}$.
 \end{itemize}
\end{frame}

\begin{frame}[fragile]
\frametitleTC{An introductory case}
\framesubtitleTC{Impulse response of $g(z)$}
\myPause
 \begin{itemize}[<+-| alert@+>]
 \item Summarising, the impulse response of $g(z)$ is
       \begin{displaymath}
        y(k) = \begin{cases}
                0           & k=0 \\
                \mu p^{k-1} & k>0
               \end{cases}
       \end{displaymath}
 \item Let us compute and plot this response with Scilab:
       {\small
       \begin{verbatim}
 g   = syslin('d',1/(%z-0.5)); // define transfer function ('d' means DT)
 gss = tf2ss(g);               // convert to state space for dsimul
 u   = [1,0,0,0,0,0,0,0,0,0];  // impulse sequence (10 samples)
 y   = dsimul(gss,u);          // compute response
 plot(y,'.');                  // plot (as dots)
       \end{verbatim}
       }
 \item Try different values of $\mu$ and $p$, and comment on the results.
 \end{itemize}
\end{frame}

\begin{frame}
\frametitleTC{An introductory case}
\framesubtitleTC{Impulse response of $g(z)$ -- general remarks}
\myPause
 \begin{itemize}[<+-| alert@+>]
 \item The pole $p$ governs stability as we already know.
 \item For $p=0$ the system is a pure one-step delay.
 \item For $0<p<1$ the response converges monotonically, for $-1<p<0$ oscillating.
 \item In both cases, $p$ governs the convergence speed.
 \item For $p=1$ the response is constant, for $p=-1$ a sustained oscillation\\
       (in both cases for $k>0$, obviously).
 \item Parameter $\mu$ acts as a (signed) scale factor.
 \end{itemize}
\end{frame}

\begin{frame}
\frametitleTC{An introductory case}
\framesubtitleTC{Step response of $g(z)$}
\myPause
 \begin{itemize}[<+-| alert@+>]
 \item Set $u(k)=step(k)$, i.e., the sequence $\{1,1,1,1,\ldots\}$.
 \item We can verify that this yields the response
       \begin{displaymath}
        y(k) = \frac{\mu}{1-p}(1-p^k)
       \end{displaymath}
 \item To this end, we observe that with $\mu=1-p$ we get $y(k) = 1-p^k$:
       {\scriptsize
       \begin{displaymath}
        \begin{array}{lclclclclcl}
         y(0) &=& p \cdot 0       + (1-p) \cdot 0 & &           &=& 0     \\
         y(1) &=& p \cdot 0       + (1-p) \cdot 1 & &           &=& 1-p   \\
         y(2) &=& p \cdot (1-p)   + (1-p) \cdot 1 &=& p-p^2+1-p &=& 1-p^2 \\
         y(3) &=& p \cdot (1-p^2) + (1-p) \cdot 1 &=& p-p^3+1-p &=& 1-p^3 \\
         y(4) &=& p \cdot (1-p^3) + (1-p) \cdot 1 &=& p-p^4+1-p &=& 1-p^4 \\
         y(5) &=& p \cdot (1-p^4) + (1-p) \cdot 1 &=& p-p^5+1-p &=& 1-p^5 \\
         \ldots
        \end{array}
       \end{displaymath}
       }
 \item \vspace{-4mm}Hence a generic $\mu$ scales $y$ to give the result above.
 \end{itemize}
\end{frame}

\begin{frame}[fragile]
\frametitleTC{An introductory case}
\framesubtitleTC{Step response of $g(z)$}
\myPause
 \begin{itemize}[<+-| alert@+>]

 \item Also for the step response case, let us compute and plot some examples with Scilab:
       {\small
       \begin{verbatim}
 g   = syslin('d',1/(%z-0.5)); // define transfer function ('d' means DT)
 gss = tf2ss(g);               // convert to state space for dsimul
 u   = ones(1,10)              // step sequence (a row of 10 samples)
 y   = dsimul(gss,u);          // compute response
 plot(y,'.');                  // plot (as dots)
       \end{verbatim}
       }
 \item Try again different values of $\mu$ and $p$, and comment on the results.
 \end{itemize}
\end{frame}

\begin{frame}
\frametitleTC{An introductory case}
\framesubtitleTC{Step response of $g(z)$ -- general remarks}
\myPause
 \begin{itemize}[<+-| alert@+>]
 \item The pole $p$ governs stability as we already know.
 \item For $p=0$ the system is a pure one-step delay.
 \item For $0<p<1$ the response converges monotonically, for $-1<p<0$ oscillating.
 \item In both cases, $p$ governs the convergence speed.
 \item For $p=1$ the response is a diverging ramp, for $p=-1$ a sustained oscillation.
 \item If $y(k)$ converges, it does so to the value
       \begin{displaymath}
        \frac{\mu}{1-p} = g(1)
       \end{displaymath}
       that is called the \TC{gain} of the transfer function.
 \item Hence for an asymptotically stable $g(z)$, if for $k\rightarrow\infty$ $u(k)\rightarrow\overline{u}$,\\
       then $y(k)\rightarrow g(1)\overline{u}$.
 \end{itemize}
\end{frame}

\begin{frame}
\frametitleTC{Generalisation}
\framesubtitleTC{}
\myPause
 \begin{itemize}[<+-| alert@+>]
 \item In the same way we treated the elementary term $g(z)$, we could address a generic transfer function.
 \item However
       \begin{itemize}[<+-| alert@+>]
       \item as long as there are single poles (eigenvalues), the response will be a linear
             combination of terms like those yielded by $g(z)$,
       \item while multiple eigenvalues (poles) can be treated like we did from slide~\ref{pag:ex-realisation}
             onward (enough on this for our purposes),
       \item and complex poles could be a nice exercise for the interested \smiley\\
             although here we do not address them either.
       \end{itemize}
 \item We do not treat the most general case, nonetheless we go through\\
       one non-elementary example as this allows for useful considerations.
 \end{itemize}
\end{frame}

\begin{frame}
\frametitleTC{Generalisation}
\framesubtitleTC{One model class, some particular cases}
\myPause
 \begin{itemize}[<+-| alert@+>]
 \item Take the class of transfer functions with up to two poles and one zero
       \begin{displaymath}
        G(z) = \frac{b_0+b_1z}{a_0+a_1z+a_2z^2}
       \end{displaymath}
 \item and specialise it to the four cases
       \begin{displaymath}
        \begin{array}{c}
         G_A(z) = \cfrac{1}{z}, \qquad
         G_B(z) = \cfrac{0.5}{z-0.5}, \qquad
         G_C(z) = \cfrac{(1-0.25)^2}{1-0.55} \, \cfrac{z-0.55}{(z-0.25)^2}, \\ \\
         G_D(z) = \cfrac{2.5-1}{(1-0.5)^2} \, \cfrac{2.5-z}{(z-0.5)^2}.
        \end{array}
       \end{displaymath}
 \item Notice that for clarity in the following plots they all have unity\\
       gain, i.e., $G_{A,B,C,D}(1)=1$.
 \end{itemize}
\end{frame}

\begin{frame}
\frametitleTC{Generalisation}
\framesubtitleTC{One model class, different responses}
\myPause
 \begin{itemize}[<+-| alert@+>]
 \item The corresponding four (unit) step responses are plotted below with the so-called\\
       ``staircase'' style:
       \begin{center}
        \includegraphics[width=0.50\columnwidth]{./Unit-04/img/StepRespTypes.pdf}
       \end{center}
 \item \vspace{-3mm} Let us try to provide some possible interpretation.
 \end{itemize}
\end{frame}

\begin{frame}
\frametitleTC{Generalisation}
\framesubtitleTC{One model class, different responses}
\myPause
 \begin{columns}
  \column[T]{0.45\textwidth}
   \only<2->{\includegraphics[height=5.5cm]{./Unit-04/img/StepRespTypes.pdf}}
  \column[T]{0.55\textwidth}
   \begin{itemize}[<+-| alert@+>]
   \item Suppose $u(k)$ and $y(k)$ to be respectively a resource to allot and its effect.
         \begin{itemize}[<+-| alert@+>]
         \item[A.] The resource is acquired and exerts immediately its effect (that is therefore
                   seen at the very next step).
         \item[B.] The resource acts immediately but takes some steps to yield its full effect\\
                   (for example because first\\
                   some queue needs\\
                   emptying).
         \end{itemize}
   \end{itemize}
 \end{columns}
\end{frame}

\begin{frame}
\frametitleTC{Generalisation}
\framesubtitleTC{One model class, different responses}
 \begin{columns}
  \column[T]{0.45\textwidth}
   \only<1->{\includegraphics[height=5.5cm]{./Unit-04/img/StepRespTypes.pdf}}
  \column[T]{0.55\textwidth}
   \begin{itemize}[<+-| alert@+>]
   \item Suppose $u(k)$ and $y(k)$ to be respectively a resource to allot and its effect.
         \begin{itemize}[<+-| alert@+>]
         \item[C.] The resource produces a transiently enhanced effect (this is quite typical
                   when the resource is computational power and the effect is the \emph{speed} toward a goal).
         \item[D.] The resource requires some effort to be acquired and initially \emph{reduces}
                   performance, like a new\\
                   core that when acquired\\
                   has an unknown cache\\
                   content, thus causing\\
                   a lot of cache misses.
         \end{itemize}
   \end{itemize}
 \end{columns}
\end{frame}

\begin{frame}
\frametitleTC{Generalisation}
\framesubtitleTC{Lessons learnt and next steps}
\myPause
 \begin{itemize}[<+-| alert@+>]
 \item One model can produce very different responses \TC{by just changing parameters}, thus fitting
       several physical cases --- remember the remark in the introductory section, that we need a systems
       and control theory because determining a controller is largely physics-independent?.
 \item \vspace{3mm} We shall now see how control requirements can be stipulated by saying that some response
       to some \emph{stimulus} should have a certain aspect.
 \item We shall then convert this into requiring some \TC{transfer function}\\
       to have a certain aspect...
 \item ...and finally start synthesising feedback controllers.
 \end{itemize}
\end{frame}


text:
\documentclass[11pt,a4paper]{article}
\usepackage[margin=0.5in, bottom=1.75cm]{geometry}
\usepackage{caption}
\usepackage{tabu}
\usepackage[hidelinks]{hyperref}

\captionsetup[figure]{labelfont=bf}
\captionsetup[table]{labelfont=bf}

\bibliographystyle{ieeetr}

\title{\vspace{-2em}Blockchain and Cryptocurrencies Coursework}
\author{pbqk24}
%\date{}

\begin{document}
	\maketitle

	\vspace{-3em}

	\section{Mining Puzzles}

	\subsection{Proof of Work}
	The requested information for Proof of Work is as follows:

	\begin{table}[h!]
		\centering
		\begin{tabu} to 1.0\linewidth {|r|p{8cm}|X[l]|}
			\hline
			Index&Information&Value\\
			\hline
			1&User ID&pbqk24\\
			\hline
			2&Block hash target calculated (hex)&000003e7fc1800000000000000000000\newline00000000000000000000000000000000\\
			\hline
			3&Nonce value (int)&$2171906$\\
			\hline
			4&Number of (double) hashes performed&$2171907$ (one per nonce tried, starting at 0)\\
			\hline
			5&Estimate for mining time for difficulty $= 1$&$58629$ seconds\\
			 &Estimate for mining time for difficulty $= 7454968648263$&$4.37*10^{17}$ seconds\\
			\hline
		\end{tabu}
		\caption{Mining Puzzles: Information Requested}
		\label{table_mining_puzzles_pow}
	\end{table}

	\noindent The equations used for calculating the mining time estimates $t$ are as follows:

	\begin{equation}
	target = \frac{target_{initial}}{difficulty}
	\end{equation}

	\begin{equation}
	h_q = \frac{h_{space}}{target}
	\end{equation}

	\begin{equation}
	t = h_q * t_h
	\end{equation}

	Where $h_q$ is the estimated number of hashes required to be performed to find a valid hash, $target$ is the target value, $t_h$ is the estimated time per hash calculated by timing how long it takes to perform a large number of hashes (e.g. $10^9$) and finding the average. $t_h$ was computed as $1.365*10^{-5}$ and used for both calculations.

	For difficulty of $1$:

	$$target = \frac{00000000FFFF0000000000000000000000000000000000000000000000000000}{1}$$

	$$h_q = \frac{2^{256}}{00000000FFFF0000000000000000000000000000000000000000000000000000} = 4295032833$$

	$$t = 4295032833 * 1.365*10^{-5} = 58629$$

	For difficulty of $7454968648263$:

	$$target = \frac{00000000FFFF0000000000000000000000000000000000000000000000000000}{7454968648263} = 3.62*10^{54}$$

	$$h_q = \frac{2^{256}}{3.62*10^{54}} = 3.2 * 10^{22}$$

	$$t = 3.2 * 10^{22} * 1.365*10^{-5} = 4.37*10^{17}$$

	\subsection{Proof of Stake}

	The requested information for Proof of Stake is as follows:

	\begin{table}[h!]
		\centering
		\begin{tabu} to 1.0\linewidth {|r|p{7cm}|X[l]|}
			\hline
			Index&Information&Value\\
			\hline
			6&ECDSA public key (hex)&4f045a6cfacb3e67e7c5d4ddfb9f1acfe7d6ddda\newline c29869734cce5218cdab24e2d2cc72601138d6f\newline 324464df7691f819cd14e8b3752d9c463e5162a\newline ad37393ca0\\
			\hline
			7&Signature of "Hello world" (hex)&eae12ab8fdbeb5635ac45edbfceb999907a5b090\newline 42eeddbd9a07a744f656b3ac7e00124086256e5\newline caf86539e68186742d593e5e8b537b9f6d7ee055\newline 57c2ef68a\\
			\hline
			8&Signature used in calculating hit (hex)&aa2974089248c51977f63350c3aad2757b935d68\newline a236dd777621c3ed879657d2c5e1f01d22ad16b\newline b2d37f1c2567d1daeccd4e3f1a45201f53291e2e\newline ba9e9bea3\\
			\hline
			9&Hit value (hex)&a135a0781dd3c0f6\\
			\hline
			10&Time (s) that you could forge a new block&394\\
			\hline
		\end{tabu}
		\caption{Mining Puzzles Information}
		\label{table_mining_puzzles_pos}
	\end{table}

	\noindent The equations used for calculating the hit value are as follows:

	\begin{equation}
	hit_{full} = hash(sign(S_g))
	\end{equation}

	Where the hit value is the first 8 bytes of $hit_{full}$, and $S_g$ is the generation signature for the previous block:

	$$S_g = 9737957703d4eb54efdff91e15343266123c5f15aaf033292c9903015af817f1$$

	$$sign(S_g) = aa2974089248c51977f63350c3aad2757b935d68a236dd777621c3ed879657d2c5e1f01d22ad16bb2d37f1$$

	\vspace{-2.5em}$$c2567d1daeccd4e3f1a45201f53291e2eba9e9bea3$$

	$$hash(sign(S_g))[:8] = a135a0781dd3c0f6$$

	\noindent The time in seconds when you would be able to forge a new block was calculated using the following equations:

	\begin{equation}
	T = T_b * B_e
	\end{equation}

	\begin{equation}
	t_{forge} = \frac{hit}{T}
	\end{equation}

	Where $T$ is the target value (independent of time passed), $T_b$ is the base target value, $B_e$ is your effective balance, and $t_{forge}$ is the time when you can forge a new block (rounded up, in seconds):

	$$T = 1229782938247303 * 24 = 29514790517935272$$

	$$t_{forge} = \frac{11616367251628998902}{29514790517935272} = 394$$

	\section{Interacting with bitcoin-testnet}

	The requested information for Task 2 is included in Table \ref{table_bitcoin_testnet} and \ref{table_bitcoin_testnet_transactions} below.

	\begin{table}[h!]
		\centering
		\begin{tabu} to 1.0\linewidth {|r|l|X[l]|}
			\hline
			Index&Information&Value\\
			\hline
			1&User ID&pbqk24\\
			\hline
			2&blockchain.com links&This is included in Table \ref{table_bitcoin_testnet_transactions} below\\
			\hline
			3&Transaction explanations&This is included in Table \ref{table_bitcoin_testnet_transactions} below\\
			\hline
			4&bitcoin-testnet address&mvcM9NV5hesnSUNpZGZ9Pyt3PK8xDFmCTp\\
			\hline
			5&100 Satoshi Tx ID&bfb4090faca08fe0f1ca46883cef1bf7e7860a4df6637acb7962741db0206f29\\
			&chain.so hyperlink&\href{https://chain.so/tx/BTCTEST/bfb4090faca08fe0f1ca46883cef1bf7e7860a4df6637acb7962741db0206f29}{https://chain.so/tx/BTCTEST/bfb4090faca08fe0f1ca46883cef1bf7e78\newline 60a4df6637acb7962741db0206f29}\\
			\hline
			6&Proof of Burn Tx ID&611186bc95e29fc70127fce35bd9c8a7f86c46f00aecd9df4765731d27f64d31\\
			&chain.so hyperlink&\href{https://chain.so/tx/BTCTEST/611186bc95e29fc70127fce35bd9c8a7f86c46f00aecd9df4765731d27f64d31}{https://chain.so/tx/BTCTEST/611186bc95e29fc70127fce35bd9c8a7f8\newline6c46f00aecd9df4765731d27f64d31}\\
			\hline
			7&Hex used as script&6a067062716b323\\
			&Explanation of hex script&This script is equivalent to `OP\_RETURN 06 7062716b323'. This causes the transaction to always be marked invalid, as OP\_RETURN always outputs \emph{fail}. The `06' signals that the next 6 bytes are to be pushed onto the stack, and `7062716b323' is the result of converting `pbqk24', my USER ID, from ASCII to hex.\\
			\hline
		\end{tabu}
		\caption{Bitcoin-Testnet Information}
		\label{table_bitcoin_testnet}
	\end{table}

	\begin{table}[h!]
		\centering
		\begin{tabu} to 1.0\linewidth {|r|l|X[l]|}
			\hline
			Tx&Aspect&Explanation\\
			\hline
			1&blockchain.com link&\href{https://www.blockchain.com/btc/tx/6c260da65fe98b08b27b80f8481c6f0ae34252921f6c34d327172472c5b419d7}{https://www.blockchain.com/btc/tx/6c260da65fe98b08b27b80f8481c6f0ae\newline 34252921f6c34d327172472c5b419d7}\\
			\hline
			&Input scripts&There is no input script since the coins are newly generated.\\
			\hline
			&Output scripts&There are three output scripts: one specifying the receiver of the mined bitcoin, one using OP\_RETURN to push data onto the blockchain (not decodable as text), and one that seems to have produced an error when decoding the script (but similarly to the second one, it transfers no coins).\\
			\hline
			&Inferences from structure&This is a transaction claiming the mining reward of (at the time) $\sim12.6$BTC (including transaction fees). This can be inferred as there is no input script, thus this transaction is the miner's claiming their reward.\\
			\hline
			2&blockchain.com link&\href{https://www.blockchain.com/btc/tx/4a3751b29128bea458f7f07d4f92b29322ba1900bbc364130bf2648e73f8cfad}{https://www.blockchain.com/btc/tx/4a3751b29128bea458f7f07d4f92b2932\newline 2ba1900bbc364130bf2648e73f8cfad}\\
			\hline
			&Input scripts&There is a single input script, which includes a witness.\\
			\hline
			&Output scripts&There are a large number of output scripts, most simply checking the hash of the receiver's address is valid, and a few additionally verifying and checking the signature.\\
			\hline
			&Inferences from structure&As this transaction has a single input, multiple outputs, and pays a large sum ($\sim1.7$ BTC), I suspect that this is payout from a mining guild, or possibly a sale of bitcoin by an exchange.\\
			\hline
			3&blockchain.com link&\href{https://www.blockchain.com/btc/tx/496cda9b0f4083b7775822f07a1541176866947b9f93006752de029489e1abd6}{https://www.blockchain.com/btc/tx/496cda9b0f4083b7775822f07a1541176\newline 866947b9f93006752de029489e1abd6}\\
			\hline
			 &Input scripts&This transaction contains a large number of input scripts. Most of these have a small input amount, with three being notably large: $\sim1, \sim4.3,$ and $\sim25$ bitcoin. All input scripts are from the same address.\\
			\hline
			 &Output scripts&The transaction contains two output scripts. One claims $\sim13.2$ BTC, and the other $22.5$ BTC.\\
			\hline
			 &Inferences from structure&Due to the amounts involved, and the exact payment of $22.5$ BTC to the second output address, I suspect that this transaction is a user selling BTC to an exchange. This is supported by investigating the recipient address of the $22.5$ BTC, which shows it being involved in numerous high-value transactions, where the address seems to mainly be used as a middle man, often transferring the exact input amount onwards to another address.\\
			\hline
		\end{tabu}
		\caption{Bitcoin-Testnet Transactions Details}
		\label{table_bitcoin_testnet_transactions}
	\end{table}

	\section{Investment Advice: Bitcoin, NXT or Gold}

	The judgment of what to invest in depends on your reasons for investing. Firstly, if you are investing to maintain value then gold would be the best candidate. The value of gold rarely fluctuates, and it has some value as a material outside of being used as currency. It is also the most durable of these options, as it is not reliant on any technology or network in order to have worth and be useable. Even in extreme circumstances such as financial collapse, gold will maintain value as a currency, while any cryptocurrency may see its value plummet or become invalid due to collapse of its network or userbase.

	If you are investing for short-term returns, then NXT is a good candidate. Over the past few months both Bitcoin and NXT have started to increase in value \cite{coinmarketcap}. Out of these two NXT has risen faster, and due to its technical advantages over Bitcoin, such as using Proof of Stake rather than Proof of Work making it less wasteful to operate and more expensive to attack, and its ability to trade any asset on its network, it has more utility than Bitcoin. This theoretically gives NXT an edge over Bitcoin, meaning it should steal market share and users from it over time. However, will not necessarily happen due to the popularity of Bitcoin. Even though Bitcoin is an inefficient and outdated cryptocurrency, the fact that it was the first to gain widespread popularity and support cannot be ignored. It currently holds the largest market cap of any cryptocurrency, and is unlikely to lose popularity quickly \cite{coinmarketcap}.

	Additionally, there is a large number of cryptocurrencies available, most of which have at least some technical merits over Bitcoin, and some of which are improvements on NXT, which NXT is competing with as well. This means it is extremely unlikely for NXT to become a true Bitcoin equal, and its value is likely to stay volatile. This means that investing in NXT could see short-term profits, but these are unlikely to be sustainable in the long-term.

	The popularity of Bitcoin may also be a detriment when it comes to investment, however. Due to its technical shortcomings, Bitcoin can only process a handful of transactions per second, with long delays before a transaction is confirmed. This means that the more popular the cryptocurrency becomes, the more expensive transactions will become due to fees needed to ensure the transaction is confirmed within a reasonable time period. This will likely cap the potential market cap and value of Bitcoin in the future, which limits its investment opportunities. Even worse, this effect may result in people becoming aware of its technical shortcomings, and moving to other cryptocurrencies, leading to a massive crash in users, market cap, and value.

	Because of the reasons outlined above, I would recommend investing in Bitcoin for potential profit, and gold for maintaining value. Due to the large number of competing cryptocurrencies, and small current market cap, I would not recommend investing in NXT \cite{coinmarketcap}.

	\pagebreak

	\section{An analysis of XRP (Ripple)}

	\subsection{Idea and Justification for Creation}

	XRP, commonly referred to as Ripple, is a decentralized cryptocurrency used as part of the XRP Ledger. It was initially released in 2012, intended as a currency exchange and transfer system for financial institutions \cite{finder}. Ripple Labs Inc., the developer of XRP, uses it as part of their solutions and offerings to financial institutions. The idea behind its creation was to allow fast, cheap, and reliable international transactions, which currently can take up to 5 business days and cost as much as 6\% in commission fees \cite{topcryptocurrencies}. Any currency beyond XRP can be represented and traded on the XRP Ledger as `issued currencies,' which can be traded for each other or for XRP, and can represent any item, not just traditional currency.

	\subsection{Technical Differences to Bitcoin}

	XRP differs significantly from Bitcoin in many regards. Firstly, unlike in Bitcoin and many other blockchain technologies, nodes do not need to store the entire history of the blockchain in order to track its current state. XRP uses a ledger system, where each ledger stores the entire current state of the system \cite{rippledevelopers}. This means that the cost in terms of storage for each node is reduced. Every ledger is produced by a set of transactions that are applied to the previous ledger. The new ledger is then summarized using a hash tree and compared across the nodes \cite{bitcoinmagazine}. A consensus is reached using the XRP Ledger Consensus Protocol (XRP LCP), which ensures that all nodes agree on the set of transactions, and a transaction processing protocol that is followed by each node to produce the same ledger based on this set \cite{Chase}. The XRP LCP is designed to ensure that all users of the XRP Ledger reach an agreement on the state of the ledger, all valid transactions are processed, transactions can be processed even if some participants are missing or behaving nefariously, and to avoid requiring large amounts of resources to be spent \cite{rippledevelopers}. This is a key difference from Bitcoin, which requires massive amounts of processing power (and thus energy) to be spent for each new block to be produced.

	In Bitcoin, anyone can set up a system to begin mining and be a part of creating the next block. XRP differs from this in that it uses validated servers to reach the consensus to produce the next ledger. Only trusted servers, those present in a participant's Unique Node List (UNL) are considered when determining if a given transaction or ledger is valid. While participants can freely choose which servers are in their UNL, Ripple Labs publishes a recommended UNL. This presents a barrier to entry for any party wanting to join the consensus system, and makes XRP much less decentralized than Bitcoin and other cryptocurrencies.

	Another major difference between Bitcoin and XRP is in the transaction fees. In Bitcoin, transaction fees are voluntarily added by the source of the transaction, and any fees included in transactions in a mined block can be collected by the miner in full. In practice, transaction fees are mandatory if a user wants their transaction included within a reasonable amount of time. The typical transaction fee is completely controlled by market forces and varies with the network congestion. For reference, the estimated fee for a transaction to be included in the next block at the time of writing was $\sim\$0.30$ \cite{bitcoinfees}. On the other hand, XRP has a mandated minimum transaction fee of $0.00001$ XRP per transaction built into the protocol (at the time of writing this was equivalent to $\sim\$0.0000031$). Additionally, this fee is burned, rather than being collected as in Bitcoin. The minimum transaction fee scales with the current load on the network. In XRP, this transaction fee serves two purposes: firstly, it discourages attacks on the network attempting to overload it with transactions, both intentional and unintentional. Secondly, in burning the XRP paid for the fee it makes all remaining XRP more valuable \cite{transactioncost}. This makes XRP a deflationary currency, as there is a finite supply of the coin.

	In addition to the differences above, XRP is also much faster and has a higher throughput than Bitcoin. The XRP Ledger is one of the fastest blockchains currently, being able to confirm a transaction in under four seconds \cite{investinblockchain}. Bitcoin, on the other hand, can take longer than an hour before a transaction is considered confirmed, as a transaction is usually only considered to be completed when it has been present in several consecutive blocks. XRP can currently handle up to $1500$ transactions per second, giving it a much higher transaction capacity than Bitcoin, which can only process $\sim7$ transactions per second \cite{blocksplain}. This makes XRP much better suited as a transaction processing system and currency than Bitcoin. Additionally, according to Ripple Labs XRP has the capability to scale to handle as many transactions per second as Visa ($50000$) \cite{ripple}.

	\subsection{Mining Ripple}

	Unlike Bitcoin, Ripple is not designed to be mined, and no reward is given to nodes for helping produce the next ledger \cite{cointelegraph}. $100$ billion XRP were initially created by its creator, Ripple Labs, and no new XRP can ever be created. Out of these, roughly $38$ billion are currently available with the rest being held by Ripple Labs, most of them in escrow to be released at a rate of $1$ billion per month \cite{finder}. This also means that there is no financial incentive to operating a validator server, as there is no reward in XRP for doing so. Instead, the reward given to validators is in being a part in controlling the network, and deciding on the future evolution of the network. Ripple Labs' justification for this being a viable system is that the only cost to running a server is the electricity it consumes, which is extremely low compared to a Bitcoin mining rig - roughly equivalent to running an email server \cite{technicalFAQ}. In addition to this, institutions or individuals that rely on the XRP Ledger, for example for financial transactions, are incentivised to operate servers in order to ensure its reliability and stability. If already runnning a server, the additional cost to run a validator is negligible \cite{technicalFAQ}. However, this design also further reduces the extent to which XRP is decentralized.

	\subsection{Performance}

	Despite its technical advantages over Bitcoin, XRP has failed to outperform the more popular coin. It briefly held a price of $\sim\$0.2$ per XRP for the second half of 2017, before rapidly climbing to a peak value of $\$3.84$ in early 2018, and rapidly falling down to just below $\$1$. Since this peak, the price of XRP in USD has been on a slow but steady decline. Bitcoin has similarly been declining after a massive peak in price around the same time, but has seen a small increase in the last month which XRP has failed to mimic. XRP currently holds a fairly stable market cap of $\sim\$13$ billion, while Bitcoin is at nearly $\$80$ billion \cite{coinmarketcap}.

	While XRP is not performing as well as Bitcoin recently, compared to the general cryptocurrency market it is performing favourably. It remains at the number 3 spot in terms of market cap, being only $\$1$ billion behind Ethereum at number two, and comfortably $\sim\$9.5$ billion ahead of Litecoin at number four. Additionally, most cryptocurrencies have seen a small slump over the past few days, which XRP has begun to recover from faster than many others.

	\subsection{Notable Attacks and Events}

	Ripple has so far mostly managed to stay out of the limelight and has not been the victim of any major attacks. According to Ripple Labs' CTO David Schwartz, this is because of the consensus protocol used in the XRP Ledger, which makes it immune to `51\%' attacks that many other cryptocurrencies have suffered from \cite{newsbtc}. However, this does not mean that XRP is without controversy. One common source of worry is the fact that Ripple Labs owns $\sim60$ billion of the $100$ billion XRP in existence. Most of these ($\sim55$ billion) are locked in escrow accounts, scheduled to be released $1$ billion per month over the next $55$ months. Ripple Labs have stated that the reason for their holding this many XRP is to incentivize the company to continue development of XRP Ledger to the best of their ability \cite{technicalFAQ}, but many users worry that this gives them extreme powers over the cryptocurrency, breaking the principles of decentralization. For example, Ripple Labs have the ability to drastically affect the price of XRP by releasing a large amount of their holdings, at any time \cite{investinblockchain}. Another source of worry is the design choices limiting decentralization discussed previously, such as most validated servers being controlled by financial institutions. This goes against a common drive behind interest in cryptocurrencies and blockchain: independence from banks and governments.

	A major event that affected XRP occurred in May of 2018, when Ripple Labs was named in a lawsuit filed in the state of California, USA. This lawsuit alleged that Ripple Labs ran a scheme to collect hundreds of millions of dollars by generating XRP and trading them in unregistered sales in a ``never-ending initial coin offering'' \cite{bloomberg}. The lawsuit is based on the idea that XRP tokens act more like stock for Ripple Labs than a traditional cryptocurrency, and as such should be subject to more strict controls and regulations \cite{blockexplorer}. As of November 2018, the lawsuit is still ongoing.

	\subsection{Assessment of XRP and Conclusion}

	While XRP has many technological advantages over Bitcoin, such as drastically faster transaction confirmation speeds and higher transaction throughput, many design choices that contribute to these feats may severely restrict its potential as a cryptocurrency. Although XRP technically is a decentralized cryptocurrency, in practice this ideal is violated by the fact that Ripple Labs control $\sim62\%$ of all XRP, and that ledger consensus is carried out by a select few parties, and there are large barriers to becoming one of these parties. Lastly, while many see XRP's connection to Ripple Labs and their financial services as a positive regarding its feasibility and stability, XRP is not necessary to the operation of the XRP Ledger due to the issued currencies mentioned earlier. Thus, this connection has no impact on the utility and value of XRP as a cryptocurrency.

	\bibliography{bibliography}

\end{document}

max_stars_repo_name: Hoclor/Blockchain-Investigation

max_issues_repo_name: Hoclor/Blockchain-Investigation

max_forks_repo_name: Hoclor/Blockchain-Investigation