Task behavior monitoring for adaptive real-time communication

Real-time distributed systems include communicating tasks that interact via message-passing. In such systems the timely delivery of messages is essential for meeting task timing constraints. Consequently, in addition to task execution times, message delivery times must also be constrained. In order to minimize the number of failures to meet timing constraints message communication protocols, in addition to task scheduling algorithms, play a crucial role. A legitimate question to ask is whether making such protocols adaptive to run-time system and environment status can significantly improve system performance. Consequently, a rum-time monitoring approach to adaptive real-time distributed systems is proposed; the work focuses on an investigation of adaptive message communication protocols and corresponding run-time support mechanisms. Simulation is used to obtain performance results. It is concluded that although improvement is obtained it ,ay not be significant enough to offset the increased overhead and requirement for task information.     

Testing axioms for quantum theory on probabilistic toy-theories

In D’Ariano in Philosophy of Quantum Information and Entanglement, Cambridge University Press, Cambridge, UK (2010), one of the authors proposed a set of operational postulates to be considered for axiomatizing Quantum Theory. The underlying idea is to derive Quantum Theory as the mathematical representation of a fair operational framework, i.e. a set of rules which allows the experimenter to make predictions on future events on the basis of suitable tests, e.g. without interference from uncontrollable sources and having local control and low experimental complexity. In addition to causality, two main postulates have been considered: PFAITH (existence of a pure preparationally faithful state), and FAITHE (existence of a faithful effect). These postulates have exhibited an unexpected theoretical power, excluding all known nonquantum probabilistic theories. In the same paper also postulate PURIFY-1 (purifiability of all states) has been introduced, which later has been reconsidered in the stronger version PURIFY-2 (purifiability of all states unique up to reversible channels on the purifying system) in Chiribella et al. (Reversible realization of physical processes in probabilistic theories, arXiv:0908.1583). There, it has been shown that Postulate PURIFY-2, along with causality and local discriminability, narrow the probabilistic theory to something very close to the quantum one. In the present paper we test the above postulates on some nonquantum probabilistic models. The first model—the two-box world—is an extension of the Popescu–Rohrlich model (Found Phys, 24:379, 1994), which achieves the greatest violation of the CHSH inequality compatible with the no-signaling principle. The second model—the two-clock world— is actually a full class of models, all having a disk as convex set of states for the local system. One of them corresponds to—the two-rebit world— namely qubits with real Hilbert space. The third model—the spin-factor—is a sort of n-dimensional generalization of the clock. Finally the last model is the classical probabilistic theory. We see how each model violates some of the proposed postulates, when and how teleportation can be achieved, and we analyze other interesting connections between these postulate violations, along with deep relations between the local and the non-local structures of the probabilistic theory.     

Comparison of connectionist and multiple regression approaches for prediction of body weight of goats

The Attappady Black goat is a native goat breed of Kerala in India and is mainly known for its valuable meat and skin. In this work, a comparative study of connectionist network [also known as artificial neural network (ANN)] and multiple regression is made to predict the body weight from body measurements in Attappady Black goats. A multilayer feed forward network with backpropagation of error learning mechanism was used to predict the body weight. Data collected from 824 Attappady Black goats in the age group of 0–12 months consisting of 370 males and 454 females were used for the study. The whole data set was partitioned into two data sets, namely training data set comprising of 75 per cent data (277 and 340 records in males and females, respectively) to build the neural network model and test data set comprising of 25 per cent (93 and 114 records in males and females, respectively) to test the model. Three different morphometric measurements viz. chest girth, body length and height at withers were used as input variables, and body weight was considered as output variable. Multiple regression analysis (MRA) was also done using the same training and testing data sets. The prediction efficiency of both models was compared using the R ² value and root mean square error (RMSE). The correlation coefficients between the actual and predicted body weights in case of ANN were found to be positive and highly significant and ranged from 90.27 to 93.69%. The low value of RMSE and high value of R ² in case of connectionist network (RMSE: male—1.9005, female—1.8434; R ²: male—87.34, female—85.70) in comparison with MRA model (RMSE: male—2.0798, female—2.0836; R ²: male—84.84, female—81.74) show that connectionist network model is a better tool to predict body weight in goats than MRA.     

Performing tasks on synchronous restartable message-passing processors

Summary. This work considers the problem of performing t tasks in a distributed system of p fault-prone processors. This problem, called do-all herein, was introduced by Dwork, Halpern and Waarts. The solutions presented here are for the model of computation that abstracts a synchronous message-passing distributed system with processor stop-failures and restarts. We present two new algorithms based on a new aggressive coordination paradigm by which multiple coordinators may be active as the result of failures. The first algorithm is tolerant of stop-failures and does not allow restarts. Its available processor steps (work) complexity is and its message complexity is . Unlike prior solutions, our algorithm uses redundant broadcasts when encountering failures and, for p =t and largef, it achieves better work complexity. This algorithm is used as the basis for another algorithm that tolerates stop-failures and restarts. This new algorithm is the first solution for the do-all problem that efficiently deals with processor restarts. Its available processor steps is , and its message complexity is , wheref is the total number of failures. Received: October 1998 / Accepted: September 2000     

A static scheduling algorithm for distributed hard real-time systems

A static scheduling algorithm is presented for off-line scheduling of tasks in distributed hard real-time systems. The tasks considered are instances of periodic jobs and have deadlines, resource requirements and precedence constraints. Tasks are divided into nonpreemptable blocks and all task characteristics are known a priori. The algorithm orders the tasks and iteratively schedules the tasks according to the order. Each task is scheduled globally by selecting a node to which it is assigned. Then, the task is scheduled locally by adding the task to the schedule of the selected node. Heuristics are used for both task ordering and node selection in order to guide the algorithm to a feasible schedule. Whenever local scheduling leads to an infeasible schedule, backtracking is used.Results of simulation studies of randomly generated task sets are presented. Although the scheduling problem is NP-hard, the results show that time performance is acceptable for off-line scheduling, except for extremely difficult task sets which make extensive use of the available resources.     

An Overview of Synchronous Message-Passing and Topology

A slowly-growing number of computer scientists have found that ideas from topology can be used to analyze and understand problems in distributed computing. In this paper, we review one approach we have used in the past to write a succinct proof of the lower bound for the number of rounds needed to solve the k-set agreement problem in a synchronous, message-passing model of computation. The central idea in this approach is a simple combinatorial structure we call a pseudosphere, in which each process from a set of processes is independently assigned a value from a set of values. Pseudospheres have a number of nice combinatorial properties, but their principal interest lies in the observation that the global states that arise in the synchronous, message-passing model can be viewed as simple unions of pseudospheres, and the fact that topological properties of unions of pseudospheres are so easy to prove. We choose this work to review because it is a simple example of how we model distributed systems with topology, and because it is the basis of on-going work to simplify the proof of this result.     

Self-Stabilizing Routing and Related Protocols

Aself-stabilizingsystem is a distributed system which can tolerateany numberandany typeof faults in the history. After the last fault occurs the system converges to alegitimate behavior. The self-stabilization property is very useful for systems in which processors may malfunction for a while and then recover. When there is a long enough period during which no processor malfunctions the system stabilizes.Dynamicdistributed systems are systems in which communication links and processors may fail and recover during normal operation. Such failures could cause partitioning of the system communication graph. The application of self-stabilizing protocols to dynamic systems is natural. Following the last topology change each connected component of the system stabilizes independently. We present self-stabilizing dynamic protocols for a variety of tasks including: routing, leader election, and topology update. For systems that support local broadcasts to neighbors in a single time unit the protocol for each of those tasks stabilizes in Θ(d) time, wheredis theactualdiameter of the system.     

A capabilities-based model for adaptive organizations

Multiagent systems have become popular over the last few years for building complex, adaptive systems in a distributed, heterogeneous setting. Multiagent systems tend to be more robust and, in many cases, more efficient than single monolithic applications. However, unpredictable application environments make multiagent systems susceptible to individual failures that can significantly reduce its ability to accomplish its overall goal. The problem is that multiagent systems are typically designed to work within a limited set of configurations. Even when the system possesses the resources and computational power to accomplish its goal, it may be constrained by its own structure and knowledge of its member’s capabilities. To overcome these problems, we are developing a framework that allows the system to design its own organization at runtime. This paper presents a key component of that framework, a metamodel for multiagent organizations named the Organization Model for Adaptive Computational Systems. This model defines the requisite knowledge of a system’s organizational structure and capabilities that will allow it to reorganize at runtime and enable it to achieve its goals effectively in the face of a changing environment and its agent’s capabilities.     

Distributed Approximation of Capacitated Dominating Sets

We study local, distributed algorithms for the capacitated minimum dominating set (CapMDS) problem, which arises in various distributed network applications. Given a network graph G=(V,E), and a capacity cap(v)∈ℕ for each node v∈V, the CapMDS problem asks for a subset S⊆V of minimal cardinality, such that every network node not in S is covered by at least one neighbor in S, and every node v∈S covers at most cap(v) of its neighbors. We prove that in general graphs and even with uniform capacities, the problem is inherently non-local, i.e., every distributed algorithm achieving a non-trivial approximation ratio must have a time complexity that essentially grows linearly with the network diameter. On the other hand, if for some parameter ε>0, capacities can be violated by a factor of 1+ε, CapMDS becomes much more local. Particularly, based on a novel distributed randomized rounding technique, we present a distributed bi-criteria algorithm that achieves an O(log Δ)-approximation in time O(log ³ n+log (n)/ε), where n and Δ denote the number of nodes and the maximal degree in G, respectively. Finally, we prove that in geometric network graphs typically arising in wireless settings, the uniform problem can be approximated within a constant factor in logarithmic time, whereas the non-uniform problem remains entirely non-local.     

A Local Facility Location Algorithm for Large-scale Distributed Systems

In a facility location problem (FLP) we are given a set of facilities and a set of clients, each of which is to be served by one facility. The goal is to decide which subset of facilities to open, such that the clients will be served at a minimal cost. In this paper we investigate the FLP in a setting where the cost depends on data known only to the clients. This setting typifies modern distributed systems: peer-to-peer file sharing networks, Grid systems, and wireless sensor networks. All of them need to perform network organization, data placement, collective power management, and other tasks of this kind. We propose a local and efficient algorithm that solves FLP in these settings. The algorithm presented here is extremely scalable, entirely decentralized, requires no routing capabilities, and is resilient to failures and changes in the data throughout its execution.     

Runtime support for scalable programming in Java

The paper research is concerned with enabling parallel, high-performance computation—in particular development of scientific software in the network-aware programming language, Java. Traditionally, this kind of computing was done in Fortran. Arguably, Fortran is becoming a marginalized language, with limited economic incentive for vendors to produce modern development environments, optimizing compilers for new hardware, or other kinds of associated software expected of by today’s programmers. Hence, Java looks like a very promising alternative for the future. The paper will discuss in detail a particular environment called HPJava. HPJava is the environment for parallel programming—especially data-parallel scientific programming—in Java. Our HPJava is based around a small set of language extensions designed to support parallel computation with distributed arrays, plus a set of communication libraries. A high-level communication API, Adlib, is developed as an application level communication library suitable for our HPJava. This communication library supports collective operations on distributed arrays. We include Java Object as one of the Adlib communication data types. So we fully support communication of intrinsic Java types, including primitive types, and Java object types.     

A multiagent framework for coordinated parallel problem solving

Today’s organizations, under increasing pressure on the effectiveness and the increasing need for dealing with complex tasks beyond a single individual’s capabilities, need technological support in managing complex tasks that involve highly distributed and heterogeneous information sources and several actors. This paper describes CoPSF, a multiagent system middle-ware that simplifies the development of coordinated problem solving applications while ensuring standard compliance through a set of system services and agents. CoPSF hosts and serves multiple concurrent teams of problem solving contributing both to the limitation of communication overheads and to the reduction of redundant work across teams and organizations. The framework employs (i) an interleaved task decomposition and allocation approach, (ii) a mechanism for coordination of agents’ work, and (iii) a mechanism that enables synergy between parallel teams.     

<Emphasis FontCategory="SansSerif">LRE</Emphasis>-<Emphasis FontCategory="SansSerif">TL</Emphasis>: an optimal multiprocessor algorithm for sporadic task sets with unconstrained deadlines

This article presents a detailed discussion of LRE-TL (Local Remaining Execution-TL-plane), an algorithm that schedules hard real-time periodic and sporadic task sets with unconstrained deadlines on identical multiprocessors. The algorithm builds upon important concepts such as the TL-plane construct used in the development of the LLREF algorithm (Largest Local Remaining Execution First). This article identifies the fundamental TL-plane scheduling principles used in the construction of LLREF . These simple principles are examined, identifying methods of simplifying the algorithm and allowing it to handle a more general task model. For example, we identify the principle that total local utilization can never increase within any TL-plane as long as a minimal number of tasks are executing. This observation leads to a straightforward approach for scheduling task arrivals within a TL-plane. In this manner LRE-TL can schedule sporadic tasks and tasks with unconstrained deadlines. Like LLREF, the LRE-TL scheduling algorithm is optimal for task sets with implicit deadlines. In addition, LRE-TL can schedule task sets with unconstrained deadlines provided they satisfy the density test for multiprocessor systems. While LLREF has a O(n ²) runtime per TL-plane, LRE-TL’s runtime is O(nlog n) per TL-plane.     

From insect to Internet: Situated control for networked robot teams

Ant-like systems take advantage of agents' situatedness to reduce or eliminate the need for centralized control or global knowledge. This reduces the need for complexity of individuals and leads to robust, scalable systems. Such insect-inspired situated approaches have proven effective both for task performance and task allocation. The desire for general, principled techniques for situated interaction has led us to study the exploitation of abstract situatedness – situatedness in non-physical environments. The port-arbitrated behavior-based control approach provides a well-structured abstract behavior space in which agents can participate in situated interaction. We focus on the problem of role assumption, distributed task allocation in which each agent selects its own task-performing role. This paper details our general, principled Broadcast of Local Eligibility (BLE) technique for role-assumption in such behavior-space-situated systems, and provides experimental results from the CMOMMT target-tracking task. This revised version was published online in August 2006 with corrections to the Cover Date.     

Increasing processor utilization in hard-real-time systems with checkpoints

Often hard real-time systems require results that are produced on time despite the occurrence of processor failures. This paper considers a distributed system where tasks are periodic and each task occurs in multiple copies which are periodically synchronized in order to handle failures. The problem of preemptively scheduling a set of such tasks is discussed where every occurrence of a task has to be completely executed before the next occurrence of the same task. First, a static scheduling algorithm is proposed which uses periodic checkpoints to tolerate processor failures. Then, the performance of the algorithm is substancially improved employing a mixed strategy which constructs a schedule where high frequency tasks are duplicated, and low frequency tasks are periodically checkpointed. The performance of the solution proposed is evaluated in terms of the minimum achievable processor utilization due to the useful computation of the tasks. Moreover, analytical and simulation studies are used to reveal interesting trade-offs associated with the scheduling algorithm. In particular, if high frequency tasks are less than 70 percent of the total number of tasks then the mixed strategy yields a higher processor utilization than the task duplication scheme.     

PIWA-LOC--一种Cluster环境下的大图像并行重采样算法

图像重采样问题应用广泛,具有计算复杂度高、运行时间长的特点．为了提高处理性能,针对Cluster并行环境,对一种并行几何校正算法进行改进,提出了并行重采样算法PIWA—LOC．采用一种新的存储结构用于保存各计算结点上的不规则输出子图像,并提出线段近似法用于获取不规则输出子图像的边界,使算法的通用性大大提高,适用于具有复杂几何变换的图像重采样问题．实验结果表明,该算法对大图像的重采样问题具有良好的并行性能,且网络带宽越高算法的可扩展性越好．     

Self-stabilizing smoothing and balancing networks

A smoothing network is a distributed data structure that accepts tokens on input wires and routes them to output wires. It ensures that however imbalanced the traffic on input wires, the numbers of tokens emitted on output wires are approximately balanced. Prior work on smoothing networks always assumed that such networks were properly initialized. In a real distributed system, however, network switches may be rebooted or replaced dynamically, and it may not be practical to determine the correct initial state for the new switch. Prior analyses do not work under these new assumptions. This paper makes the following contributions. First, we show that some well-known 1-smoothing networks, known as counting networks, when started in an arbitrary initial state (perhaps chosen by an adversary), remain remarkably smooth, degrading from 1-smooth to (log n)-smooth, where n is the number of input/output wires. For the networks that we consider, we show that the above (log n) bound for the smoothness is tight. Our second contribution is to show how any balancing network can be made self-stabilizing with the addition of local stabilization actions and state, which restore the network back to a “legal state” even if it starts out in an illegal state. A preliminary version of this work appeared in the Proceedings of The 23rd International Conference on Distributed Computing Systems, Providence, Rhode Island, USA.     

An Input/Output Semantics for Distributed Program Equivalence Reasoning

A new notion of input/output equivalence of distributed imperative programs, with synchronous communications, is introduced. It preserves the input/output relation, encompassing both, initial/final state and communication channel values. For its mathematical justification, the semantic framework of Manna and Pnueli, based on finite transition systems and reduced behaviors, is extended with the notion of input/output behavior. A set of laws for the equivalence is overviewed. A deduction rule for the substitution of references to input/output equivalent procedures is defined and justified in the new semantics. The rule is applied to decompose distributed program simplification proofs, introduced in a prior work, which use the laws to establish the equivalence between a sequential and a parallel communicating program. They include communication elimination as one of their steps. An outline of one of such proofs, for a pipelined processor model, is included.     

Group-Based Pfair Scheduling

We consider the problem of supertasking in Pfair-scheduled multiprocessor systems. In this approach, a set of tasks, called component tasks, is assigned to a server task, called a supertask, which is then scheduled as an ordinary Pfair task. Whenever a supertask is scheduled, its processor time is allocated to its component tasks according to an internal scheduling algorithm. Hence, supertasking is an example of hierarchal (or group-based) scheduling. In this paper, we present a generalized framework for “reweighting” supertasks. The goal of reweighting is to assign a fraction of a processor to a given supertask so that all timing requirements of its component tasks are met. We consider the use of both fully preemptive and quantum-based scheduling within a supertask. Work supported by NSF grants CCR 9732916, CCR 9972211, CCR 9988327, ITR 0082866, CCR 0204312, and CCR 0309825. Preliminary versions of some content appeared previously in (Holman and Anderson, 2001, 2003).