Monitoring Functions on Global States of Distributed Programs

The domain of a global function is the set of all global states of an execution of a distributed program. We show how to monitor a program in order to determine if there exists a global state in which the sumx₁+x₂+ \cdots +x_Nexceeds some constantK, wherex_iis defined in processi. We examine the cases wherex_iis an integer variable forN= 2 and wherex_iis a boolean variable for generalN. For both cases we provide algorithms, prove their correctness, and analyze their complexity.     

Understanding the Generalized Median Stable Matchings

Let I be a stable matching instance with N stable matchings. For each man m, order his (not necessarily distinct) N partners from his most preferred to his least preferred. Denote the ith woman in his sorted list as p _i (m). Let α _i consist of the man-woman pairs where each man m is matched to p _i (m). Teo and Sethuraman proved this surprising result: for i=1 to N, not only is α _i a matching, it is also stable. The α _i ’s are called the generalized median stable matchings of I. Determining if these stable matchings can be computed efficiently is an open problem.     

Heterogeneous-criteria scheduling: Minimizing weighted number of tardy jobs and weighted completion time

In this paper, a novel O(N²) algorithm is presented to minimize the weighted number of tardy jobs with unit processing times, integer ready times and deadlines, and M homogeneous parallel machines, where N is the number of jobs to be scheduled. w_i is the weight reflecting job i's importance, and U_i is 1 if job i is tardy and 0 otherwise, so Σw_iU_i is the measure of performance. (In standard notation, this is the P/r_i, p_i = 1/Σw_iU_i problem.) This algorithm is extended to minimize weighted completion time Σw_iC_i for some jobs, where completion time C_i is the time job i completes processing, and Σw_iU_i for other jobs, at the same complexity. (The P/r_i, p_i = 1/Σw_iU_i & Σw_iC_i problem.) Complexity can be reduced to O(N log N) if all ready times are the same (with one additional constraint on weights). (P/p_i = 1/Σw_iU_i & Σw_iC_i.) Finally, if one is trying to find the number of tardy jobs of each weight under optimal scheduling, but an actual schedule is not needed, this (P/r_i, p_i = 1/Σw_iU_i) problem can be solved with an O(WN log N) algorithm, where W is the number of different weight values. In some cases, this can be done analytically.     

The Traveling Agent Problem

 This paper considers a sequencing problem which arises naturally in the scheduling of software agents. We are given n sites at which a certain task might be successfully performed. The probability of success is p _i at the ith site and these probabilities are independent. Visiting site i and trying the task there requires time (or some other cost metric) t _i whether successful or not. Latencies between sites i and j are l _ij, that is, the travel time between those two sites. Should the task be successfully completed at a site then any remaining sites do not need to be visited. The Traveling Agent Problem is to find the sequence which minimizes the expected time to complete the task. The general formulation of this problem is NP-Complete. However, if the latencies are constant we show that the problem can be solved in polynomial time by sorting the ratios t _i/p _i according to increasing value and visiting the sites in that order. This result then leads to an efficient algorithm when groups of sites form subnets in which latencies within a subnet are constant but can vary across subnets. We also study the case when there are deadlines for solving the problem in which case the goal is to maximize probability of success subject to satisfying the deadlines. Applications to mobile and intelligent agents are described. Date received: February 10, 1998. Date revised: November 16, 1999.     

Relocation problems of maximizing new capacities under a common due date

Given a set of h buildings to be torn down and rebuilt, each building B_i , demands n_i units of temporary vacancies for reconstruction (i.e. the reconstruction of B_i can be started only if there are at least n_i temporary vacancies available) and returns a_i units of vacancies when it is rebuilt. The reconstruction time of each building is assumed to be unitary. Under the initial provision of V _o units of vacancies and a specified due date d, Σ_BiεSa _i , where S is a feasible sequence such that |S| ≤ d, is the objective function to be maximized. We show that the problem is NP-complete. Based on a dominance heuristics, we further propose a branch-and-bound algorithm. Experimental results are included to elucidate the effectiveness of our algorithm. Two further restricted versions are also polynomially solvable.     

Parallel solution of recurrences on a tree machine

The recurrencex _o =a _o x _i =a _i+b _i x _i–1,i = 1, 2,...,n–1 requiresO(n) operations on a sequential computer. Elegant parallel solutions exist, however, that reduce the complexity toO(logN) usingNn processors. This paper discusses one such solution, designed for a tree-structured network of processors.A tree structure is ideal for solving recurrences. It takes exactly one sweep up and down the tree to solve any of several classes of recurrences, thus guaranteeing a solution inO(logN) time for a tree withNn leaf nodes. Ifn exceedsN, the algorithm efficiently pipelines the operation and solves the recurrence inO(n/N + logN) time.     

Blocking analysis of transaction processing queues

A transaction processing queue manages a database which is partitioned into N items. Each arriving class-i customer requests to read and write a certain subset of the N items (called the shared and exclusive access sets and ). Classes i and j are said to conflict if

Full-size image

. No two conflicting classes of customers can be processed simultaneously. All classes arrive according to independent Poisson processes and have general i.i.d. service times.In this paper, we discuss database systems without queuing. We show the insensitivity property of the system, and derive analytical expressions for performance measures such as blocking probabilities, throughput, etc.     

On a generalized k-out-of-n system and its reliability

A consecutive-k-out-of-n system is a system with n components arranged either linearly or circularly, which fails if and only if at least k consecutive components fail. An (n,?f,?k) system further requires that the total number of failed components is less than f for the system to be working. Here we consider a more general system consisting of N modules with the ith module-composed of n _i components in parallel; the system fails if and only if there exist at least f failed components or at least k consecutive failed modules. In this paper, some formulae for the reliability of such a generalized k-out-of-n system are derived for both the linear and the circular cases. The recursive formulae established here can be easily computed. Many existing results are also shown to be special cases of the results obtained in this paper. Furthermore, we investigate some component importance properties.     

A novel approach for analyzing dynamics in neural networks with saturated characteristics

Current theories about the dynamics of neural networks with nonlinear characteristics and parameterized by set of parameters are mostly based on approximations in one way or another. In this paper we first introduce a rigorous approach which allows us to check in which parameter region a given saturated state is an attractor of the dynamics: a saturated state w=(w _i , i=1,...,N){-1,1} ^N is an attractor of the dynamics if and only if there is a local field gap between neurons in J ⁺ (w)={i, w _i =1} and J ^- (w)={i, w _i =–1}. Then we apply the result to analyze several models in neural networks. In particular in the Hopfield model we calculate the capacity and give an exact relation between the capacity and the threshold.     

Cybernetics of Taxation: The Optimization of Economic Participation

One of the primary problems in statistical mechanics is to find in a system of a large number of freely interacting elements (particles) the distribution of the available energy over all elements which will be observed in most of the cases when the number of elements N₁ are counted which possess energies that fall within an “energy-bracket” E_i ± ½δ of width δE ; (i = 1, 2, 3, …). In a conservative system in which the number of elements, N, and the available energy, E, are given and remain unchanged, the most probable distribution is, of course, Boltzmann's distribution function which maximizes the entropy of the system and has the form of a decaying exponential N_i = N_o exp(-E_i/E*), in which E*, a universal parameter for this system, is the average energy per particle, and expresses through the Boltzmann's constant k (1.378 ergs/centigrade) the “temperature” T of the system T = E*/k.     

A two-stage approach in solving the state probabilities of the multi-queue M/G/1 model

The M/G/1 model is the fundamental basis of the queueing system in many network systems. Usually, the study of the M/G/1 is limited by the assumption of single queue and infinite capacity. In practice, however, these postulations may not be valid, particularly when dealing with many real-world problems. In this paper, a two-stage state-space approach is devoted to solving the state probabilities for the multi-queue finite-capacity M/G/1 model, i.e. q-M/G/1/K_i with K_i buffers in the ith queue. The state probabilities at departure instants are determined by solving a set of state transition equations. Afterward, an embedded Markov chain analysis is applied to derive the state probabilities with another set of state balance equations at arbitrary time instants. The closed forms of the state probabilities are also presented with theorems for reference. Applications of Little's theorem further present the corresponding results for queue lengths and average waiting times. Simulation experiments have demonstrated the correctness of the proposed approaches.     

Hybrid curve fitting

We consider a parameterized family of closed planar curves and introduce an evolution process for identifying a member of the family that approximates a given unorganized point cloud {p _i } _{i =1,..., N} . The evolution is driven by the normal velocities at the closest (or foot) points (f _i ) to the data points, which are found by approximating the corresponding difference vectors p _i -f _i in the least-squares sense. In the particular case of parametrically defined curves, this process is shown to be equivalent to normal (or tangent) distance minimization, see [3], [19]. Moreover, it can be generalized to very general representations of curves. These include hybrid curves, which are a collection of parametrically and implicitly defined curve segments, pieced together with certain degrees of geometric continuity.     

Optimal testing policy for a computer system with fault margin

The periodic testing policy is considered, for a computer system which fails when the total number of hidden faults exceeds a threshold level N of tolerence. Periodic tests are scheduled at times kT(k = 1,2,[tdot]) to detect hidden faults. A fault occurs according to a non-homogeneous Poisson processes. When the ith fault occurs at age S_i < T, (i) it causes a system failure with probability p₁(S_i), (ii) it becomes a hidden fault with probability p₂(S_i) and is accumulated, or (iii) it is removed with probability p₃(S_i). The expected cost rate is derived. The aim of the paper is to find the optimal T which minimizes the expected cost rate per unit time of the policy. Various special cases are considered.     

Performance Bounds of Algorithms for Scheduling Advertisements on a Web Page

Consider a set of n advertisements (hereafter called ads) A ={A₁,...,A_n} competing to be placed in a planning horizon which is divided into N time intervals called slots. An ad A _i is specified by its size s _i and frequency w _i. The size s _i represents the amount of space the ad occupies in a slot. Ad A _i is said to be scheduled if exactly w _i copies of A _i are placed in the slots subject to the restriction that a slot contains at most one copy of an ad. In this paper, we consider two problems. The MINSPACE problem minimizes the maximum fullness among all slots in a feasible schedule where the fullness of a slot is the sum of the sizes of ads assigned to the slot. For the MAXSPACE problem, in addition, we are given a common maximum fullness S for all slots. The total size of the ads placed in a slot cannot exceed S. The objective is to find a feasible schedule of ads such that the total occupied slot space is maximized. We examine the complexity status of both problems and provide heuristics with performance guarantees.     

An Equational Axiomatization for Multi-exit Iteration

This paper presents an equational axiomatization of bisimulation equivalence over the language of Basic Process Algebra (BPA) with multi-exit iteration. Multi-exit iteration is a generalization of the standard binary Kleene star operation that allows for the specification of agents that, up to bisimulation equivalence, are solutions of systems of recursion equations of the form wherenis a positive integer and theP_iand theQ_iare process terms. The addition of multi-exit iteration to BPA yields a more expressive language than that obtained by augmenting BPA with the standard binary Kleene star (BPA*). As a consequence, the proof of completeness of the proposed equational axiomatization for this language, although standard in its general structure, is much more involved than that for BPA*. An expressiveness hierarchy for the family ofk-exit iteration operators proposed by Bergstra, Bethke, and Ponse is also offered.     

Utilization Based Schedulability Bounds for Age Constraint Process Sets in Real-Time Systems

Some real-time systems consist of a number of processes that operate under age constraints. In such systems, the maximum time from the start of process L _i in cycle k to the end in cycle k+1 must not exceed the age constraint A _i for that process. The age constraint can be met by using fixed priority scheduling and periods equal to A _i/2. However, this approach restricts the number of process sets which are schedulable. In this paper, we define a method for obtaining process periods other than A _i/2. The periods are calculated in such a way that the age constraints are met. Our approach is better in the sense that a larger number of process sets can be scheduled compared to using periods equal to A _i/2. The main results in this paper are a number of performance bounds on age constraint processes. These bounds show that there is a significant gain in worst case as well as in best case behavior by using periods other than A _i/2, particularly when there are a large number of processes in the system.     

Numerical simulation of cloud droplet formation in a tank

Using the computational fluid dynamics (CFD) code FLUENT 6 together with the fine particle model (FPM), numerical simulations of droplet dynamics in a 12.4 m³ cloud tank were conducted. The coupled fields of water vapor, temperature, flow velocity, particle number concentration, and particle mass concentration inside the cloud tank were computed.The system responses to changes of the wall's temperature and mass fraction of water vapor, respectively, were investigated. Typical times for mixing the cloud tank's contents are in the range of some tens of seconds. The maximum volume-averaged deviations from the mean of temperature and mass fraction of water vapor are around 5% of the respective parameter changes applied to the wall.Time-dependent simulations were performed in order to study the growth of ammonium-sulfate particles in humid air at around room temperature. Supersaturation up to (S_w–1)=8.2×10⁻³ was achieved by the expansion of the gas. The particles were activated and grew rapidly to a maximum diameter of 5.2×10⁻⁶ m after critical supersaturation was reached. After S_w fell again below the equilibrium value, the particles shrank quickly and deactivated roughly 60 s after activation.The spatial inhomogeneities of temperature and water-vapor concentration cause volume-averaged deviations of the particle number N and diameter d_g of up to 2.3% and 36%, respectively.     

Transversal of disjoint convex polygons

Given a set S of n disjoint convex polygons {P_i∣1?i?n} in a plane, each with k_i vertices, the transversal problem is to find, if there exists one, a straight line that goes through every polygon in S. We show that the transversal problem can be solved in O(N+nlogn) time, where N=∑_i=1ⁿk_i is the total number of vertices of the polygons.     

The complexity of preemptive scheduling given interprocessor communication delays

We discuss the problem of scheduling af set of independent tasks T, each t_i ϵ T of lenght ℓ_i ϵ Z⁺, on m identical processors. We allow preemption but assume a communication delay of time k ϵ N. Whenever a task is preempted from one processor to another, there must be a delay of at least k time units. We show that if k = 1, an optimal schedule can be found in polynomial time but if k ⩾ 2, the corresponding decision problem is NP-complete.     

Correlation between soil apparent electroconductivity and plant hyperspectral reflectance in a managed wetland

The apparent electrical conductivity (σ_a) of soil is influenced by a complex combination of soil physical and chemical properties. For this reason, σ_a is proposed as an indicator of plant stress and potential community structure changes in an alkaline wetland setting. However, assessing soil σ_a is relatively laborious and difficult to accomplish over large wetland areas. This work examines the feasibility of using the hyperspectral reflectance of the vegetation canopy to characterize the σ_a of the underlying substrate in a study conducted in a Central California managed wetland. σ_a determined by electromagnetic (EM) inductance was tested for correlation with in-situ hyperspectral reflectance measurements, focusing on a key waterfowl forage species, swamp timothy (Crypsis schoenoides). Three typical hyperspectral indices, individual narrow-band reflectance, first-derivative reflectance and a narrow-band normalized difference spectral index (NDSI), were developed and related to soil σ_a using univariate regression models. The coefficient of determination (R ²) was used to determine optimal models for predicting σ_a, with the highest value of R ² at 2206 nm for the individual narrow bands (R ²?=?0.56), 462 nm for the first-derivative reflectance (R ²?=?0.59), and 1549 and 2205 nm for the narrow-band NDSI (R ²?=?0.57). The root mean squared error (RMSE) and relative root mean squared error (RRMSE) were computed using leave-one-out cross-validation (LOOCV) for accuracy assessment. The results demonstrate that the three indices tested are valid for estimating σ_a, with the first-derivative reflectance performing better (RMSE?=?30.3 mS m^?1, RRMSE?=?16.1%) than the individual narrow-band reflectance (RMSE?=?32.3 mS m^?1, RRMSE?=?17.1%) and the narrow-band NDSI (RMSE?=?31.5 mS m^?1, RRMSE?=?16.7%). The results presented in this paper demonstrate the feasibility of linking plant–soil σ_a interactions using hyperspectral indices based on in-situ spectral measurements.