On Algebraic Structures and Automaton for Optimal Computer Network Design and Performance Study

For decades, study of computer networks has been concentrated on the use of the well-established OSI or TCP/IP reference models that have found tremendous success in the actual implementation of various network structures and protocols. Lack of theoretical foundation, this implementation-driven, empirical approach, however, is experiencing insurmountable difficulties in delivering, tuning for, and sustaining the promised peak performance of a computer system that is so heavily dependent on the performance of the underline computer networks. This issue is becoming particularly prevalent in today’s cloud-based high-performance computing environment where CPU-time-extensive computation loads need to get distributed among computing machines through high-speed networks. Instead of relying on empirical models and years of simulation runs needed to the design, verification, and performance evaluation of computer networks, which still does not give satisfactory results and often is inclined to miss many possible scenarios, gives rise to a need for the development of formal approaches and models to “formally” attack such network-related performance problem. Existing formal models adopted in computer systems include Alan Turing’s Turing machine and Church’s lambda calculus. One serious drawback of the Turing machine is that it does not provide a comprehensive symbolic system, while Church’s lambda calculus is considered too abstract from the hardware implementation perspective, making it exclusively accepted in programming language community and leaving no footprint in computer architectures. Although processor’s ISA can be viewed as some sort of a formal model, its abstraction level is too low, and it does not cap- ture designer’s intuition. On top of these problems, as there are many abstraction layers in the development of high-level programming, some valuable information gets lost during compilation and interpretation. Inspired by these existing formal models, and in reference to the advances in mathematical tools that are available to build and interpret today’s computation model, including category theory, homology, abstract algebra, type theory, calculus of Inductive Constructions, and Manifolds, we for the first time present a new abstract machine model and develop the algebraic framework (EQM ) that enables us to build a layered system to model universal computation. Along with a computation model comes the second problem referred as the model measurement. True to any complex and evolving system, changes in a system need to study by an applicable calculus system involving derivatives. To this end, we have developed differentiable manifolds from EQM . As an important class of manifolds, differentiable manifolds do allow calculus to be performed on manifolds. A Riemannian metric on a manifold thus allows distances and angles to be measured. In this dissertation, we essentially attempt to address a simple and seemly trivial problem that touches base on the foundation of computation: ”how to model the virtual network in a computer system?” The algebraic structures and automaton thus developed are a big step forward to show how to design optimal network systems and measure their performance. One less obvious outcome of this research endeavor is that we have demonstrated that it is very possible that a general distributed program can be realized without going for explicit synchronization