This paper demonstrates that it is possible to generate a reasonably accurate coordinate system on randomly distributed processors, using only local information and local communication. By coordinate systems we imply that each element assigns itself a logical coordinate that maps to its global physical location, starting with no apriori knowledge of position or orientation. The algorithm presented is inspired by biological systems that use chemical gradients to determine the position of cells. Extensive analysis and simulation results are presented. Two key results are: there is a critical minimum average neighborhood size of 15 for good accuracy and there is a fundamental limit on the resolution of any coordinate system determined strictly from local communication. We also demonstrate that using this algorithm, random distributions of processors produce significantly better accuracy than regular processor grids - such as those used by cellular automata. This has implications for discrete models of biology as well as for building smart sensor arrays.

Cell-cell and cell-environment interactions are controlled by a set of local rules that dictate cell behavior. With such local rules, emergence of computationally meaningful building blocks and hierarchies can be observed. For example, at the cellular level organization in the visual system, receptive field of a retinal ganglion cell displays an activation inhibition behavior that can be modeled as Mexican Hat wavelet or Difference of Gaussians. This precise organization is the product of a harmonious collaboration of different cell types located at the lower levels in a hierarchical structure for each ganglion cell. Moreover, a similar hierarchical organization is observed at higher levels in the visual system. This thesis investigates the visual system from several perspectives in an effort to explore the biological/computational principles underlying these local rules. The investigation results in a hybrid computer model that can combine the advantages of evolutionary and developmental principles to explore the effects of local rules on cellular differentiation, retinal mosaics, layered structures and network topology.

The whole in a complex system is the sum of its parts, plus the interactions between the parts. Understanding social, biological, and economic systems therefore often depends on understanding their patterns of interactions---their networks. In this thesis, the approach is to understand complex systems by making simple network models with nodes and links. It is first of all an attempt to investigate how the communication over the network affects the network structure and, vice versa, how the network structure affects the conditions for communication. To explore the local mechanism behind network organization, we used simplified social systems and modeled the response to communication. Low communication levels resulted in random networks, whereas higher communication levels led to structured networks with most nodes having very few links and a few nodes having very many links. We also explored various models where nodes merge into bigger units, to reduce communication costs, and showed that these merging models give rise to the same kind of structured networks. In addition to this modeling of communication networks, we developed new ways to measure and characterize real-world networks. For example, we found that they in general favor communication on short distance, two-three steps away in the network, within what we call the information horizon. / Helheten i ett komplext system är mer än summan av dess delar, då den även inbegriper interaktionerna mellan dem. Att studera sociala, biologiska och ekonomiska system blir därför ofta en fråga om att förstå deras interaktionsmönster, d.v.s. deras nätverk av noder och länkar. Med utgångspunkt i enkla nätverksmodeller undersöker avhandlingen i huvudsak hur kommunikation i nätverk påverkar nätverksstrukturen och, vice versa, hur nätverksstrukturen påverkar villkoren för kommunikation. Vi utforskade mekanismerna bakom hur nätverk är organiserade genom att modellera effekten av kommunikation i förenklade sociala system. En låg kommunikationsnivå visade sig ge upphov till kaotiska nätverk där ingen nod i princip hade fler länkar än någon annan. En hög kommunikationsnivå resulterade däremot i strukturerade nätverk, med några få centrala noder med många länkar, medan flertalet noder var perifera med enbart några få länkar. Det visade sig också att alla aktörer i nätverket gynnades av kommunikation, även när den var ojämnt fördelad. Kvaliteten på kommunikationen, d.v.s. informationens giltighet, var också avgörande för vilka positioner som gynnades i ett nätverk, vilket vi visade genom att studera aktörer som spred falsk information. Eftersom effektiv kommunikation är en viktig del i många nätverk betraktar vi utvecklingen av dem som en optimeringsprocess. Varje kommunikationshandling mellan noderna tar tid och genom att slå sig samman till större enheter begränsas dessa kostnader och gör nätverket effektivare. Dessa s.k. sammanslagningsmodeller gav upphov till samma typ av strukturerade nätverk som ovan. Genom att utveckla olika sätt att mäta nätverksstrukturer visade vi bland annat att många verkliga system främjar kommunikation över korta avstånd, två-tre steg bort i nätverket, innanför det vi kallar informationshorisonten. Vi uppskattade också den mängd information som krävs för att orientera sig i städer, och fann att det är lättare att hitta i moderna, planerade städer än i äldre städer som utvecklats under lång tid.

This thesis investigates designs that enable individual components of a distributed system to work together and coordinate their actions towards a common goal. While the basic motivation for our research is to develop engineering principles for large-scale autonomous systems, we address the problem in the context of resource management in server clusters that provide web services. To this end, we have developed, implemented and evaluated a decentralized design for resource management that follows four principles. First, in order to facilitate scalability, each node has only partial knowledge of the system. Second, each node can adapt and change its role at runtime. Third, each node runs a number of local control mechanisms independently and asynchronously from its peers. Fourth, each node dynamically adapts its local configuration in order to optimize a global utility function. The design includes three fundamental building blocks: overlay construction, request routing and application placement. Overlay construction organizes the cluster nodes into a single dynamic overlay. Request routing directs service requests towards nodes with available resources. Application placement partitions the cluster resources between applications, and dynamically adjusts the allocation in response to changes in external load, node failures, etc. We have evaluated the design using complexity analysis, simulation and prototype implementation. Using complexity analysis and simulation, we have shown that the system is scalable, operates efficiently in steady state, quickly adapts to external events and allows for effective service differentiation by a system administrator. A prototype has been built using accepted technologies (Java, Tomcat) and evaluated using standard benchmarks (TPC-W and RUBiS). The evaluation results show that the behavior of the prototype matches closely that of the simulated design for key metrics related to adaptability and robustness, therefore validating our design and proving its feasibility. / QC 20100629

Self-organizing overlay networks have emerged as a powerful paradigm for providing network services. While most approaches assume that overlay networks are built over a single substrate network, generally, the Internet, this thesis addresses the construction of overlay networks over multiple substrate networks. We present the design, implementation and evaluation of Cross-Substrate Advertisement (CSA) mechanisms for overlay networks over multiple heterogeneous substrate networks. A key difficulty arises from the more complex address bindings, since a single logical identifier is bound to multiple substrate addresses. We present mechanisms for exchanging information on address bindings and evaluate their effectiveness. The CSA mechanisms have been implemented in the HyperCast overlay protocol architecture, and have been evaluated in measurement experiments on an Emulab testbed. The experiments show that our CSA methods are effective in disseminating address information in large networks and are robust in the presence of network disruptions.

Self-organizing overlay networks have emerged as a powerful paradigm for providing network services. While most approaches assume that overlay networks are built over a single substrate network, generally, the Internet, this thesis addresses the construction of overlay networks over multiple substrate networks. We present the design, implementation and evaluation of Cross-Substrate Advertisement (CSA) mechanisms for overlay networks over multiple heterogeneous substrate networks. A key difficulty arises from the more complex address bindings, since a single logical identifier is bound to multiple substrate addresses. We present mechanisms for exchanging information on address bindings and evaluate their effectiveness. The CSA mechanisms have been implemented in the HyperCast overlay protocol architecture, and have been evaluated in measurement experiments on an Emulab testbed. The experiments show that our CSA methods are effective in disseminating address information in large networks and are robust in the presence of network disruptions.

Understanding the first order controls over resource cycling and limitation in ecosystems is critical for predicting ecosystem response to disturbances. Topography and vegetation self-organizing mechanisms are first order controls over resource fluxes across the landscape. Topography controls downslope flow of resources (i.e water and nutrients). Through spatial feedbacks, vegetation is able to actively modify its environment and maximize resource flows towards it. To date, the impacts of these controls on ecosystem dynamics have mostly been investigated separately. As such, there is a knowledge gap in the understanding of how these first order controls together dictate the dynamics of the ecosystem. This dissertation aims to gain a better understanding of how self-organizing mechanisms and topography operate together to affect wetland ecosystem dynamics. A spatially explicit, wetland vegetation patterning model that includes for both vegetation self-organizing control and topographic control is developed (Nutrient Depletion Model, NDM). The model describes a scale dependent feedback between vegetation, transpiration and nutrient accumulation that drives the formation of vegetation patterns. The model is applied to investigate the effects of topography and self-organizing mechanisms on form and orientation of vegetation patterns and vegetation growth dynamics of wetland ecosystems. Results show that the two first order controls synergistically impact the formation of the various patterns as observed in wetland ecosystems. Results also show the following: (1) Self-organizing mechanisms result in a more efficient retention of resources, which result in higher biomass in the model that include for both self-organizing mechanism and topographic control (SO+TC) than in the model that that includes only for topographic control (TC). (2) However, when resources or topographic gradients increase or annual rainfall decrease, the vegetation growth dynamics of the TC+SO and TC models converge. The NDM is applied to arctic Alaska to investigate how do the two first order controls impact present and future C-N dynamics of an arctic ecosystem. Simulation results show no significant difference in the dynamics between the SO+TC model and the TC model. The climate change simulation results suggest that changes in daily variability of temperature and precipitation can impact ecosystem dynamics as much as the changes in mean temperature and precipitation. Results from this dissertation provide a more complete picture on the relative roles of the two first order controls over ecosystem nutrient cycling and vegetative growth dynamics. Finally, in this thesis, in order to simulate small-scale feedbacks over large spatial domains, the NDM is implemented in a GPU computing language, which accelerates computational simulation by at least two orders of magnitude. These tools for grid-based simulations can provide a platform for using GPUs in other areas of scientific investigation.

No description available.

Esta tesis se dedica en un estudio de estabilidad no lineal de la morfodinàmica de la zona de rompientes de playas de arena. El modelo numérico MORFO55 resuelve las ecuaciones de aguas someras no lineales para la hidrodinámica y actualiza la topografía a partir del transporte de sedimento. En primer lugar, se aplica en el caso de playas complejas longitudinalmente no uniformes con objeto de probar sus distintas formulaciones. En secundo lugar, se usa para estudiar la generación de estructuras rítmicas en playas longitudinalmente uniformes. Entre estos patrones se distinguen las barras transversales y oblicuas, las barras crescenticas y los sistemas de barras/surcos (ridges/runnels). La hipótesis de que emergen a partir de inestabilidades internas del acoplamiento entre la topografía y la hidrodinámica se investiga. Los estudios previos de modelización numérica se limitaban a las etapas iniciales de la generación de las barras. En particular, mostraban que las barras transversales y oblicuas pueden formarse en playas planas mientras que las barras crecenticas aparecen en playas con barra. La formación de los sistemas de barras/surcos se explica con modelos conceptuales de la observación mediante satélite según los cuales emergerán a partir de la deformación de la barra intermareal. Esta tesis estudia el régimen no lineal de la evolución de todos estos sistemas. Particularmente se obtiene un estado 'nal de equilibrio. Los resultados generales coinciden cualitativamente con las barras observadas en la naturaleza. Se da una interpretación física de la formación, de la evolución y de la saturación del crecimiento de las barras. / This thesis performs a nonlinear stability study of the surf zone morphodynamics of sandy beaches. To this end the MORFO55 model based on a wave and depth averaged nonlinear shallow water equations solver with wave driver, sediment transport and bed updating is presented. It is first applied to complex longitudinally non-uniform beaches in order to test different model formulations. Second, it is applied to study the generation of surf zone rhythmic features on alongshore uniform beaches. Shore-attached transverse or oblique bars, crescentic bars and ridge and runnel systems are well known examples of such features. The hypothesis that they emerge by self organisation of the coupling between topography, waves and currents is here tested. In absence of shore-parallel bars, the initial formation of transverse and oblique bars had been shown by previous modelling studies of linear stability analysis but is now extended to the finite amplitude regime. In most of barred beaches, crescentic bars and ridge and runnel systems appear. Conceptual models based on field observations suggest that ridges and runnels could emerge by the deformation of the alongshore intertidal bar intercepted by crescentic bars. Up to now, only the formation of crescentic bars had numerically succeeded with linear and non linear models. This study shows that a dynamical equilibrium state of each of these rhythmic bar systems may be described with a numerical model. General results are in qualitative agreement with the bar systems observed in nature. A physical explanation for their formation, their evolution and the saturation of their growth is given.

With the trend of using of Internet and multimedia, e-Learning has became an important learning method. e-Learning is easy to use and bring into practice, but it also has the defects inversely. One of those defects is the reuse of important and valuable discussing knowledge from asynchronous discussion boards. Nobody has time and be willing to make effort to manage the important discussion from asynchronous discussion boards in e-Learning except enthusiastic teachers or assistants. All of us know that asynchronous discussion boards is an important tool used in e-Learning for communicating and discussing with all class information for teachers and students. And reusing of important class discussing knowledge can aid teachers and students to teach and study with efficiency and effect. But up to the present, there are few researches in this domain. So, in this research we create an automatic essential content extraction method from asynchronous discussion boards in e-Learning. We explain the usage, management, and shortcomings of asynchronous discussion boards in e-Learning before. And we also describe the designing process of the research in detail. Finally, we describe the operation and the result of content extraction in this research system. All of those are hope to help teachers and students can reuse the valuable knowledge easily and quickly from past class discussion in e-Learning.