Implementing Distributed Systems Using Linear Naming

Linear graph reduction is a simple computational model in which the cost of naming things is explicitly represented. The key idea is the notion of "linearity". A name is linear if it is only used once, so with linear naming you cannot create more than one outstanding reference to an entity. As a result, linear naming is cheap to support and easy to reason about. Programs can be translated into the linear graph reduction model such that linear names in the program are implemented directly as linear names in the model. Nonlinear names are supported by constructing them out of linear names. The translation thus exposes those places where the program uses names in expensive, nonlinear ways. Two applications demonstrate the utility of using linear graph reduction: First, in the area of distributed computing, linear naming makes it easy to support cheap cross-network references and highly portable data structures, Linear naming also facilitates demand driven migration of tasks and data around the network without requiring explicit guidance from the programmer. Second, linear graph reduction reveals a new characterization of the phenomenon of state. Systems in which state appears are those which depend on certain -global- system properties. State is not a localizable phenomenon, which suggests that our usual object oriented metaphor for state is flawed.

Safe Distributed Coordination of Heterogeneous Robots through Dynamic Simple Temporal Networks

Research on autonomous intelligent systems has focused on how robots can robustly carry out missions in uncertain and harsh environments with very little or no human intervention. Robotic execution languages such as RAPs, ESL, and TDL improve robustness by managing functionally redundant procedures for achieving goals. The model-based programming approach extends this by guaranteeing correctness of execution through pre-planning of non-deterministic timed threads of activities. Executing model-based programs effectively on distributed autonomous platforms requires distributing this pre-planning process. This thesis presents a distributed planner for modelbased programs whose planning and execution is distributed among agents with widely varying levels of processor power and memory resources. We make two key contributions. First, we reformulate a model-based program, which describes cooperative activities, into a hierarchical dynamic simple temporal network. This enables efficient distributed coordination of robots and supports deployment on heterogeneous robots. Second, we introduce a distributed temporal planner, called DTP, which solves hierarchical dynamic simple temporal networks with the assistance of the distributed Bellman-Ford shortest path algorithm. The implementation of DTP has been demonstrated successfully on a wide range of randomly generated examples and on a pursuer-evader challenge problem in simulation.

Fast Sorting on a Distributed-Memory Architecture

We consider the often-studied problem of sorting, for a parallel computer. Given an input array distributed evenly over p processors, the task is to compute the sorted output array, also distributed over the p processors. Many existing algorithms take the approach of approximately load-balancing the output, leaving each processor with Θ(n/p) elements. However, in many cases, approximate load-balancing leads to inefficiencies in both the sorting itself and in further uses of the data after sorting. We provide a deterministic parallel sorting algorithm that uses parallel selection to produce any output distribution exactly, particularly one that is perfectly load-balanced. Furthermore, when using a comparison sort, this algorithm is 1-optimal in both computation and communication. We provide an empirical study that illustrates the efficiency of exact data splitting, and shows an improvement over two sample sort algorithms.

Scaling algorithms for distributed max flow

Bibliography: p. 22-24.

Un análisis comparativo del papel del bucle fonológico versus la agenda visoespacial en el cálculo en niños de 7-8 años = A comparative analysis of the phonological loop versus the visuo-spatial sketchpad in mental arithmetic tasks in 7-8 y.o. children

En esta investigación se ha estudiado la relación entre dos subsistemas de la memoria de trabajo (bucle fonológico y agenda viso-espacial) y el rendimiento en cálculo con una muestra de 94 niños españoles de 7-8 años. Hemos administrado dos pruebas de cálculo diseñadas para este estudio y seis medidas simples de memoria de trabajo (de contenido verbal, numérico y espacial) de la «Batería de Tests de Memoria de Treball» de Pickering, Baqués y Gathercole (1999), y dos pruebas visuales complementarias. Los resultados muestran una correlación importante entre las medidas de contenido verbal y numérico y el rendimiento en cálculo. En cambio, no hemos encontrado ninguna relación con las medidas espaciales. Se concluye, por lo tanto, que en escolares españoles existe una relación importante entre el bucle fonológico y el rendimiento en tareas de cálculo. En cambio, el rol de la agenda viso-espacial es nulo

El papel de la memoria de trabajo en el cálculo mental un cuarto de siglo después de Hitch = The role of working memory in mental arithmetic a quarter of century after Hitch

Desde que Hitch (1978) publicó el primer estudio sobre el rol de la memoria de trabajo en el cálculo han ido aumentando las investigaciones en este campo. Muchos trabajos han estudiado un único subsistema, pero nuestro objetivo es identificar qué subsistema de la memoria de trabajo (bucle fonológico, agenda viso-espacial o ejecutivo central) está más implicado en el cálculo mental. Para ello hemos realizado un estudio correlacional en el que hemos administrado dos pruebas aritméticas y nueve pruebas de la “Bateria de Test de Memòria de Treball” de Pickering, Baqués y Gathercole (1999) a una muestra de 94 niños españoles de 7-8 años. Nuestros resultados indican que el bucle fonológico y sobretodo el ejecutivo central inciden de forma estadísticamente significativa en el rendimiento aritmético

Automatic self-configuration of the logical network using distributed software agents

We present a system for dynamic network resource configuration in environments with bandwidth reservation. The proposed system is completely distributed and automates the mechanisms for adapting the logical network to the offered load. The system is able to manage dynamically a logical network such as a virtual path network in ATM or a label switched path network in MPLS or GMPLS. The system design and implementation is based on a multi-agent system (MAS) which make the decisions of when and how to change a logical path. Despite the lack of a centralised global network view, results show that MAS manages the network resources effectively, reducing the connection blocking probability and, therefore, achieving better utilisation of network resources. We also include details of its architecture and implementation

An ATM distributed simulator for network management research

Due to the high cost of a large ATM network working up to full strength to apply our ideas about network management, i.e., dynamic virtual path (VP) management and fault restoration, we developed a distributed simulation platform for performing our experiments. This platform also had to be capable of other sorts of tests, such as connection admission control (CAC) algorithms, routing algorithms, and accounting and charging methods. The platform was posed as a very simple, event-oriented and scalable simulation. The main goal was the simulation of a working ATM backbone network with a potentially large number of nodes (hundreds). As research into control algorithms and low-level, or rather cell-level methods, was beyond the scope of this study, the simulation took place at a connection level, i.e., there was no real traffic of cells. The simulated network behaved like a real network accepting and rejecting SNMP ones, or experimental tools using the API node

A distributed environment for virtual and/or real experiments for underwater robots

This paper presents the distributed environment for virtual and/or real experiments for underwater robots (DEVRE). This environment is composed of a set of processes running on a local area network composed of three sites: 1) the onboard AUV computer; 2) a surface computer used as human-machine interface (HMI); and 3) a computer used for simulating the vehicle dynamics and representing the virtual world. The HMI can be transparently linked to the real sensors and actuators dealing with a real mission. It can also be linked with virtual sensors and virtual actuators, dealing with a virtual mission. The aim of DEVRE is to assist engineers during the software development and testing in the lab prior to real experiments

Dynamic bandwidth management as part of an integrated network management system based on distributed agents

We present a system for dynamic network resource configuration in environments with bandwidth reservation and path restoration mechanisms. Our focus is on the dynamic bandwidth management results, although the main goal of the system is the integration of the different mechanisms that manage the reserved paths (bandwidth, restoration, and spare capacity planning). The objective is to avoid conflicts between these mechanisms. The system is able to dynamically manage a logical network such as a virtual path network in ATM or a label switch path network in MPLS. This system has been designed to be modular in the sense that in can be activated or deactivated, and it can be applied only in a sub-network. The system design and implementation is based on a multi-agent system (MAS). We also included details of its architecture and implementation

A Focus on Distributed Denial of Service

An Arbor Networks paper describing DDoS attacks and related attacks. The first 9-10 pages or so are good background reading for INFO6003. Students may also find the rest of the paper interesting.

Spontaneous Meta-Arithmetic as the First Step Toward School Algebra. 'La meta-aritmética espontánea como el primer paso hacia el álgebra escolar'.

Resumen basado en el de la publicación