%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% LaTeX 2e file
%%
%% Author : Alexander V. Konstantinou (akonstan@cs.columbia.edu)
%% Title  : "Computational Models of Change Propagation"
%% Date   : $Id: candidacy.tex,v 1.7 1999/12/06 19:43:45 akonstan Exp $
%%

\documentclass{article}

\title{Computational Models of Change Propagation}
\author{ Alexander V. Konstantinou \\
         Computer Science Department \\
         Columbia University in the City of New York\\ \\
         \texttt{akonstan@cs.columbia.edu} }
\date{Candidacy Exam\\ December 9th, 1999 }


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{document}

\bibliographystyle{alpha}      
%\bibliographystyle{plain}
%\bibliographystyle{unsrt}

\maketitle

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Purpose}

``The candidacy exam certifies that the student has demonstrated a 
depth of scholarship in the literature and the methods of the student's chosen 
area of research, and has demonstrated a facility with the scholarly
skills of critical evaluation and verbal expression.''
(source : CS Dept. Candidacy Exam Requirements).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Candidate Research Area Statement}

Network element and service configuration is currently a manual process.
System administrators configure devices and services by editing files, 
using text based interactive shells, or through some forms based graphical
user interface.  Each of these methods entails different risks.  For example,
a manually edited file may contain syntax errors, and changes through a shell
or a graphical interface may not be easily reversible.  State of the art
installations apply a combination of version control software and 
device/service-specific syntactical and semantic checkers (e.g. DNS lint)
to maintain correctness through change.

The current methodology is not without its risks since users may subvert 
the version control system, or push through changes that were flagged as 
erroneous by the checker (the entire \texttt{.com} domain was inaccessible for
over 24 hours when a Network Solutions employee ignored warnings and pushed
through a corrupted DNS root record).  Moreover, the syntax and semantic
checkers must themselves be configured to enforce the local domain policies.
Since each checker is custom developed for each device or service,
administrators must learn several different languages for expressing
configuration and policy constraints.

More importantly, this whole approach fails when configuration constraints
must be enforced across devices or services.  Currently, there is no
alternative but to depend on the expertise of system administrators who
must constantly maintain these high level constraints when making
configuration changes.  Sometimes, through human error, or an unforeseen
new interaction between services, multi-device/service configuration changes
may result in partial, or total network failure. Network administrators are
then forced to undo these changes by individually restoring each configuration
file.  If the correct order is not maintained, some changes are not undone,
or due to side effects which have made the previous network state unattainable
or unstable, normal network service may still not be restored.

The goal our research is to provide core technologies for automating those
aspects of network configuration.  Our approach focuses on :

\begin{itemize}
\item Extending existing network modeling languages to support modeling
     of static and dynamic network device and service configuration.
     This unified modeling language will provide an abstraction from
     the underlying configuration mechanisms and simplify the task of
     system administrators.  Additionally, the unified model will significantly
     simplify the task of defining cross device/service configuration
     constraints and change propagation,

\item Creating a configuration policy language which will enable system
     administrators to express constraints on configuration states and 
     configuration change propagation.  System administrators will use
     this language to create simple scripts for performing complex
     configuration changes, such as, migrating a web server to a new subnet.

\item Developing a configuration transaction system which will define the
     semantics of network device configuration transactions.  Configuration
     scripts will execute as a transaction which may be aborted or
     rolled over.

\item An architecture for integrating these novel technologies to existing
     networks along with a prototype implementation. 
\end{itemize}

More background on the project, which is called NESTOR (NEtwork Self 
managemenT and ORganization) may be found in the URL :

\texttt{http://www.cs.columbia.edu/dcc/nestor/}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Exam Scope and Structure}

The goal of the candidacy exam will be to assist the candidate in
establishing depth of scholarship in the literature related to his
research area.  Although the main application of this research will
be in network management, the non-architectural core research issues
require a background in language design, constraint languages and systems,
as well as transaction processing systems.  Given the breadth of the
material covered, and the candidate's previous experience in network
management it is desirable to narrow the focus of the exam to 
those other areas.

For that purpose, the candidate has selected references that cover the area 
that can be broadly characterized as ``computational models of change
propagation''.  In accordance to the requirements outlined in the
departmental candidacy exam requirements, the
candidate will prepare a 30 minute oral presentation based on the selected
references, followed by a 90 minute question and answer session.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Citations}

\begin{itemize}

\item Theory:
\cite{Mackworth:1977}
\cite{Mohr:1986}
\cite{Jaffar:1987}
\cite{Cohen:1990}
\cite{Mittal:1990}
\cite{Mackworth:1992}
\cite{Zanden:1992}
\cite{Minton:1992}

\item Algorithms:
\cite{Kumar:1992}
\cite{Sannella:1995}
\cite{Zanden:1994}
\cite{Borning:1996}
\cite{Fruhwirth:1998}

\item Interval Labels:
\cite{Davis:1987}
\cite{Hyvonen:1992}

\item Constraint Hierarchies:
\cite{Borning:1992}
\cite{Hiroshi:1996}

\item Systems/Imperative Constraint Programming:
\cite{Avesani:1990}
\cite{Wilk:1991}
\cite{Benson:1992}
\cite{Lopez-1994}
\cite{Smolka:1995}
\cite{Sabin:1996}

\end{itemize}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\bibliography{candidacy}

\end{document}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%