text:
\section{Introduction}
\label{intro}
Graphs are ubiquitous data structures.
Many real-world relations are formulated
as graphs and graph algorithms are used to
derive various characteristics related to those
relations. Applications such as social networks,
web search and scientific computing etc.,
use graph algorithms to derive useful information about graphs.
As for many other data, graph relations are
also growing so that they cannot be fit into
a graph data structure in a single process.
Those graphs need to be distributed
among several
computing resources and must be processed in
parallel.

Designing, implementing and analyzing distributed memory
parallel algorithms is inherently a difficult task
due to several reasons: 1. distributed memory
parallel algorithms depend on the data distribution
used, 2. designing and implementing proper mutual
exclusion and locking methods for distributed memory
systems is hard, 3. graphs are irregular in memory
access pattern. Therefore, the performance
of graph algorithms is not predictable as in
for other regular algorithms, 4. due to irregularity,
graph algorithms heavily depend on the underlying
run-time and the architecture.

To provide better solutions to above
challenges, abstractions that help to understand the nature
of distributed memory parallel graph algorithms are
important. Developing such abstractions is difficult,
due to the discrepancy between the solution approaches
used in those distributed memory
parallel graph algorithms.
For example, \textit{Dijkstra's Single Source Shortest Path}~\cite{dijkstra1959note}
algorithm starts from a given source vertex and
spread its search through neighbors, but \textit{Bor\r{u}vka's Minimum Spanning Tree}~\cite{nevsetvril2001otakar}
algorithm rely on set operations (disjoint union) to calculate the
Minimum Spanning Tree (MST).
While Bor\r{u}vka's Minimum Spanning Tree (MST) uses set
operations in its solution, the Dijkstra's Single Source Shortest Path (SSSP)
algorithm relies on priority based ordering of distances of neighbors
to calculate the SSSP.
Therefore, the solution approach used in Dijkstra's
SSSP
is different from the solution approach used in Bor\r{u}vka's
MST algorithm.

\begin{figure}
\centering
\includegraphics[width=.75\linewidth]{classification.pdf}
\caption{Graph algorithm classification based on their solution approach.}
\vspace{-5ex}
\label{fig:classes}
\end{figure}

Based on the solution
approach, we classify parallel graph algorithms into four categories (Figure~\ref{fig:classes}):
1. Data-driven algorithms
2. Iterative algorithms
3. Set operations based algorithms
4. Nested parallel algorithms.

\textit{Data-driven algorithms} associate
a \textit{state} to each vertex. At the start of the algorithm,
vertex states are initialized to a specific
value. The algorithm starts by changing the states of a subset of
vertices. Whenever a vertex state is changed, its neighbors
are notified. The state change is spread by notifying changes
to neighbors. Towards to end of the algorithm, state changes will
be reduced and states reach a fixed point. When there is no
more state changes the algorithm terminates. An example of
a data-driven algorithm is the Dijkstra's SSSP.

As in data-driven algorithms,
\textit{iterative algorithms} also associate a state to a vertex, but
instead of starting
from a subset of vertices, iterative algorithms
refine states associated with all vertices
several iterations
until all vertex states satisfy a defined condition.
For example, in \textit{PageRank}~\cite{page1999pagerank},
the rank is calculated in iterations until rank values associated
with all vertices are less than the defined error value. \textit{Shiloach-Vishkin
Connected Components} (CC)~\cite{shiloach1982logn} is another
example of an iterative algorithm.

Part of the \textit{set operations based algorithms}, chase
neighbors through edges, which is the standard
action, should take place in a graph algorithm and rest
of the algorithm rely on
set operations. An example is Bor\r{u}vka's
MST.
Bor\r{u}vka's MST uses disjoint sets of components and relies on
merging those components through set union operation to build
the MST. Another example of a parallel graph algorithm
that uses set operations is the
\textit{Divide \& Conquer Strongly Connected Components} (DCSCC)~\cite{fleischer2000identifying}.
In DCSCC, the vertex set is divided into two sets based on predecessor,
successor reach-ability of a random vertex. Those two sets
intersect to calculate the strongly connected component.

The \textit{nested parallel graph algorithms}
usually have an iterative or data-driven part. However,
enclosing the iterative or data-driven section these algorithms
have another iterative loop. An example for these kind of algorithms
is the \textit{Parallel Betweeness Centrality}~\cite{bader2006parallel} algorithm. Another
example is \textit{All-Pairs Shortest Path} algorithm.

Out of the algorithms discussed above, data-driven
algorithms and iterative algorithms can be formulated as
\textit{stabilizing} algorithms, in which
those algorithms start from a specific initial
vertex state and goes through several state
changes and converges.
When all vertex states converged, the algorithm
terminates.
Further, those algorithms rely on standard graph
operations rather than set operations.
This paper proposes
an abstract model for converging graph algorithms
that only rely on graph operations.

The \textit{Abstract Graph Machine} (AGM) is a
mathematical abstraction for stabilizing graph algorithms.
In AGM each vertex is associated with a \textit{state}.
States are changed by data propagating through edges. We call
data propagating through edges \textit{work}. The work
is executed on a uniform function, i.e. same
function is executed in every process.
We call this function \textit{processing function}.
The processing function takes a unit of work as the parameter
and may generate more work. Before processing,
the work is ordered using
a \textit{strict weak ordering} relation.
The strict weak ordering relation divides work into
\textit{equivalence classes}.

By dividing work into equivalence classes, the AGM
controls the rate at which algorithm converges.
When the amount of work in a single equivalence
class is higher the amount of available data parallelism
is also higher. However, when equivalence class is large
the amount of \textit{unnecessary work} (work that does
not contribute to the final algorithm state) is also higher.
The amount of
work in a single equivalence class is decided by the nature
of the strict weak ordering relation defined.
The strict weak ordering relation also imposes an
induced ordering on the equivalence classes.
The equivalence classes are processed according to
the induced order. Work within a single equivalence
class can be processed in parallel but the processing of
work in
different equivalence classes is ordered.

The proposed abstraction provides a systematic
way to study stabilizing graph algorithms. Using AGM,
we can generalize existing data-driven graph algorithms
and also
derive new algorithms by composing orderings or
by introducing new attributes into the definition
of work. Further, AGM can be used for cost analysis
of distributed memory parallel graph algorithms.

In general, we will assume graph $G=(V,E)$,
where $V$ is the set of vertices and $E$ is the
set of edges. The algorithm states are maintained
in property maps and we assume graph and relevant
property maps are distributed  as a 1D distribution.
After defining necessary prerequisites, we give the
definition of an AGM in\secref{agm}.\secref{ddalgo}, models data-driven
graph algorithms in AGM. We discuss AGM applicability
to non-data-driven algorithms in\secref{agmnondd}.

\AJ{TODO : Our work is focused on unstructured graphs}
\AJ{define what is a data-driven algorithm}
\AJ{discuss about other types of algorithms}
\AJ{what is the main point of the paper ?}
\AJ{data-driven or work driven ?}
\AJ{Work profile for each type of algorithm}
\AJ{Explain what is a data-driven algorithm}

\section{Abstract Graph Machine}
\label{agm}

In this section, we present the \textit{Abstract Graph Machine}.
First, we will define some of the terminologies
that we will be using. Then, we will
layout the structure of the AGM.

The main function that encapsulates the
logic of a stabilizing algorithm is called
the \textit{processing function}. Parameters
to the processing function is a single
unit of work and we call it a \WorkItem. The definition
of the \WorkItem depends on the state/s in which
algorithm is focused on and a \WorkItem
must be indexed with a vertex or
an edge.
The set of all the \WorkItems that algorithm
generates is the set
\WorkItemSet.
When the processing function, processes a \WorkItem,
it may change the states associated
with vertices.
For example, in SSSP, the state is the distance
from the source vertex and
the processing function resembles the logic
inside ``relax''.
For SSSP, a \WorkItem
consists of a vertex and
the distance associated to
the vertex and $\WorkItemSet \subseteq (V \times \mathbb{R}_+^*)$.

An \textit{Abstract Graph Machine}(AGM) consists of a definition of a \textit{\WorkItemSet} set,
an \textit{initial \WorkItem set},
a set of \textit{states},
a \textit{processing function}
and a \textit{strict weak ordering} relation.
In the following subsections, we discuss each of these parameters
in detail.

\subsection{The WorkItem Set}
\label{sec:workitems}

A \WorkItem is a tuple that has a vertex or an edge as of its first
element. If the first element of a \WorkItem is a vertex,
then we call that \WorkItem a \textit{vertex indexed \WorkItem}
and if the first element is an edge we call that \WorkItem
an \textit{edge indexed \WorkItem}.
The additional elements in the \WorkItem, carry state data local to the vertex or an edge.
For example, distance in a SSSP algorithm is an additional element
in the ``SSSP algorithm \WorkItem''. In addition to vertex (or edge)
and state data, a \WorkItem may carry \textit{ordering
attributes}. Ordering attributes are used when
defining the strict weak ordering relation.

A \WorkItem is constructed and consumed within a processing
function.
The processing function, that constructs the \WorkItem
may not reside in the same locality as the processing function, that consumes
the \WorkItem. In other words, \WorkItems can
travel from one locality to another. A \WorkItem
destination locality is decided based on the
data distribution. For a 1D distributed
graph and for a vertex indexed \WorkItem, the destination
locality is decided based on the ownership of
the indexed vertex (i.e. the first element of the \WorkItem).
Details about data distribution is discussed in\secref{sec:datadis}.

All the \WorkItems generated by an algorithm is the set \WorkItemSet.
\WorkItemSet is
formally defined in\defref{def-graph-wi}.

\begin{mydef}\label{def-graph-wi}
  The \textbf{\WorkItemSet} is a set. For a given graph, G = (V, E), the
  $\WorkItemSet \subseteq (V \times P_0 \times P_1 \dots \times P_n)$ where each $P_i$ represents a state value or an ordering attribute value.
  A \WorkItem $\in \WorkItemSet$ is represented as a tuple (e.g., \WorkItem = \textless$v, p_0, p_1 \dots, p_n$\textgreater $\:$ where $v \in V$ and each $p_i \in P_i$).
\end{mydef}

\AJ{TODO : Mention how work item tuple values are accessed. i.e. ``[]'' operator}
To access values in a \WorkItem tuple
AGM uses \textit{bracket operator}. e.g., if $w \in \WorkItemSet$ and
if $w$ = \textless$v, p_0, p_1\dots, p_n$\textgreater
 then $w[0]$ = v and $w[1]$ = $p_0$ and $w[2]$ = $p_1$,
etc.

\subsection{Data Distribution}
\label{sec:datadis}
Data distribution is implicit in AGM
and AGM always assumes that
each vertex (or an edge)
has a single \textit{owner} node (process).
Ownership of a \WorkItem is decided
by the ownership of the indexed
vertex (or edge) of the \WorkItem.
When a \WorkItem is being produced by a
processing function it must be sent to
its appropriate owner node for execution.

In addition, states are also
distributed based on vertex (or edge)
distribution. State value for a
vertex (or edge) is only
maintained at the owner.

\subsection{States}

AGM uses \textit{mappings} to represent states.
Each vertex or edge records
a value algorithm is calculating. Collectively, all the values
recorded against vertices or edges is treated as \textit{the} state
of the algorithm.
States are read and updated by the processing function.
In AGM terminology,
accessing a state value associated with a vertex (or edge) ``v''
is denoted as ``mapping\_name(v)'' (E.g :- distance(v), where distance
is a mapping from vertex to distance from source in SSSP).
\AJ{Unify this across the paper}

In addition to state mappings, processing
functions access read-only graph properties. For example,
``edge weight'' is read as a read only property. In terms of
syntax, AGM does not distinguish between a read-only
property map and a state mapping. However, read-only graph properties
such as ``edge weight'' are part of the graph definition.

States and read-only graph properties are only used
within the processing function.
Further, local updates to states are made \textit{atomically}.

\subsection{Processing Function}

The \textit{processing function} (\PF) takes a \WorkItem as an argument
and may produce more \WorkItems (or 0) based on the logic defined inside
the \PF. Mathematically, \PF is declared as
$\mli{\PFM} : \WorkItemSet \longrightarrow \powerset{\WorkItemSet}$.

The processing function consists of a set of \textit{statements}
(\defref{pf}).
Each statement specifies, how the output \WorkItem (i.e., $w_{new}$)
should be constructed (\textit{<constructor>}), a condition based on
input \WorkItem and/or states (\textit{<condition>}) and an update
to states (\textit{<state\_update>}).
A statement
is invoked  if the condition evaluated
to true. A statement may not generate new \WorkItems but only changes
a state based on a condition. If a statement is only making changes to
states based on input \WorkItems, then it produces $w_{nil}$ \WorkItem as the output.
The \WorkItem $w_{nil}$, is not treated as an active \WorkItem; i.e.,
$w_{nil}$ is not ordered and also $w_{nil}$ is not fed to any of the
processing functions for further processing.

\begin{mydef}\label{pf}
  $\mli{\PFM} : \WorkItemSet \longrightarrow \powerset{\WorkItemSet}$
\begin{equation*}
  \mli{\PFM}(w) =  \begin{cases}
    \{ w_{new} | <constructor>, <state\_update>, \\
    \;\;\; <condition> \}
    \\
    \{ w_{new} | <constructor>, <state\_update>, \\
    \;\;\; <condition> \}
    \\
    \dots
    \\
    \{\} \;\;\;\; \mli{else}
  \end{cases}
\end{equation*}
\end{mydef}

An algorithm starts by invoking processing function
with the \textit{initial \WorkItem set}. Output \WorkItems of
the \PF are ordered according to the strict weak ordering
defined on \WorkItems. Ordered \WorkItems are then again
fed into the processing function. The interaction between
\PF and ordering is graphically depicted in Figure~\ref{fig:agm}.

\begin{figure}
\centering
\includegraphics[width=.55\linewidth]{ordering-relax.pdf}
\caption{Interaction between ordering and the processing function in an AGM}
\vspace{-1ex}
\label{fig:agm}
\end{figure}

\subsection{Ordering}

The AGM orders, output \WorkItems of the processing function
using a \textit{strict weak ordering} relation (denoted by $<_{\wis}$).
The strict weak ordering relation divides \WorkItemSet into
equivalence classes based on the \textit{comparable}
relation ($<_{\wis}$).
The strict weak ordering relation
must satisfy following properties; \AJ{Or constraints ?}
\begin{enumerate}
\item For all $w \in \WorkItemSet$ $w \nless_{\wis} w$.
\item For all $w_1, w_2 \in \WorkItemSet$ if $w_1 <_{\wis} w_2$ then $w_2 \nless_{\wis} w_1$.
\item For all $w_1, w_2, w_3 \in \WorkItemSet$ if $w_1 <_{\wis} w_2$ and $w_2 <_{\wis} w_3$ then $w_1 <_{\wis} w_3$.
\item For all $w_1, w_2, w_3 \in \WorkItemSet$ if $w_1$ not comparable with $w_2$ and $w_2$ not comparable with $w_3$ then $w_1$ is not comparable with $w_3$.
\end{enumerate}

Properties 1 and 2 states that the strict
weak ordering relation is \textbf{not} \textit{reflexive} and
\textit{antisymmetric}. Property 3 denotes the
\textit{transitivity} of the ``comparable \WorkItems''
and Property 4 states that transitivity is preserved among
non-comparable elements in the \WorkItem set.
These properties give rise to an \textit{equivalence}
(i.e. non-comparable \WorkItems belong to the same
equivalence class)
relation defined on \WorkItem set, hence partition
the complete \WorkItem set. Since \WorkItems in
different equivalence classes are comparable, the
strict weak ordering relation defined on \WorkItem
set \textit{induces an ordering} on generated equivalence
classes. In general, there are several ways to define the induced
ordering relation (denoted $<_{\WIS}$), for our work we stick to the definition
given in~\defref{def-graph-aws-relation}.

\begin{mydef}\label{def-graph-aws-relation}
  $<_{\WIS}$ is a binary relation defined on $\powerset{\WorkItemSet}$, such that if $W_1, W_2 \in
  \powerset{\WorkItemSet}$ then; $W_1 \le_{\WIS} W_2
  \; iff \\
  \; forall \; w_1 \in W_1 \; and \; forall \; w_2 \in W_2 ; w_1 <_{\wis} w_2$.
\end{mydef}

\begin{figure
\centering
\includegraphics[width=.45\linewidth]{workitem_partition.pdf}
\caption{Partitioning \WorkItems based on strict weak order relation $<_{\wis}$.}
\vspace{-1ex}
\label{fig:wipartition}
\end{figure}

Figure~\ref{fig:wipartition}, shows how \WorkItemSet is
partitioned by the strict weak ordering
relation $<_{\wis}$. Sets A, B, C, D, E are mutually exclusive
and $A \cup B \cup C \cup D \cup E = \WorkItemSet$.
Elements (\WorkItems) in A are not comparable using $<_{\wis}$, i.e. if
$w_1, w_2 \in A$ then $w_1 \nless_{\wis} w_2$ nor $w_2 \nless_{\wis} w_1$.
Same applies to other sets.
Also, induced relation order partitions in a
sequence. E.g., $B <_{\WIS} D <_{\WIS} A <_{\WIS} E <_{\WIS} C$;
as per this example the smallest partition defined by $<_{\WIS}$ is B.

\subsection{The AGM}
The AGM is formally defined in~\defref{def-graph-agm}.
\begin{mydef}\label{def-graph-agm}
  An \textbf{Abstract Graph Machine}(AGM) is a 6-tuple (G, \WorkItemSet, Q, \PF, $<_{\wis}$, S), where
  \begin{enumerate}
  \itemsep0em
  \item G = (V, E) is the \textbf{input graph},
  \item $\textbf{\WorkItemSet} \subseteq (V \times P_0 \times P_1 \dots \times P_n)$ where each $P_i$ represents a state value or an ordering attribute,
  \item Q - Set of states represented as property maps,
  \item $\PFM : \WorkItemSet \longrightarrow \powerset{\WorkItemSet}$ is the \textbf{processing function},
  \item $<_{\wis}$ - \textbf{Strict weak ordering relation} defined on \WorkItems,
  \item S ($\subseteq \WorkItemSet$) - \textbf{Initial \WorkItem set}.
  \end{enumerate}
\end{mydef}

AGM execution starts with the \textit{initial \WorkItem set}.
The initial \WorkItem set is ordered according to the strict weak
ordering relation. Then \WorkItems within the smallest equivalence class
is fed to the \PF.
If \PF generates new \WorkItems,
they are again, separated into equivalence classes.
The \WorkItems within a single equivalence class can execute \PF
in parallel. However, \WorkItems in two different equivalence
classes must be ordered according to the induced relation (i.e. $<_{\WIS}$).
When executing \WorkItems in an equivalence class, it may generate
new \WorkItems to the same equivalence class or to an equivalence
class greater (as per $<_{\WIS}$)
than currently processing equivalence class.
The AGM executes \WorkItems in next equivalence class,
once it finished executing all the workitems in the
current equivalence class. An AGM terminates when it
executes all the \WorkItems in all the equivalence classes.

\section{Data-driven Algorithms in AGM}
\label{ddalgo}
A \textit{Data-driven algorithm} starts from a subset of \WorkItem set,
and generates more work as it progress. Towards to the end, the algorithm
generates less work and comes to a termination when it does not
generate more work. Most of the SSSP algorithms including Dijkstra's Algorithm,
$\Delta$-Stepping algorithm~\cite{meyer2003delta}, KLA~\cite{harshvardhan_kla:_2014} SSSP algorithm
are data-driven algorithms. Also, the \textit{Level Synchronous
Breadth First Search}~\cite{bulucc2011parallel}, \textit{KLA Breadth First Search}~\cite{harshvardhan_kla:_2014}
and \textit{Push based Page Rank} discussed in ~\cite{whang2015scalable}
are also data-driven algorithms.
In this section, we go through
those data-driven algorithms and show the AGM formulation
for each.
Further, we present
a data-driven Connected Components algorithm
and an AGM formulation for that.

\subsection{Single Source Shortest Path Algorithms}
In this section, we go through several algorithms for SSSP
application and show how they can be modeled
using the Abstract Graph Machine defined in
Definition~\ref{def-graph-agm}.

In general, the \WorkItem set for SSSP application can be defined as
$\WorkItemSet^{sssp}  \subseteq (V \times Distance)$,
where \textit{Distance} $\subseteq \mathbb{R}_+^*$. SSSP algorithms
use \textit{distance} as the output state and \textit{weight} map as a
read-only input mapping.
The processing function for SSSP changes the distance state
if input \WorkItem's distance is less than what is already stored in the
distance map. Further, adjacent vertices of a given vertex are
accessed through the \textit{neighbors} function.
(Declared as $neighbors: V \longrightarrow \powerset{V}$).

Interestingly, most of the SSSP algorithms share almost the same processing function.
In general, the SSSP processing function ($\PFM^{sssp}$) can be defined as follows;

\begin{mydef}\label{sssp-pf}
  $\PFM^{sssp} : \WorkItemSet^{sssp} \; \longrightarrow \WorkItemSet^{sssp}$
\begin{equation*}
  \PFM^{sssp}(w) =  \begin{cases}
    \{ w_k | < w_k[0] \in \mli{neighbors}(w[0]) \; \mli{and}
    \\ \;\;\; w_k[1] \longleftarrow w[1] + \mli{weight}(w[0], w_k[0]) >
    \\ \;\;\;< distance(w[0]) \longleftarrow w[1] >
    \\ \;\;\;< \mli{if} \; w[1] < \mli{distance}(w[0]) > \}
    \\
    \{\} \;\;\;\; \mli{else}
  \end{cases}
\end{equation*}
\end{mydef}

The processing function definition given in\defref{sssp-pf}
is organized according to the general processing function
definition given in~\ref{pf}. The processing function, \PF
has two statements. The first statement is executed
only if \WorkItem distance is less than the value stored
in the $distance$ state for the relevant vertex in \WorkItem.
Constructor of the first statement
specifies how to construct a new \WorkItem.
In\defref{sssp-pf}, $w$ refers to currently processing
\WorkItem and $w_k$ is the new \WorkItem that will be
constructed. Further, the bracket operator is used
to access \WorkItem elements (As discussed in\secref{sec:workitems}).
For $w \in \WorkItemSet^{sssp}$, the term $w[0]$
refers to a vertex and $w[1]$ refers to
the distance associated with the vertex referred by $w[0]$.

\subsubsection{Dijkstra's Algorithm}

Dijkstra's SSSP algorithm is the work efficient SSSP algorithm.
Algorithm globally orders vertices by their associated
distances and shortest distance vertices are processed first.
In the following we define the ordering relation for Dijkstra's algorithm and,
we instantiate Dijkstra's algorithm using an AGM.

\begin{mydef}\label{dj-swo}
  $<_{\mli{dj}}$ is a binary relation defined on $\WorkItemSet^{sssp}$ as follows;
  Let $w_1, w_2 \in \WorkItemSet^{sssp}$, then;
  $w_1 <_{\mli{dj}} w_2$ iff $w_1[1] < w_2[1]$
\end{mydef}

It can be proved that $<_{dj}$ is a strict weak ordering relation that
satisfies constraints listed under Definition~\ref{dj-swo} (proof is omitted).
AGM instantiation for Dijkstra's algorithm is given in~\propref{dijkstra-agm}.

\begin{myproposition}\label{dijkstra-agm}
  Dijkstra's Algorithm is an instance of an AGM where;
 \begin{enumerate}
 \itemsep0em
 \item $G = (V, E, weight)$ is the input graph,
 \item \WorkItemSet = $\WorkItemSet^{sssp}$,
 \item Q = \{distance\} is the state mapping,
 \item \PF = $\PFM^{sssp}$,
 \item Strict weak ordering relation $<_{\wis}$ = $<_{\mli{dj}}$,
 \item S = \{\textless$v_s$, 0\textgreater\} where $v_s \in V$ and $v_s$ is the source vertex.
 \end{enumerate}
\end{myproposition}

\subsubsection{$\Delta$-Stepping Algorithm}

$\Delta$-Stepping~\cite{meyer2003delta} arrange vertex-distance pairs
into distance ranges (\textit{buckets}) of size $\Delta (\in \mathbb{N})$
and executes buckets in order.  Within a bucket, vertex-distance pairs
are not ordered,
and can be executed in any order.
Processing a bucket may produce extra work for
the same bucket or for a successive bucket.
The strict weak ordering relation for the $\Delta$-Stepping algorithm
is given in Definition~\ref{delta-swo}.

\begin{mydef}\label{delta-swo}
  $<_\Delta$ is a binary relation defined on $\WorkItemSet^{sssp}$ as follows;
  Let $w_1, w_2 \in \WorkItemSet^{sssp}$, then; \newline
  $w_1 <_{\Delta} w_2$ iff $\lfloor w_1[1]/\Delta \rfloor < \lfloor  w_2[1]/\Delta \rfloor$
\end{mydef}

Instantiation of the $\Delta$-Stepping algorithm in AGM (given in Proposition~\ref{delta-agm})
is same as in Proposition~\ref{dijkstra-agm},
except the strict weak ordering relation is $<_{\Delta}$ (= $<_{\wis}$).

\AJ{If we need more space we can remove redundant text}
\begin{myproposition}\label{delta-agm}
  $\Delta$-Stepping Algorithm is an instance of AGM where;
 \begin{enumerate}
  \itemsep0em
  \item G = (V, E, weight) is the input graph
  \item \WorkItemSet = $\WorkItemSet^{sssp}$
  \item Q = \{distance\} is the state mapping,
  \item \PF = $\PFM^{sssp}$,
  \item Strict weak ordering relation $<_{\wis}$ = $<_{\Delta}$
  \item S = \{\textless$v_s$, 0\textgreater\} where $v_s \in V$ and $v_s$ is the source vertex.
 \end{enumerate}
\end{myproposition}

\subsection{Breadth First Search (BFS) Algorithms}

In this subsection, we present AGM models for
two distributed memory parallel BFS algorithms.
They are, level synchronous BFS and KLA BFS.

\subsubsection{Level Synchronous BFS Algorithm}

The level-synchronous breadth first search algorithm
uses data structures to store the \textit{current} and \textit{next}
vertex frontiers.
Then the next container data is swapped with current
after processing each level.

In the following we model level-synchronous BFS with the AGM.
The level synchronous BFS order work by the level in the resulting
BFS tree.
Therefore, the ordering attribute, that we are interested in, is the \textit{level};
hence we define $\WorkItemSet^{bfs} \subseteq V \times Level$
where $Level \subseteq \mathbb{N}$.

The processing function for BFS is defined in Definition~\ref{bfs-pf}.
The state of the BFS algorithm is maintained in a map
($vertex\_level : V \longrightarrow Level$)
that store the level associated with each vertex. An infinite value
(very large value) is associated to each vertex at the start of
the algorithm. Then the infinite value is changed as the algorithm
traverse through graph level by level.

\begin{mydef}\label{bfs-pf}
  $\PFM^{bfs} : \WorkItemSet^{bfs} \longrightarrow \powerset{\WorkItemSet^{bfs}}$
\begin{equation*}
  \PFM^{bfs}(w) =  \begin{cases}
    \{ w_k | < w_k[0] \in neighbors(w[0]) \; and
    \\ \;\;\; w_k[1] \longleftarrow w[1] + 1 >
    \\ \;\;\; < vertex\_level(w_k[0]) \longleftarrow w[1] >
    \\ \;\;\;\;\;< (if \; vertex\_level(w_k[0]) < \infty) > \}
    \\ \{\} \;\;\;\; else
  \end{cases}
\end{equation*}
\end{mydef}

The AGM is instantiated for level-synchronous BFS algorithm
is given in\propref{bfs-agm}.

\begin{myproposition}\label{bfs-agm}
  Level Synchronous BFS Algorithm is an instance of an AGM where;
 \begin{enumerate}
  \itemsep0em
  \item G = (V, E) is the input graph,
  \item \WorkItemSet = $\WorkItemSet^{bfs}$,
  \item Q = \{ vertex\_level \} is the state mapping,
  \item \PF = $\PFM^{bfs}$,
  \item The strict weak ordering relation $<_{\wis}$ = $<_{bfs}$,
  \item S = \{\textless$v_s$, 0\textgreater\} where $v_s \in V$ and $v_s$ is the source vertex.
 \end{enumerate}
\end{myproposition}

\subsubsection{KLA BFS Algorithm}
The KLA BFS is similar to the level-synchronous BFS discussed above.
Unlike in level-synchronous BFS,
the KLA BFS processes \WorkItems asynchronously up to $k$ levels.
In other words, \WorkItems are partitioned based on the value of $k$.
The strict weak ordering relation for KLA is defined in~\defref{kla-rel}.

\begin{mydef}\label{kla-rel}
  $<_{kla}$ is a binary relation defined on $\WorkItemSet^{bfs}$ as follows:
  Let $w_1, w_2 \in \WorkItemSet^{bfs}$, then;
  $w_1 <_{kla} w_2$ iff $\lfloor w_1[1]/k \rfloor < \lfloor w_2[1]/k \rfloor$
\end{mydef}

The AGM instantiation for KLA BFS is same as
level synchronous BFS instantiation
(Proposition~\ref{bfs-agm}), except the ordering relation is replaced with $<_{kla}$.

\subsection{PageRank}
\textit{PageRank}(PR)~\cite{page1999pagerank} is a
graph algorithm extensively used in web mining.
Given a graph $G=(V,E)$, the PageRank, $PR(v)$ of a
vertex $v$ is calculated using the formula given in Equation 1.
The variable $\alpha$ represents the teleportation parameter.
Function \textit{source} returns the source vertex given an edge and
functions \textit{in\_edges} and \textit{out\_edges} respectively return in and out
edges of a given vertex.

\begin{equation}
\label{pr-formula}
PR(v) = (1-\alpha) + \alpha\sum_{e \in in\_edges(v)}\frac{PR(source(e))}{|out\_edges(source(e))|}
\end{equation}

In PageRank, web pages are modeled as vertices and links between
web pages are edges. The PageRank algorithm calculates a numeric
weight for each page, which describes the importance of a web page.

Often PageRank algorithm is implemented as an
\textit{iterative algorithm}; i.e. algorithm iterate through
all the vertices and calculates PageRank using the formula
given in Equation 1.
The algorithm continues to calculate rank values
until the different between newly calculated value and
the previous value is less than, a given error vale - $\epsilon$.

In the data-driven form of the algorithm, the PageRank
of a vertex depends on the neighbours connected to the vertex
using an in-edge. Whenever PageRank value of a neighbour connected
through an in-edge changes, the PageRank of the current
vertex must be re-calculated. A PageRank algorithm that
uses this argument is also explained in~\cite{whang2015scalable}.
The AGM formulation of the PageRank algorithm uses dependency between
vertices (through in-edges) in terms of PageRank calculation to generate
work.

In PageRank the final state we are interested in
is the rank values of  vertices.
A straightforward way to model work for PageRank is to
use vertex and rank value.
One way to reduce the amount
work is to
order \WorkItems
by the \textit{residual} of a PageRank calculated
for a vertex. (Residual based ordering is discussed in~\cite{whang2015scalable}). \AJ{TODO : Verify !}.
Residual is the portion of the PageRank value that is being
pushed through an out edge of a vertex.
\AJ{Validate with Marcin}

Based on the residue value,
the \WorkItem set for PageRank can be defined
as $\WorkItemSet^{pr} \subseteq (V \times \mathbb{R})$,
where $\mathbb{R}$ is used to represent
the residual value.
The processing
function for PageRank takes a \WorkItem ($\in \WorkItemSet^{pr}$)
and produces more \WorkItems if the difference
between newly calculated PageRank value and previous
PageRank value is greater than $\epsilon$. Further, the algorithm
uses $rank$ mapping to store the calculated PageRank values.
The processing function for PageRank is defined in\defref{pf-pr}.

\begin{mydef}\label{pf-pr}
  $\mli{\PFM^{pr}} : \WorkItemSet^{pr} \longrightarrow \powerset{\WorkItemSet^{pr}}$
\begin{equation*}
  \mli{\PFM^{pr}}(w) =  \begin{cases}
    \{ w_n | < w_n[0] \in out\_neighbours(w[0]) \; \& \\
    \;\;\; w_n[1] \leftarrow \delta > \\
    < pr_{new} \leftarrow PR(w[0]) \; ; \; \delta \leftarrow (pr_{new} - rank(w[0])) \\
    \;\;\; ; rank(w[0]) \leftarrow pr_{new} > \\
    < (\mli{if} \; \delta > \epsilon ) > \}
    \\
    \{\} \;\;\;\; \mli{else}
  \end{cases}
\end{equation*}
\end{mydef}

The PageRank algorithm converges quickly if we process
higher residue \WorkItems first. Therefore, there are
several possibilities to define ordering for PageRank:
1. do a strict comparison on residue value,
2. define strict weak ordering as in $\Delta$-Stepping
3. do not perform ordering at all. Each of the orderings creates a
different size of equivalence class on PageRank
\WorkItems.
However, for the formulation presented above, we
define strict weak ordering (\defref{s-w-o-pr}) only based on the comparison of
residue
values.
Other orderings are also possible.

\begin{mydef}\label{s-w-o-pr}
  $<_{pr}$ is a binary relation defined on $\WorkItemSet^{pr}$ as follows;
  Let $w_1, w_2 \in \WorkItemSet^{pr}$, then; \newline
  $w_1 <_{pr} w_2$ iff $w_1[1] >  w_2[1] $.
\end{mydef}

The PageRank algorithm starts by assigning an initial
rank to every vertex. Therefore the initial \WorkItemSet
has a \WorkItem per each vertex and a associated
residue value initialized to 0. More formally
the initial \WorkItemSet $IW^{pr} = \{w | w[0] \in V \; and \; w[1] \leftarrow 0\}$.

With necessary parameters in hand we define the AGM
formulation for PageRank algorithm in\propref{pr-agm}.

\begin{myproposition}\label{pr-agm}
  PageRank Algorithm is an instance of an AGM where;
 \begin{enumerate}
 \itemsep0em
 \item $G = (V, E)$ is the input graph,
 \item \WorkItemSet = $\WorkItemSet^{pr}$,
 \item Q = \{rank\} is the state mapping,
 \item \PF = $\PFM^{pr}$,
 \item Strict weak ordering relation $<_{\wis}$ = $<_{\mli{pr}}$,
 \item S = $IW^{pr}$
 \end{enumerate}
\end{myproposition}

\AJ{State update should come before condition - change everywhere}
\subsection{Connected Components Algorithm}
For a given undirected graph, $G = (V, E)$, the \textit{connected component} (CC)
is a \textit{subgraph}
in which, any two vertices are connected through a \textit{path}. A connected component
can also be defined as a \textit{reachable} relation. A vertex $v \; (\in V)$
is reachable to vertex $u \; (\in V)$ if and only
if there is a path from $v$ to $u$.

In the literature, we find two main types of parallel connected component algorithms:
1. \textit{Shiloach-Vishkin's $O(log n)$ based algorithms}~\cite{shiloach1982logn},
2. \textit{Search based algorithms}~\cite{hirschberg1979computing}.
Algorithms derived from Shiloach-Vishkin's connected components
are not data-driven algorithms. They are
\textit{iterative algorithms} and will be discussed in
Section~\ref{secite}.
In the following we discuss a search based connected component
algorithm.

Search based algorithms mainly
use \textit{Depth-first search} (DFS), \textit{Breadth-first search} (BFS)
or a \textit{Chaotic search} algorithm (See~\cite{hirschberg1979computing}).
DFS based algorithms give little support to explore
the available parallelism.
Both BFS based algorithms and Chaotic
search based algorithms have more opportunity
to explore parallelism. To present the AGM formulation
we will use a Chaotic search based algorithm.

A parallel search (Chaotic) based algorithm is given in Listing~\ref{search-cc}.
Algorithm uses
a property map (\textit{component}) to record the component id of each vertex.
Component map is the output state of the algorithm.
Initially, the value of component id of a vertex is assigned
to a very large number, then component map is
updated when the function ``CC'' is invoked. The ``VertexComponent''
structure contains the vertex id and the component id for the vertex.

\begin{algorithm}
\algsetup{linenosize=\scriptsize}
\caption{Search Based CC Algorithm}
\label{search-cc}
\textbf{Input:} Graph $G=(V, E)$
\begin{algorithmic}[1]
  \STATE Initialize() \{
  \FOR{each vertex $v$ in $V$}
  \STATE $component(v) \longleftarrow \infty$
  \ENDFOR
  \STATE \}
  \STATE
  \STATE CC(vc : VertexComponent) \{
  \STATE $old\_component \longleftarrow component(vc.vertex)$
  \IF {$vc.component < old\_component$}
  \STATE $component(v) \longleftarrow vc.component$
  \FOR {each $v$ in adjacencies(vc.vertex)}
  \STATE CC(VertexComponent(v, vc.component))
  \ENDFOR
  \ENDIF
  \STATE \}
  \STATE
  \STATE Invoke() \{
  \STATE Initialize()
  \FOR{each vertex $v$ in $V$}
  \STATE CC(VertexComponent(v, v))
  \ENDFOR
  \STATE \}
\end{algorithmic}
\end{algorithm}

We can develop several versions of the above algorithm. The algorithm in Listing~\ref{search-cc}
is a chaotic search algorithm. We also can develop the Dijkstra's version
and $\Delta$-Stepping version of the algorithm.
In the following we model above algorithm using an AGM.

The \WorkItems for search based CC should include the distance
and the \textit{component id} (Since component id represents the state).
Therefore, we define $\WorkItemSet^{cc} \subseteq (V \times Component)$.
In the definition the $Component \subseteq \mathbb{N}$.
The processing function for search based CC is similar to SSSP processing
function except it updates component id instead of the distance.
Processing function for CC is given in Definition~\ref{sb-cc-pf}.

\begin{mydef}\label{sb-cc-pf}
  $\PFM^{cc} : \WorkItemSet^{cc} \longrightarrow \powerset{\WorkItemSet^{cc}}$
\begin{equation*}
 \PFM^{cc}(w) =  \begin{cases}
    \{ w_k | < w_k[0] \in \mli{neighbors}(w[0]) \\
    \;\;\;\; and \; w_k[1] \longleftarrow  w[1] > \\
    \;\;\; < component(w[0]) \longleftarrow w[1] > \\
    \;\;\; < \mli{if} \; (w[1] < component(w[0]) > \}
    \\
    \\
    \{\} \;\;\;\; \mli{else}
  \end{cases}
\end{equation*}
\end{mydef}

We order \WorkItems by component id so that the smallest component ids
are processed  first. The order \WorkItems processed
does not affect the correctness of the Algorithm~\ref{search-cc}.
Therefore, more relaxed ordering can also be applied
to CC AGM formulation. For simplicity we use
the ordering based on component id. The strict weak ordering
relation for CC is defined in Definition~\ref{sb-cc}.

\begin{mydef}\label{sb-cc}
  $<_{cc}$ is a binary relation defined on $\WorkItemSet^{cc}$ as follows;
  Let $w_1, w_2 \in \WorkItemSet^{cc}$, then; \newline
  $w_1 <_{cc} w_2$ iff $w_1[1] < w_2[1]$.
\end{mydef}

In Proposition~\ref{sb-cc-agm} we define the AGM for search based connected
components.
\begin{myproposition}\label{sb-cc-agm}
  CC Algorithm is an instance of an AGM where;
 \begin{enumerate}
  \itemsep0em
  \item $G = (V, E)$ is the input graph
  \item \WorkItemSet = $\WorkItemSet^{cc}$
  \item Q = \{components\} is the state mapping,
  \item \PF = $\PFM^{cc}$
  \item Strict weak ordering relation $<_{\wis}$ = $<_{cc}$
  \item S = $\{w | w[0] \in V \; and \; w[1] = w[0]\}$.
 \end{enumerate}
\end{myproposition}

\section{AGM for Non-Data-driven \\ Algorithms}
\label{agmnondd}
So far we modeled data-driven algorithms in
AGM.
A natural question to ask is whether AGM
approach can be used to model other kinds
of graph algorithms. The answer depends on the type
of the graph algorithm we are focused on.
For some types of graph algorithms AGM
approach can be used with few modifications.
Some other graph algorithms cannot be modeled using
AGM due to the in-adequateness to express orderings
using strict weak orderings and use set operations
in those algorithms. In this section,
we analyze the applicability of AGM to several
non data driven
algorithm types.

\subsubsection{Iterative Algorithms}
\label{secite}

An \textit{iterative algorithm} travels through
all the vertices (or edges) until algorithm
meets a specific state condition. Example
algorithms are \textit{Iterative PageRank}~\cite{gleich2004fast}
and \textit{Shiloach-Vishkin Connected Components}~\cite{shiloach1982logn}.
We use iterative PageRank as an example to dicuss
the applicability of AGM to iterative algorithms,
but discussion is general in which it applies
to other iterative algorithms also.

\textit{Iterative PageRank} iterate through
all the vertices until all vertices reach
a saturated PageRank value. PageRank value of
a vertex is saturated if the difference between
newly calculated PageRank value and the previous
PageRank value is less than a defined error
value. In the parallel iterative PageRank vertices
in a single iteration are processed parallely and
after each iteration algorithm checks whether
the PageRank values has reached a saturation.

Vertices processed in parallel within
a single iteration
goes into a single equivalence class in the
AGM formulation of the iterative PageRank. But
vertices belonging to different iterations should be placed
in different equivalence classes. Yet, after
processing each equivalence class AGM must check
whether PageRank has reached its saturation
state.
\AJ{Maybe a figure}

The current, AGM formulation does not have
fascility to check a condition before processing
next equivalence class. The AGM can be
augmented to check a condition
after processing each equivalence class.
Since equivalence classes are defined
based on the iteration, a \WorkItem
of an iterative algorithm must have
the \textit{iteration number}
as a member and strict weak ordering
must be defined in such a way, \WorkItems
that has same iteration numbers are
not comparable.

\subsubsection{Divide \& Conquer Algorithms}

A \textit{Divide \& Conquer} algorithm recursively
breaks down a problem into two or more
sub problems, until they become sufficiently
simple to solve. In a parallel Divide \& Conquer
algorithm divisions are conquered parallely.
An example is \textit{Divide \& Conquer Strongly Connected Components}
(DCSCC)~\cite{fleischer2000identifying}.
The question is whether we can use AGM
to express Divide \& Conquer algorithms.

The answer is \textit{no}, we cannot use AGM
to express parallel \textit{Divide \& Conquer}
algorithms. The main reason is that the strict
weak ordering cannot be used to express
the ordering in a Divide \& Conquer algorithm
in such a way it produces full available
data parallelism.
\AJ{review}
Ordering in divide \& conqer algorithms
is organized based on subset relationships
of divisions. Therefore, the strict weak
ordering is too strong to represent
such ordering. In Appendix~\ref{appscc} we use DCSCC
 algorithm as an example to show
that divide \& conqer algorithm ordering
cannot be expressed using a strict
weak ordering. Rather, \WorkItems in DCSCC algorithm is
ordered using a \textit{partial order} (based on the subset relationship of
divisions).

\subsubsection{Algorithms with Nested Parallelism}

Some algorithms show multiple levels
of parallelism. Usually these algorithms
have a visible data parallelism then a second
level of \textit{task parallelism} or
\textit{data parallelism}.
Such nested parallel constructs are
not easily transferrable to processing
function so that it is amenable to
execute in a distributed environment.
We see these types of algorithms in
applications such as \textit{Minimum Spanning Tree} (MST)
and \textit{Betweeness Centrality}.
In the following we use MST as an example
and briefly analyze
nested parallel algorithms in related
to AGM.

A \textit{spanning tree}, T of a graph G is a subgraph
that includes all the vertices of G and is a tree.
A minimum spanning tree (MST) of an undirected,
connected, weighted graph G is a
spanning tree that connects all the
vertices with minimum weighted edges.
There are
3 widely used algorithms to solve MST problem. They
are 1. Prim's Algorithm~\cite{Cormen:2001}, 2. Kruskal Algorithm~\cite{Cormen:2001}
and 3. Bor\r{u}vka's Algorithm~\cite{nevsetvril2001otakar}.

Both Prim's algorithm
and Kruskal algorithm does not provide much data parallelism.
However, Bor\r{u}vka's algorithm provides more
parallelism and most of the existing
parallel (and also distributed)
implementations are based on Bor\r{u}vka's
algorithm (See ~\cite{gallager1983distributed}.~\cite{garay1998sublinear}).
Bor\r{u}vka's algorithm starts with a forest
(i.e. each vertex is a component initially)
and finds the minimum
weight edge betwee two components.
If algorithm finds a such edge,
components are connected using the found edge.

To find the representative component set
Bor\r{u}vka's algorithm uses
\textit{disjoint union} data structure.
In a distributed setting calculating the
representative set for a given source vertex
and for a given target vertex of an edge can
be performed in parallel.
Therefore in addition to parallel
processing of components algorithm
also can process calculation of
representative components for source
vertex and target vertex in parallel.
\AJ{TODO: Need a figure}

The current AGM formulation does not have
fascility to model nested levels of parallel work;
i.e. work for parallel component processing
and work for parallely calculate representative
vertex sets for source and target of an
edge. Another algorithm that shows the same behaviour
is \textit{Parallel Betweeness Centrality}~\cite{bader2006parallel}
algorithm. Both algorithms generate parallel work
in a \textit{fork-join} like structure.

\AJ{In future work mention that we expect to extend current AGM
to express nested levels of work}

\section{Conclusion}

In this paper we presented Abstract Graph Machine (AGM),
a mathematical model for distributed memory parallel
graph algorithms that converges. The model formulate
edge traversals as work and express an algorithm
using a common function executed by every process in the system
and an ordering that divides work into equivalence classes.
We showed that existing data driven algorithms can be
modeled using the AGM and also iterative algorithms. Algorithms
that converge using set operations cannot be modeled in the AGM.
We believe algorithms can be derived in such a way they can
be modeled in the AGM.

Modeling algorithms using AGM generalizes existing algorithms,
also
model allows us to derive new variations of algorithms
by changing the way algorithm order work. Ordering
of an algorithm can be changed by either changing the average
size of an equivalence class generated by the ordering or by
introducing new ordering attributes.
Further, in future we plan to
use AGM model to build cost models for distributed memory
parallel
graph algorithms.

\section{Acknowledgments}
Authors (Thejaka) would like to thank
Prabath Silva, for his valuable input
on orderings in divided and conquer algorithms.
I (Thejaka) thank Martina Barnas for many discussions
about AGM algorithm abstractions and for her valuable feedback on
this paper.
Further,
this material is based upon work
supported by the National Science Foundation under Grant No. 1319520
and National Science Foundation under Grant No. 1111888.

\bibliographystyle{abbrv}

redpajama_set_name: RedPajamaArXiv


text:
Chris Cheek
Chris Cheek was born in St. Louis, Missouri. He began playing the alto-sax when he was 12. Chris was fortunate to have a solid public school music program as well as a supportive family. He had both good educational and performing experiences right from the beginning. Chris was a member of several local Jazz and Blues groups, including the Bob Kuban brass and Willie Akins, who were both saxophonists. Chris moved to Boston to study at Berklee College, where he was a student of Joe Viola, Herb Pomeroy and Hal Crook. Chris moved to New York in 1992. He has since recorded and toured with Charlie Haden's Liberation Music Orchestra and The Bloomdaddies. Chris has played with Bill Frisell and Lee Konitz, Bill Frisell, Bill Frisell, Carla Bley and Tom Harrell. He also recorded with Frank Carlberg, Eliot Zigmund. Kurt Rosenwinkel, El Muchacho, Kurt Mehldau, Kurt Rosenwinkel, Kurt Rosenwinkel, Kurt Rosenwinkel, Kurt Rosenwinkel, Kurt Rosenwinkel, and Brad Mehldau. Cheek is also a member of the Brooklyn Boogaloo Blowout's Rudder, Steve Swallow's Quintet and Guillermo Klein's "Los Guachos", as well as the newly formed Axis Saxophone Quartet with Josh Redman and Chris Potter. Chris has also recorded four albums as the leader of Fresh Sound Records. He currently lives in Brooklyn, NY. from www.chrischeek.net

redpajama_set_name: RedPajamaCommonCrawl


MSC Cruises has announced that MSC Lirica will home-port at Shanghai, China, in May 2016 following a 60-day round-the-world Grand Voyage.
The 65,000 gross ton ship will make the company's maiden call at China's largest city near the end of its Grand Voyage which will depart on 3 March 2016 from Rio de Janeiro, Brazil.
Guests will be able to board the Grand Voyage at Rio de Janeiro, Brazil; Genoa, Italy; or Dubai, United Arab Emirates. Prices for the full 60-day voyage start from £2,799 per person on the Bella experience on a cruise-only basis, based on two people sharing an inside cabin.
CAISSA Touristic Group, China's leading outbound tourism service provider, and MSC Cruises have entered into a strategic partnership to enable MSC Lirica to home-port in Shanghai as of May 2016 to serve the Chinese home market.
The cruise line plans to tailor MSC Lirica's products and services to serve the needs of Chinese consumers and will announce several industry firsts at a press conference in Beijing in the coming weeks.
The voyage will start in Brazil and visits Spain, France, Italy, Greece, Egypt, Jordan, Oman, United Arab Emirates, India, Sri Lanka, Thailand, Malaysia, Singapore, Vietnam, Hong Kong, China, and Japan.
4 Sat 5 Mar At Sea …. ….
7 Tue 8 Mar At Sea …. ….
9 Thu 10 Mar At Sea …. ….
10 Fri 11 Mar At Sea …. ….
11 Sat 12 Mar At Sea …. ….
12 Sun 13 Mar At Sea …. ….
13 Mon 14 Mar At Sea …. ….
15 Wed 16 Mar At Sea …. ….
17 Fri 18 Mar At Sea …. ….
22 Wed 23 Mar At Sea …. ….
27 Mon 28 Mar At Sea …. ….
28 Tue 29 Mar At Sea …. ….
29 Wed 30 Mar At Sea …. ….
30 Thu 31 Mar At Sea …. ….
31 Fri 1 Apr At Sea …. ….
34 Mon 4 Apr Dubai 08:00 ….
36 Wed 6 Apr At Sea …. ….
37 Thu 7 Apr At Sea …. ….
38 Fri 8 Apr At Sea …. ….
41 Mon 11 Apr At Sea …. ….
43 Wed 13 Apr At Sea …. ….
44 Thu 14 Apr At Sea …. ….
48 Mon 18 Apr Singapore 08:00 ….
50 Wed 20 Apr At Sea …. ….
52 Fri 22 Apr At Sea …. ….
53 Sat 23 Apr At Sea …. ….
55 Mon 25 Apr At Sea …. ….
56 Tue 26 Apr Shanghai 19:00 ….
58 Thu 28 Apr At Sea …. ….
60 Sat 30 Apr At Sea …. ….
61 Sun 1 May Shanghai 05:00 ….


text:
Q: find first completely empty row on a sheet need a function that returns the first completely empty row (no values, no formulas, no blanks) from a sheet with sparely populated cells.  No one single column is required to be filled.
I tried this, but i can even get it to compile:
Public Donations As Worksheet
Set Donations = Sheets("Sheet2")

Function getEmptyRow() As Long
   Dim lastCol As Long, lastRow As Long, maxRow As Long
   Dim col As Long
   Dim r As Variant

   lastCol = Donations.Cells(1, Columns.Count).End(xlToLeft).Column
   For col = 1 To lastCol Step 1
      lastRow = Donations.Cells(Rows.Count, col).End(xlUp).row
      maxRow = Application.WorksheetFunction.max(maxRow, lastRow)
   Next col
   getEmptyRow = maxRow + 1
End Function

A: Using EntireRow (which is so useful let me tell you) and counting row by row starting in A1 is one very basic way of doing this.
This will tell you in the immediate window:
Sub findemptyrow()                       '''Psuedo Code
Application.ScreenUpdating = False       'turns off annoying blinky
Range("a1").Activate                     'start at beginning
While a <> 1                             'keep going
  If Application.CountA(ActiveCell.EntireRow) = 0 Then  'is it blank?
  Debug.Print "Row " & (ActiveCell.Row) & " is blank."   'it is
  a = 1                                   'stop going
  End If
  ActiveCell.Offset(1).Activate           'next cell
Wend                                      'do it all over again
Application.ScreenUpdating = True         'back to normal settings
End Sub

Making ScreenUpdating False will make this faster, even with 10k's of rows.

A: The Range.Find method is likely the most expedient method. Look for a wildcard (What:=Chr(42)), start in A1 (After:=.Cells(1, 1), search backwards  (SearchDirection:=xlPrevious), search row-by-row (SearchOrder:=xlByRows).Row), look at the formulas (LookIn:=xlFormulas) since that will find the first value or formula; looking at xlValues may not be correct if a formula is returning an empty string ("").
Option Explicit
Public Donations As Worksheet

Sub test()
    Set Donations = Worksheets("Sheet2")
    Debug.Print getNextEmptyRow(Donations)
End Sub

Function getNextEmptyRow(ws As Worksheet)
    With ws.Cells
        getNextEmptyRow = .Find(What:=Chr(42), After:=.Cells(1, 1), LookIn:=xlFormulas, _
                                SearchDirection:=xlPrevious, SearchOrder:=xlByRows).Row + 1
    End With
End Function

You cannot set Donations in the declarations area of a module code sheet. Declare the public variable in the declarations area (top) of the code sheet but Set the variable in a sub or function.
Don't forget to add 1 to the row returned if you want the 'next empty row'.

A: Just another alternative using the SpecialCells method of a `Range:
Option Explicit

Sub Test()
    Debug.Print "Last row on Sheet1 is: " & FirstCompletelyEmptyRow(Sheet1)
End Sub

Function FirstCompletelyEmptyRow(ByRef wsTarget As Worksheet) As Long
    FirstCompletelyEmptyRow = wsTarget.Range("A1").SpecialCells(xlCellTypeLastCell).Row + 1
End Function

redpajama_set_name: RedPajamaStackExchange


text:
BioM: Goldbach, Eveline E. #2 (1963)
Contact: stan@wiclarkcountyhistory.org
Surnames: Goldbach, Stewart, Scharf, Carlsen, Alexander, Uedina, Noble
----Source: OWEN ENTERPRISE (Owen, Clark County, Wis.) 09/19/1963
Goldbach, Eveline E. #2 (31 AUG 1963)
The First Congregational Church in Owen was the scene of the nuptials uniting Eveline Elizabeth Goldbach and Lanny Thomas Stewart on Saturday night, Aug. 31st, 1963. The bride is the daughter of Mr. and Mrs. Roy A. Echert of St. Paul and the parents of the groom are Mr. and Mrs. Arthur T. Stewart of Withee (Clark Co., Wis.). The Rev. Ralph Claybaugh performed the 4:00 o'clock in the afternoon ceremony. The altar was adorned with white candles and white gladioli. Baskets with sprays of white gladioli and mums in gold also added to the nuptial scene as the bride was given in marriage by Mr. Roy A. Echert. David Jablonic of Owen sang "The Wedding Prayer" and "The Lord's Prayer," and he was accompanied by Jane Westendorf at the organ.
The bride was attired in a white floor length silk organza and lace gown fashioned in a modified princess style. The bodice was decorated with flowers and lace, having a scooped neckline, short sleeves and featured a double draped bow in the back. Her elbow length veil was held by an orange blossom circlet and she carried a bouquet of white roses.
Mrs. Ramona Scharf of Bangor, Mich., a sister of the groom, was matron of honor. Miss Gisela Alexander of St. Paul and Mrs. Donna Uedina of St. Paul were bridesmaids. Her attendants were gowned alike in gold satin brocade gowns, sleeveless styled with a low square back accented with bows and streamers. A short veil was fastened to their rosebud headpiece, their shoes matched their dresses and they carried fall bouquets in colonial style.
Mr. Marlon Scharf of Bangor, Mich., the groom's brother-in-law, was best man. Groomsmen were Mr. Kenneth Carlsen of Withee and Mr. Jon Noble of St. Paul. Ushers were Mr. James Carlsen, Withee, and Mr. Robert Stewart, Stanley.
A dinner was served in the church dining rooms following the ceremony.
The bride is a graduate of a junior college in Munich, Germany, and is employed as a bookkeeper at the Farmers Union Central exchange in St. Paul.
The groom is a graduate of the Owen-Withee High School and the Eau Claire Vocational School, where he majored in business administration. He is an Insurance Underwriter for Arrowhead Insurance Co. of St. Paul.
Following a two week honeymoon trip which took them to Niagara Falls, the newlyweds will be at home at 40 Joann Street in St. Paul, Minn.
Guests from away came from Eau Claire, Arcadia, Stanley, Thorp, Dorchester, Withee, Greenwood, portage, Plainfield, Prairie du Sac, Wautoma, Kaukauna, Madison, Milwaukee, Rockford, Brookfield, Appleton and Bangor, Mich.


text:
← WWF: Raw is War (07.07.97)
WWF: Raw is War (07.21.97) →
WWF: Raw is War (07.14.97)
Posted by Matt
WWF: Raw is War
Freeman Coliseum
The current WWF champs were as follows:
World Champion: The Undertaker (3/23/1997)
Intercontinental Champion: Owen Hart (4/28/1997)
European Champion: Davey Boy Smith (3/3/1997)
World Tag Team Champions: Vacant (6/16/1997)
They kick things off with a video package detailing how beloved the Hart Foundation were on the brief tour of western Canada, and how they expect the reaction to be quite different here tonight in Texas.
Your hosts are Vince McMahon & Jim Ross.
Out comes the Hart Foundation. It's another week where Bret talks about how much better Canada is than the USA. Vince corrects Bret when he tries to say that if he loses the WWF title match at SummerSlam, and reminds us that if Bret doesn't *win* the WWF title at SummerSlam, then he will never wrestle in the United States again, in a nice subtle bit only a heel could pull off. Over to Owen, he pulls out a tube of Blistex and tells Austin that he better "pucker up", because he's going to be kissing some butt come SummerSlam. Now to Davey Boy Smith. He's got a European championship match with Ken Shamrock scheduled for SummerSlam. If he doesn't beat Shamrock, he'll eat a can of Alpo. Next, Brian Pillman has a match at SummerSlam as well where he faces Goldust. Pillman puts over Dusty Rhodes for being a terrible dad and neglecting his son in return for feeding his own massive ego (and his face), which turned Dustin into the most celebrated drag queen of the century. Brian knows Dusty broke Goldust's heart, but Pillman says he'll rip it out of his chest. If Pillman doesn't win, he'll wear a dress. He finishes saying it might as well be one of Marlena's and he promises her dress won't be the only thing he'll be getting into. Jim Neidhart declares that if any of the Hart Foundation members lose at SummerSlam, he will shave his goatee off the next night on Raw. Bret says they're not confident about SummerSlam, they are just committed to excellence. He feels Canada has prettier money, prettier women, tougher sports, and tougher men. Whether America likes it or not, it's going to be a Canadian summer.
That's when the glass breaks and out comes Steve Austin onto the ramp with his WWF tag team title. After he yells and cusses at the Harts, Ken Shamrock walks out. Then the PATRIOT debuts and stands by Steve Austin. Next, PSYCHO SID returns. And finally, San Antonio's own Shawn Michaels stands beside the other four men. Who is Austin's tag partner going to be? It's safe to assume it's one of these four men, right? Better stick with the whole program to find out!
Jerry Lawler & Brian Christopher vs. Ivan & Scott Putski
As he did many years ago, 56 year-old Ivan Putski sings the Bobby Vinton song "My Melody of Love" before the match. It's what ALL the kids are listening to these days. Lots of miscommunication errors between the Lawlers. JR says that the King admitted that he and Brian were related, but they were just brothers. Scott plays face in peril and takes a MEMPHIS PILEDRIVER from Lawler. Christopher wants to show off in front of daddy, but misses the Tennessee Jam. Hot tag to Ivan and as the match breaks down, Ivan nails the POLISH HAMMER for the win. (4:55) Little known fact: I actually dig what I've seen of Ivan Putski from the 1970s. I get it. ¾*
Let Us Take You Back to: WARZONE, 7/7/97. During the Austin/HHH match, Helmsley hit Mankind with a chair intended for Austin and then turned around into a Stone Cold Stunner. They also show Austin tricking Mankind and then being told he's going to regret it.
We now go backstage to Mankind. Vince asks him a few questions, but gets no response. Mankind just sits there and rocks back and forth.
Now over to Paul Bearer. JR told us he was going to drop a bomb this week. Bearer promises that next week he's going to prove that Kane is alive.
TAKA Michinoku vs. Yoshihiro Tajiri
Before making it to ECW in 1999, Tajiri wrestled for many different independent Japanese promotions like Michinoku Pro, WAR, IWA Japan, and most successful in the very hardcore Big Japan promotion. Now he's here on a very part time basis in the WWF. Without the signature goatee, he resembles a young Yuji Nagata. TAKA gets a video package showing off some of the moves we've seen him perform in his matches with the Great Sasuke. Really good lucha libre start to things that ends with Michinoku giving Tajiri a dropkick to the floor. TAKA explodes onto Tajiri with a springboard plancha! Back inside, Tajiri powerbombs Michinoku down and disorients TAKA with a version of the Oklahoma Roll. To the outside again, Tajiri lands an Asai Moonsault. Back inside, we get some heavy blows traded between the two. Dragon Suplex by Tajiri gets two. TAKA quickly rallies back with the missile dropkick to the back of the head followed by the MICHINOKU DRIVER for the 1-2-3. (4:11) This was pretty good and very little error in the spots. While Tajiri wrestles a couple more times on RAW in 1997 to enhance TAKA and Christopher, TAKA appears about once a month before he signs a long term contract in late October to begin the Light Heavyweight title tournament. ***
In the locker room, Ken Shamrock tells us that he's not Steve Austin's partner. He was just out there in support against the Hart Foundation. Besides, he's got his own match tonight against Jim Neidhart. KNUCKLE UP TIME!
Earlier today, Los Boricuas arrive at the Freeman Coliseum in one of those stereotypical, gaudy, tricked-out cars.
Read the latest WWF Magazine for an article on whether or not Brian Pillman's allegiance truly lies with the Hart Foundation.
In the back, the Headbangers compare Los Boricuas to Cheech & Chong. They're not very bright.
The Headbangers vs. Miguel Perez Jr. & Jose Estrada Jr. (w/Savio Vega & Jesus Castillo)
Headbangers control to start as they deliver a double gourdbuster to Estrada. Mosh is *your* face in peril. Pretty standard stuff here. Mosh blocks a corner charge and drives Estrada's head into the middle buckle with a headscissors. Hot tag to Thrasher and the match breaks down. Thrasher wants a powerbomb on Perez, but Miguel counters and victory rolls him up for the 1-2-3. (4:26) As Los Boricuas beat up the Headbangers, the Disciples of Apocalypse ride down to make the save. ½*
Elsewhere, the Patriot says he's not Steve Austin's partner either. He just wants to beat up anyone who speaks out against America.
Vince brings out Shawn Michaels to a hero's welcome for his big return interview. Is he going to be Austin's partner? Michaels says he's not at 100%, but that's never stopped him before. Shawn changes gears over to Bret Hart. He's looking forward to Bret never wrestling on US soil again. HBK brings up SummerSlam and says it wasn't his choice to not be a part of SummerSlam, it was someone else's and looks over at Vince. He tries to appeal to Vince and gets on his knees to beg Vince to somehow be a part of the show. He'll set up the ring, he'll sell souvenirs, he'll sell tickets at the door, he'll even shine Vince's shoes if he'll grant him a ticket to SummerSlam because he doesn't want to miss the Undertaker defeating Bret Hart and running him out of this country. GET THE F OUT, BRET. Makes you wonder if there isn't more to that sentiment than a "kayfabe" stipulation. Shawn tries to strip out of his shorts, but Vince covers him up with a towel. Somewhere Pat Patterson is PISSED. Whatever you do, don't leave us now!
TIME TO ENTER THE WARZONE! Jerry Lawler joins us at the commentary table for the rest of the show.
Savio Vega comes out and grabs a cameraman shouting that there's been an accident backstage that the world needs to see. It's just Los Boricuas trying to tear up the DOA's bikes. That leads another big brawl between the two gangs. As WWF agents and refs break up the fight, Los Boricuas hop in their car and drag one of the DOA bikes behind them. Skull & 8-Ball go after them while Crush stays behind with Chainz.
Ken Shamrock vs. Jim Neidhart
Neidhart is not on his game here tonight. Lots of punches and chinlocks from the Anvil. He looks like he NO-SELLS a hurracanrana and gets put out with a sleeper hold. (4:41) Weird finish. Davey Boy Smith runs out and attacks Shamrock after the match. Not sure if the British Bulldog was supposed to break up that sleeper hold for a DQ or not. There's a 2-on-1 beatdown, but the Patriot runs down for the save and gives both Neidhart and Bulldog UNCLE SLAMS. ½*
Vince tries again to speak with Mankind. Again, no response.
The Legion of Doom vs. The New Blackjacks
No match. The Godwinns attack the Legion of Doom during their entrance with chairs. Henry gives Hawk a SLOP DROP on the ramp to bust open the back of his head. These two teams will meet at SummerSlam. LOD! LOD! LOD!
Vader (w/Paul Bearer) vs. Flash Funk
Vader pounds on Funk and avalanches him in the corner. Funk fires back with a dropkick that sends Vader to the floor. Flash nails Vader with a plancha and whips him into the steps! Back inside, Vader hits Funk with a body attack and short-arm clotheslines Flash for a splash for two. Funk avoids a Powerbomb and kicks Vader down for a Moonsault! Cover, 1-2-NO! Flash comes off the ropes, but charges into another Body Attack. That staggers Flash and Vader puts him down with a POWERBOMB for the win. (4:11) After the bell, Vader gives Flash a VADER BOMB because he does what he wants to. **½
Vince talks with Steve Austin and asks him if Mankind will be his partner. Austin mentions how Mankind says he's going to resort to drastic measures, Austin says he hasn't been 100% all year long and everyday he gets out of bed is a drastic measure. The bottom line is he's not leaving San Antonio without the WWF tag team championship.
So what was the point of Psycho Sid showing up? Was he not even supposed to be here? He's been a non-factor all night.
Vacant WWF Tag Team Titles Match: Owen Hart & Davey Boy Smith vs. Steve Austin & A Mystery Partner
Austin comes out alone as he has said all along that he didn't mind doing. He handles himself okay brawling with both Owen and Bulldog until he tries a Sharpshooter on Owen. A submission in a handicap match is just a stupid babyface mistake. Bulldog throws Austin out for some guardrail action and a trip to the steps courtesy of Owen. Vince informs us that Austin's partner has arrived. We cut to the backstage area, but all we can see are a pair of white boots and some blue tights. There's also a little drum beat going over the PA system. Commercials! In the ring, Austin is drilled with a Belly to Belly Suplex by Owen. The heat segment continues until Austin cleans house on the two Hart Foundation members. While Austin waits for them in the ring, Mankind appears on the TitanTron acting completely different and wearing tie-dye and some John Lennon glasses. He doesn't blame Austin for not wanting to team with a freak like Mankind, but what about the hippest cat in the land Dude Love! He's coming to save the day. OWWW HAVE MERCY! Out comes Dude Love doing his thing and Austin does all he can to keep from laughing. He tags Dude in against Owen. Dude hits the running knee in the corner and asks Steve if he wants a tag, but he's not ready for that. Tag to Davey, Dude slips out of the Running Powerslam position and locks in the MANDIBLE CLAW! Owen breaks it up with a Missile Dropkick. While the ref is busy with Owen, Austin sneaks in and delivers a quick STONE COLD STUNNER to the Bulldog. Dude lays on top and covers for the 1-2-3! (7:38 shown) JR – "It's the Summer of Love, and we've got *new* tag team champions." One of my fave JR calls for some reason. Interesting that when Austin and Michaels won the tag belts two months ago, it was Shawn who gave Austin the assist with Sweet Chin Music to Bulldog behind the ref's back. Afterwards, a couple chicks swarm Dude Love as Austin hands him a belt. Just a very fun moment and one of the most memorable main events in Raw history. ***
Posted on August 25, 2013, in WWE and tagged 8-Ball, Barry Windham, Big Van Vader, Bradshaw, Bret Hart, Brian Christopher, Brian Pillman, Chainz, Crush, Davey Boy Smith, Disciples of Apocalypse, Dude Love, Flash Funk, Godwinns, Hart Foundation, Headbanger Mosh, Headbanger Thrasher, Headbangers, Henry O. Godwinn, Ivan Putski, Jerry Lawler, Jesus Castillo, Jim Neidhart, Jose Estrada Jr., Ken Shamrock, Legion of Doom, Los Boricuas, Mankind, Miguel Perez Jr., Owen Hart, Paul Bearer, Phineas I. Godwinn, Psycho Sid, Raw, Road Warrior Animal, Road Warrior Hawk, Savio Vega, Scott Putski, Shawn Michaels, Skull, Steve Austin, Tajiri, Taka Michinoku, The Blackjacks, The Patriot, Triple H. Bookmark the permalink.	Leave a comment.


The Laura Ashley Bathroom Collection consists of bathroom furniture, cabinets and mirrors, hand painted in soft greys and off white or constructed in solid oak, with worktop options including honed marble and granite. Three sanitary ware ranges incorporating basins and WCs spanning classic and contemporary styles. And from the seriously contemporary open spout design to more traditional styling, Laura Ashley's premium tap collection has been developed to coordinate perfectly.
For further information about our Laura Ashley bathroom furniture range, please contact our expert team at +353 (0)46.902.9444 or email info@versatile.ie.


Katy shares comforting and hilarious tales of the ghostly happenings in Gloucestershire, England in this latest episode. We go from the New Inn Hotel where a spirit throws back one last pint to the Chavenage House where all manner of historical haunting occurs, up to and including a headless horseman. Listen and Enjoy!


This diagram shows the percentages of websites using various character encodings among the sites that use HubSpot CMS. See technologies overview for explanations on the methodologies used in the surveys.
UTF-8 is used by 100.0% of all the websites whose character encoding we know and that use HubSpot CMS as content management system.
You can find usage and market share data for all 45 character encodings amongst HubSpot CMS sites in our HubSpot CMS market report.


Hello! I'm back after a little hiatus (SORRY!) with a Country Ladies special, as a sort of tribute to the recently departed Kitty Wells (who I may have referred to as Kitty Webb in the actual episode, thank you 3am). Featuring Dolly Parton (pictured), Jolie Holland, Emmylou Harris, Patsy Cline, The Dixie Chicks, Hazel Dickens & Alice Gerrard, Loretta Lynn, Gillian Welch, Neko Case and of course, Kitty Wells.


The Detroit Athletic Club (DAC) was organized in 1887 as a place for men to congregate and watch or participate in sporting events of all kinds. The original DAC field and clubhouse, located on land bordered by Woodward, Cass, Forest Avenues and Canfield Street provided spacious grounds and a full gymnasium for track and field, baseball, basketball, football, bowling, cricket, and bicycle racing. The DAC was an eminent member of the Amateur Athletic Union of the United States (AAU), hosting its inaugural track and field competition and winning AAU national baseball championships in 1890 and 1892. Despite excelling at a wide array of sports, the DAC lacked the social facilities to generate sufficient revenue for its operations and was subsidized through 1913 by the generosity of its member and past president John Kelsey.
With the decline in membership of the DAC due to members' interests shifting to business, especially the growing automobile industry, and away from amateur sports, the leadership decided there was a need for a rejuvenated sporting club. Henry B. Joy, president of the Packard Motor Car Company, led a group of prominent businessmen, many of them members of the automobile aristocracy, in planning for a new DAC building at 251 Madison Avenue. On January 4, 1913, the final act of the original DAC was to sign over the charter and all formerly won trophies to the new DAC board of directors, officially allowing them to use the renowned title for their new endeavor.
In 1913, the DAC board of directors commissioned architect Albert Kahn to design their new clubhouse. The ornately detailed six-story structure was inspired by Kahn's trip to Rome and Florence to view Renaissance architecture. In particular, the large fourth floor windows were designed after the Palazzo Farnese in Rome. The structure was planned with three distinct sections: the first and second floors housed social rooms, the third and fourth floors were intended for athletics, and the fifth and sixth floors were residential rooms. Though changes and modernizations have been undertaken since its completion in 1915, the building's layout remains basically as Kahn designed it.
Over the years, the DAC has provided financial assistance and training facilities to several athletes preparing for the Olympic Games. From its grand opening on April 17, 1915, the DAC was one of the first clubs of its type to allow the women of member's families in the clubhouse. Over the years it has greatly expanded its programs and facilities for women and the entire families of members, though women were not allowed to become full voting members until 1986. On the club's 30th anniversary in 1945, the members voted to curtail the celebration in order to open the building up for three days to over 1000 wounded veterans.
View all items related to the Detroit Athletic Club.


text:
LITTWIN
Sun Columns
Indy Archives
Thank you to the loyal readers and supporters of The Colorado Independent (2013-2020). The Indy has merged with the new nonprofit Colorado News Collaborative (COLab) on a new mission to strengthen local news in Colorado. We hope you will join us!
Visit COLab
The Colorado Independent
Home Center Well Bush Admin's environment waivers remain intact at border
Center Well
Bush Admin's environment waivers remain intact at border
Mike Lillis
The U.S.-Mexico border fence ends on the Pacific coastline of California (Photo/Bisayan lady, Flickr)
Last July, presidential candidate Barack Obama took a stage in Berlin and told the adoring crowd that a wall erected between people — like that which divided the German capital for decades — would best be knocked down.
"The walls between the countries with the most and those with the least cannot stand," Obama said to roaring applause. "The walls between races and tribes; natives and immigrants; Christians and Muslims and Jews cannot stand. These now are the walls we must tear down."
Eight months later, hundreds of miles of border fence dividing the United States and Mexico are going up as planned. Despite pleas from some Democrats, environmentalists and local communities to halt construction until the wall's impacts can be better examined, the Department of Homeland Security under President Obama has so far maintained the same border fence policies as the DHS under President Bush — a position reminiscent of the Obama's continued support of certain controversial Bush terrorism policies.
The status quo approach comes as something of a surprise. Although, as a senator, Obama voted in 2006 to approve the fence strategy, he said on the campaign trail last year that he would "reverse" Bush-era fence policies in favor of a "better approach," like deploying more border guards and installing better surveillance technologies.
More recently, his appointment of a vocal fence critic, former Arizona Gov. Janet Napolitano, to head the DHS signaled to many observers that fence policy would be soon to change. (Napolitano once mocked the border fence concept as futile, saying that "if you build a 50-foot-high wall, somebody will find a 51-foot ladder.") At the very least, fence critics hoped that the Obama White House would reinstate dozens of environmental, public health and cultural heritage laws that the Bush administration waived to expedite fence construction, including statutes designed to protect endangered species, drinking water and Native American graves.
Yet more than two months after both Obama and Napolitano were sworn in, those waivers remain in place. And they'll stay there, officials say, at least until the 670-mile-long first phase of fence construction is complete.
"We've committed to 670 miles," said Lloyd Easterling, spokesman for U.S. Customs and Border Protection, a branch of the DHS. "We're going to go ahead and meet those goals."
Easterling said "there was some question about stopping construction" when the new administration arrived, but the idea never materialized.
For environmentalists and congressional Democrats worried about the wall's effects on local communities and ecosystems, the episode presents a dilemma. On one hand, these Obama supporters are optimistic that the young administration will eventually make good on its vows to break away from Bush's border policies. On the other, they're wary that the changes aren't yet installed, allowing fence construction to continue through some of the most sensitive wilderness lands in the country. And of course, once a section goes up, it won't be easy to get down.
For the administration, the fence is a political landmine that touches on a host of issues no less volatile than immigration, national security, landowner rights, the war on drugs and the environment. Complicating the debate, border violence has crescendoed in the last year, putting pressure on policymakers at all levels of government to prevent that crime from spilling further into the United States than it's already come.
Still, some fence critics are beginning to challenge the White House to follow through on its pledges to examine fence policy more closely. In February, a group of eight border-state Democrats called on Obama to suspend fence construction until its impacts — cultural, political and environmental — could be scrutinized. The fence was "ill conceived" and "void of any meaningful input from the local communities," the lawmakers wrote in a Feb. 10 letter to the president. "In an era of advanced technologies, the border fence is an antiquated structure that has torn our communities apart and damaged our cross border relationships."
One signatory was Rep. Solomon Ortiz (D), who represents the Southeastern tip of Texas. In a telephone interview last week, Ortiz said that members of his office have met with Napolitano's staff, adding that the new administration has been much more receptive than the last to lawmakers' concerns about the fence. But Ortiz was also quick to reiterate his opposition to the waivers — and to the continued construction of the fence itself.
"It doesn't sit well with the people in my district," he said. "They don't like it, [and] I don't like it."
Aaron Hunter, spokesman for Rep. Susan Davis, a Southern California Democrat who also signed the letter, said last week that the White House has not responded to the lawmakers' concerns.
Easterling, the CBP spokesman, said the agency doesn't have far to go to complete the first phase of construction. As of last week, he said, 613 of the 670 miles were up, and the remaining sections — most of which reside in California and Texas — should be finished by year's end. Afterwards, he added, the administration will pause for a broader review before continuing to the next phase.
That there are fewer than 60 miles remaining in the first phase of construction has done little to stop fence opponents from pushing to have it stopped. Michael Degnan, Sierra Club lands representative, said that some of the unbuilt sections — including stretches in California's Otay Mountain Wilderness Area and the Lower Rio Grande Valley in Texas — are also the most isolated, and therefore the most worthy of protecting from development. The wall, environmentalists say, cuts straight through the heart of breeding corridors used by such threatened species as the jaguar, ocelot and low-flying cactus ferruginous pygmy owl.
"Some of the last places are also the most ecologically rich," Degnan said.
Last week the Sierra Club, which endorsed Obama the candidate, urged Obama the president to halt all current and future fence construction "to review the full impacts and effectiveness" of the imposing barrier.
There are other concerns associated with the border wall. In August, flooding attributed to the fence damaged Arizona's Organ Pipe Cactus National Monument, and another flood a month earlier caused millions of dollars of property damage on both sides of the border near Nogales, Ariz.
In 2007, 69 graves of the Tohono O'odham tribe were destroyed by fence construction south of Tuscon, with fragments of human bone discovered in the bulldozer tracks, the tribe's chairman testified before a congressional panel last year.
Fence critics contend that the waived laws — which include the Endangered Species Act, the Safe Drinking Water Act and the Native American Graves Protection and Repatriation Act — could have prevented such crises.
"If they'd followed the procedure and done the proper impact studies," Matt Clark, of Defenders of Wildlife, said of the flooding, "they might have avoided a disastrous situation."
Easterling said the CBP has "been very cognizant" of the wall's effects, maintaining that the agency has conducted all the appropriate impact reviews. The waivers, he added, were necessary only to prevent lawsuits from hindering the process — a claim strongly disputed by environmentalists.
"There was really no reason for them to waive those laws unless they had reason to think they couldn't comply with them," Clark said.
Still, border fence critics have been much easier on the Obama administration than they were on President Bush. When the Bush administration announced a year ago that it was waiving roughly three dozen environmental laws, a number of powerful Democrats signed their support to a Defenders of Wildlife lawsuit contending that the waivers were unconstitutional — an effort spearheaded by House Homeland Security Committee Chairman Bennie Thompson (D-Miss.). Requests for comment from nearly all the supporters of that push — including Thompson, who was traveling on the border with Napolitano last week — went unanswered.
In another effort to protect the border environment, Rep. Raul Grijalva (D-Ariz.), who signed the Feb. 10 letter to Obama, introduced legislation in the last Congress to revoke the waivers — a bill that has yet to resurface this year. Calls and emails to Grijalva's office also went unanswered.
Politically speaking, the silence is understandable. With the sharp increase in border drug violence making headlines nationwide, very few lawmakers appear willing to criticize the waivers or the fence for fear of being attacked for protecting ocelots above Arizonans.
The Washington Times neatly summarized this disdain for waiver opponents in an April 1 editorial, entitled "All the Pretty Mule Deer." The paper argued that the fence is a vital, if imperfect, law enforcement tool protecting the U.S. from a tsunami of criminality.
"When floodwaters are approaching, you begin filling sandbags to buttress the levee," the Times wrote. "You do not go to court to debate what type of sand to use."
Still, fence critics hope the Obama administration will step in sooner than later with a broad and revamped strategy for tackling the many thorny border issues — a strategy they hope will move away from the current reliance on an intrusive physical barrier dividing border communities and scarring delicate landscapes.
"Putting up a fence," said Hunter, "is not a comprehensive immigration policy."
Dept of Homeland Security
Task force to Homeland Security: Stop Secure Communities
Watch the NBA All-Star game today to see Carmelo one last time–and to join the War on Terror
Flashback: Tancredo on the virtual border fence boondoggle
DeMint would add border-fence provision to finance regulation bill
In high country, worry over economic backlash from McInnis immigration stance
tips@coloradoindependent.com
The Colorado Independent,2020
The Colorado Independent has been amplifying the voices of vulnerable Coloradans and holding public officials to account since 2013. Starting in late spring of 2020, we are teaming up with the Colorado Press Association and Colorado Media Project as part of the Colorado News Collaborative (COLab), an incubator for journalists to collaborate at a time when news resources are scarce. Our primary role is to work one-on-one with journalists in newsrooms statewide to help them report challenging stories they are unable to cover alone.
.hearken-header { background-color: #9572a0 !important; color: #ffffff !important; text-align: center !important; padding: 16px 16px !important; font-weight: 800 !important; font-size: 21px !important; line-height: 25.2px !important; font-family: Verdana, sans-serif !important; box-sizing: border-box !important; } .td-trending-now-title { background-color: #fb9204; } .td-trending-now-title:hover { background-color: #fb9204; } #header-announcment { background: #4085ff; text-align: center; line-height: 1.5; padding: 2rem; color: white; font-size: 1.1rem; } #header-announcement-button { line-height: inherit; color: white; border: solid 2px white; padding: 0.5rem 1rem; transition: 0.3s; } #header-announcement-button:hover { line-height: inherit; color: #4085ff; background-color: white; border: solid 2px #4085ff; padding: 0.5rem 1rem; }


Under CSA (Compliance, Safety, Accountability),truck drivers are held responsible for their equipment. For example, in "Table 5. CSMS Vehicle Maintenance BASIC Violations" (A-14) of "CARRIER SAFETY MEASUREMENT SYSTEM (CSMS) METHODOLOGY," any inoperative head lamp, tail lamp or turn signal carries a "Violation Severity Weight" of 6 on a scale of 1 to 10.But if you are allready broke down ,there is nothing to do that take some action and do repair .But if your repair requeres a part replacement at Freighliner and Volvo Truck Parts we are here to help you.We have body shop on site where we offer installations .Be safe on the road !
To determine the Real Cost of Ownership for its on-highway trucks, Freightliner identifies five main contributing factors to maximizing profitability: fuel efficiency, connectivity, safety, quality and uptime. Slightly different factors, however, apply to efforts to maximize profitability for vocational trucks. These are productivity, upfit, safety, quality and uptime.


OKEMAH, Okla. (AP) -- Police in Texas say the bodies of a woman and man found in shallow graves in rural Oklahoma are those of two missing central Texas residents.
Police in Minnesota confirmed Tuesday that Marks, according to KCEN-TV, was a possible person of interest in the 2009 disappearance of his 30-year-old ex-girlfriend April Pease, but was never named a suspect. Pease was last seen in Bloomington, Minnesota and hasn't been heard from since.
KFOR contributed to this report.