ELISA: An Estimated Load Information Scheduling Algorithm for Distributed Computing Systems

In this paper, we present a decentralized dynamic load scheduling/balancing algorithm called ELISA (Estimated Load Information Scheduling Algorithm) for general purpose distributed computing systems. ELISA uses estimated state information based upon periodic exchange of exact state information between neighbouring nodes to perform load scheduling. The primary objective of the algorithm is to cut down on the communication and load transfer overheads by minimizing the frequency of status exchange and by restricting the load transfer and status exchange within the buddy set of a processor. It is shown that the resulting algorithm performs almost as well as a perfect information algorithm and is superior to other load balancing schemes based on the random sharing and Ni-Hwang algorithms. A sensitivity analysis to study the effect of various design parameters on the effectiveness of load balancing is also carried out. Finally, the algorithm's performance is tested on large dimensional hypercubes in the presence of time-varying load arrival process and is shown to perform well in comparison to other algorithms. This makes ELISA a viable and implementable load balancing algorithm for use in general purpose distributed computing systems.

Architecture Optimization of Aerospace Computing Systems

Simultaneous consideration of both performance and reliability issues is important in the choice of computer architectures for real-time aerospace applications. One of the requirements for such a fault-tolerant computer system is the characteristic of graceful degradation. A shared and replicated resources computing system represents such an architecture. In this paper, a combinatorial model is used for the evaluation of the instruction execution rate of a degradable, replicated resources computing system such as a modular multiprocessor system. Next, a method is presented to evaluate the computation reliability of such a system utilizing a reliability graph model and the instruction execution rate. Finally, this computation reliability measure, which simultaneously describes both performance and reliability, is applied as a constraint in an architecture optimization model for such computing systems. Index Terms-Architecture optimization, computation

Byzantine-resilient distributed computing systems

This paper is aimed at reviewing the notion of Byzantine-resilient distributed computing systems, the relevant protocols and their possible applications as reported in the literature. The three agreement problems, namely, the consensus problem, the interactive consistency problem, and the generals problem have been discussed. Various agreement protocols for the Byzantine generals problem have been summarized in terms of their performance and level of fault-tolerance. The three classes of Byzantine agreement protocols discussed are the deterministic, randomized, and approximate agreement protocols. Finally, application of the Byzantine agreement protocols to clock synchronization is highlighted.

Classical and Cosserat plasticity and viscoplasticity models for slow granular flow

We consider models for the rheology of dense, slowly deforming granular materials based of classical and Cosserat plasticity, and their viscoplastic extensions that account for small but finite particle inertia. We determine the scale for the viscosity by expanding the stress in a dimensionless parameter that is a measure of the particle inertia. We write the constitutive relations for classical and Cosserat plasticity in stress-explicit form. The viscoplastic extensions are made by adding a rate-dependent viscous stress to the plasticity stress. We apply the models to plane Couette flow, and show that the classical plasticity and viscoplasticity models have features that depart from experimental observations; the prediction of the Cosserat viscoplasticity model is qualitatively similar to that of Cosserat plasticity, but the viscosities modulate the thickness of the shear layer.

Efficient algorithms for computing Reeb graphs

The Reeb graph tracks topology changes in level sets of a scalar function and finds applications in scientific visualization and geometric modeling. We describe an algorithm that constructs the Reeb graph of a Morse function defined on a 3-manifold. Our algorithm maintains connected components of the two dimensional levels sets as a dynamic graph and constructs the Reeb graph in O(nlogn+nlogg(loglogg)3) time, where n is the number of triangles in the tetrahedral mesh representing the 3-manifold and g is the maximum genus over all level sets of the function. We extend this algorithm to construct Reeb graphs of d-manifolds in O(nlogn(loglogn)3) time, where n is the number of triangles in the simplicial complex that represents the d-manifold. Our result is a significant improvement over the previously known O(n2) algorithm. Finally, we present experimental results of our implementation and demonstrate that our algorithm for 3-manifolds performs efficiently in practice.

Experimental evidence of the kinematic Cosserat effect in dense granular flows

To capture shear localization in the flow of dense granular materials in a continuum description, it has earlier been proposed that granular materials be treated as Cosserat, or micropolar, continua. Here, we provide experimental verification of the kinematic Cosserat effect, or the deviation of the particle spin from the material spin induced by the velocity gradient. Contrary to earlier belief, we find this effect to be sizable even outside the shear layers. Remarkably, the particles and material elements spin in opposite directions in flow through a hopper.

Towards formal specification of a distributed computing system

Onboard spacecraft computing system is a case of a functionally distributed system that requires continuous interaction among the nodes to control the operations at different nodes. A simple and reliable protocol is desired for such an application. This paper discusses a formal approach to specify the computing system with respect to some important issues encountered in the design and development of a protocol for the onboard distributed system. The issues considered in this paper are concurrency, exclusiveness and sequencing relationships among the various processes at different nodes. A 6-tuple model is developed for the precise specification of the system. The model also enables us to check the consistency of specification and deadlock caused due to improper specification. An example is given to illustrate the use of the proposed methodology for a typical spacecraft configuration. Although the theory is motivated by a specific application the same may be applied to other distributed computing system such as those encountered in process control industries, power plant control and other similar environments.

Structure and dynamics of two-dimensional sheared granular flows

The structure and dynamics of the two-dimensional linear shear flow of inelastic disks at high area fractions are analyzed. The event-driven simulation technique is used in the hard-particle limit, where the particles interact through instantaneous collisions. The structure (relative arrangement of particles) is analyzed using the bond-orientational order parameter. It is found that the shear flow reduces the order in the system, and the order parameter in a shear flow is lower than that in a collection of elastic hard disks at equilibrium. The distribution of relative velocities between colliding particles is analyzed. The relative velocity distribution undergoes a transition from a Gaussian distribution for nearly elastic particles, to an exponential distribution at low coefficients of restitution. However, the single-particle distribution function is close to a Gaussian in the dense limit, indicating that correlations between colliding particles have a strong influence on the relative velocity distribution. This results in a much lower dissipation rate than that predicted using the molecular chaos assumption, where the velocities of colliding particles are considered to be uncorrelated.

BSDD-2.0: Biomolecules Segment Display Device - An updated web accessible computing resource

The existing internet computing resource, Biomolecules Segment Display Device (BSDD), has been updated with several additional useful features. An advanced option is provided to superpose the structural motifs obtained from a search on the Protein Data Bank (PDB) in order to see if the three-dimensional structures adopted by identical or similar sequence motifs are the same. Furthermore, the options to display structural aspects like inter- and intra-molecular interactions, ion-pairs, disulphide bonds, etc. have been provided.The updated resource is interfaced with an up-to-date copy of the public domain PDB as well as 25 and 90% non-redundant protein structures. Further, users can upload the three-dimensional atomic coordinates (PDB format) from the client machine. A free molecular graphics program, JMol, is interfaced with it to display the three-dimensional structures.

Phased-Mission Analysis for Evaluating the Effectiveness of Aerospace Computing-Systems

Effectiveness evaluation of aerospace fault-tolerant computing systems used in a phased-mission environment is rather tricky and difficult because of the interaction of its several degraded performance levels with the multiple objectives of the mission and the use environment. Part I uses an approach based on multiobjective phased-mission analysis to evaluate the effectiveness of a distributed avionics architecture used in a transport aircraft. Part II views the computing system as a multistate s-coherent structure. Lower bounds on the probabilities of accomplishing various levels of performance are evaluated.

Dynamics of dense sheared granular flows. Part 1. Structure and diffusion

Shear flows of inelastic spheres in three dimensions in the Volume fraction range 0.4-0.64 are analysed using event-driven simulations.Particle interactions are considered to be due to instantaneous binary collisions, and the collision model has a normal coefficient of restitution e(n) (negative of the ratio of the post- and pre-collisional relative velocities of the particles along the line joining the centres) and a tangential coefficient of restitution e(t) (negative of the ratio of post- and pre-collisional velocities perpendicular to the line Joining the centres). Here, we have considered both e(t) = +1 and e(t) = e(n) (rough particles) and e(t) =-1 (smooth particles), and the normal coefficient of restitution e(n) was varied in the range 0.6-0.98. Care was taken to avoid inelastic collapse and ensure there are no particle overlaps during the simulation. First, we studied the ordering in the system by examining the icosahedral order parameter Q(6) in three dimensions and the planar order parameter q(6) in the plane perpendicular to the gradient direction. It was found that for shear flows of sufficiently large size, the system Continues to be in the random state, with Q(6) and q(6) close to 0, even for volume fractions between phi = 0.5 and phi = 0.6; in contrast, for a system of elastic particles in the absence of shear, the system orders (crystallizes) at phi = 0.49. This indicates that the shear flow prevents ordering in a system of sufficiently large size. In a shear flow of inelastic particles, the strain rate and the temperature are related through the energy balance equation, and all time scales can be non-dimensionalized by the inverse of the strain rate. Therefore, the dynamics of the system are determined only by the volume fraction and the coefficients of restitution. The variation of the collision frequency with volume fraction and coefficient of estitution was examined. It was found, by plotting the inverse of the collision frequency as a function of volume fraction, that the collision frequency at constant strain rate diverges at a volume fraction phi(ad) (volume fraction for arrested dynamics) which is lower than the random close-packing Volume fraction 0.64 in the absence of shear. The volume fraction phi(ad) decreases as the coefficient of restitution is decreased from e(n) = 1; phi(ad) has a minimum of about 0.585 for coefficient of restitution e(n) in the range 0.6-0.8 for rough particles and is slightly larger for smooth particles. It is found that the dissipation rate and all components of the stress diverge proportional to the collision frequency in the close-packing limit. The qualitative behaviour of the increase in the stress and dissipation rate are well Captured by results derived from kinetic theory, but the quantitative agreement is lacking even if the collision frequency obtained from simulations is used to calculate the pair correlation function used In the theory.

Dynamics of dense sheared granular flows. Part II. The relative velocity distributions

The distribution of relative velocities between colliding particles in shear flows of inelastic spheres is analysed in the Volume fraction range 0.4-0.64. Particle interactions are considered to be due to instantaneous binary collisions, and the collision model has a normal coefficient of restitution e(n) (negative of the ratio of the post- and pre-collisional relative velocities of the particles along the line joining the centres) and a tangential coefficient of restitution e(t) (negative of the ratio of post- and pre-collisional velocities perpendicular to line joining the centres). The distribution or pre-collisional normal relative velocities (along the line Joining the centres of the particles) is Found to be an exponential distribution for particles with low normal coefficient of restitution in the range 0.6-0.7. This is in contrast to the Gaussian distribution for the normal relative velocity in all elastic fluid in the absence of shear. A composite distribution function, which consists of an exponential and a Gaussian component, is proposed to span the range of inelasticities considered here. In the case of roughd particles, the relative velocity tangential to the surfaces at contact is also evaluated, and it is found to be close to a Gaussian distribution even for highly inelastic particles.Empirical relations are formulated for the relative velocity distribution. These are used to calculate the collisional contributions to the pressure, shear stress and the energy dissipation rate in a shear flow. The results of the calculation were round to be in quantitative agreement with simulation results, even for low coefficients of restitution for which the predictions obtained using the Enskog approximation are in error by an order of magnitude. The results are also applied to the flow down an inclined plane, to predict the angle of repose and the variation of the volume fraction with angle of inclination. These results are also found to be in quantitative agreement with previous simulations.

Ant colony optimization for reporting cell planning in mobile computing using selective paging strategy

Location management problem that arise in mobile computing networks is addressed. One method used in location management is to designate sonic of the cells in the network as "reporting cells". The other cells in the network are "non-reporting cells". Finding an optimal set of reporting cells (or reporting cell configuration) for a given network. is a difficult combinatorial optimization problem. In fact this is shown to be an NP-complete problem. in an earlier study. In this paper, we use the selective paging strategy and use an ant colony optimization method to obtain the best/optimal set of reporting cells for a given a network.

Low-field hopping conductivity in granular metals

The hopping conductivity of granular metals is known to be of the form sigma varies as exp (-(T0/T)12/) in the temperature range 20K

Optimal iterative schemes for computing the Moore-Penrose matrix inverse

Among the iterative schemes for computing the Moore — Penrose inverse of a woll-conditioned matrix, only those which have an order of convergence three or two are computationally efficient. A Fortran programme for these schemes is provided.