An $\mathsf{EDF}$ -based restricted-migration scheduling algorithm for multiprocessor soft real-time systems

There has been much recent interest in the use of the earliest-deadline-first ( ) algorithm for scheduling soft real-time sporadic task systems on identical multiprocessors. In hard real-time systems, a significant disparity exists between -based schemes and Pfair scheduling: on M processors, the worst-case schedulable utilization for all known variants is approximately M/2, whereas it is M for optimal Pfair algorithms. This is unfortunate because -based algorithms entail lower scheduling and task-migration overheads. However, such a disparity in schedulability can be alleviated by easing the requirement that all deadlines be met, which may be sufficient for soft real-time systems. In particular, in recent work, we have shown that if task migrations are not restricted, then (i.e. , global ) can ensure bounded tardiness for a sporadic task system with no restrictions on total utilization. Unrestricted task migrations in global may be unappealing for some systems, but if migrations are forbidden entirely, then bounded tardiness cannot be guaranteed. In this paper, we address the issue of striking a balance between task migrations and system utilization by proposing an algorithm called , which is based upon and treads a middle path, by restricting, but not eliminating, task migrations. Specifically, under , the ability to migrate is required for at most M−1 tasks, and it is sufficient that every such task migrate between two processors and at job boundaries only. , like global , can ensure bounded tardiness to a sporadic task system as long as the available processing capacity is not exceeded, but, unlike global , may require that per-task utilizations be capped. The required cap is quite liberal, hence, should enable a wide range of soft real-time applications to be scheduled with no constraints on total utilization.

Two Algorithms in Search of a Type-System

The authors’ programming formalism is a version of call-by-value under a complexity-theoretically motivated type system. programs run in type-2 polynomial-time and all standard type-2 basic feasible functionals are -definable ( types are confined to levels 0, 1, and 2). A limitation of the original version of is that the only directly expressible recursions are tail-recursions. Here we extend so that a broad range of affine recursions are directly expressible. In particular, the revised can fairly naturally express the classic insertion- and selection-sort algorithms, thus overcoming a sticking point of most prior implicit-complexity-based formalisms. The paper’s main work is in refining the original time-complexity semantics for to show that these new recursion schemes do not lead out of the realm of feasibility.     

Feasible Operations on Proofs: The Logic of Proofs for Bounded Arithmetic

This paper presents a semantics for the logic of proofs in which all the operations on proofs are realized by feasibly computable functions. More precisely, we will show that the completeness of for the semantics of proofs of Peano Arithmetic extends to the semantics of proofs in Buss’ bounded arithmetic . In view of applications in epistemology of in particular and justification logics in general this result shows that explicit knowledge in the propositional framework can be made computationally feasible. This research supported by CUNY Community College Collaborative Incentive Research Grant 91639-0001 “Mathematical Foundations of Knowledge Representation”.     

Probabilistic Length-Reducing Two-Pushdown Automata

Hardness of a separation of nondeterminism, randomization and determinism for polynomial time computations has motivated the analysis of this issue for restricted models of computation. Following this line of research, we consider randomized length-reducing two-pushdown automata ( ), a natural extension of pushdown automata ( ). Our main results are as follows. We show that deterministic s are weaker than Las Vegas s which in turn are weaker than Monte Carlo s. Moreover, bounded two-sided error s are stronger than Monte Carlo s and they are able to recognize some languages which cannot be recognized nondeterministically. Finally, we prove that amplification is impossible for Las Vegas and Monte Carlo automata. Partially supported by MNiSW grant number N206 024 31/3826, 2006-2008. An extended abstract of this paper appeared in the MFCS06 Proceedings (Lecture Notes in Computer Science, vol. 4162, pp. 561–572, 2006).     

On the Complexity of 2-Monotone Restarting Automata

The -automaton is the weakest form of the nondeterministic version of the restarting automaton that was introduced by Jančar et al. to model the so-called analysis by reduction. Here it is shown that the class ℒ(R) of languages that are accepted by -automata is incomparable under set inclusion to the class of Church-Rosser languages and to the class of growing context-sensitive languages. In fact this already holds for the class of languages that are accepted by 2-monotone -automata. In addition, we prove that already the latter class contains -complete languages, showing that already the 2-monotone -automaton has a surprisingly large expressive power. The results of this paper have been announced at DLT 2004 in Auckland, New Zealand. This work was mainly carried out while T. Jurdziński was visiting the University of Kassel, supported by a grant from the Deutsche Forschungsgemeinschaft (DFG). F. Mráz and M. Plátek were partially supported by the Grant Agency of the Czech Republic under Grant-No. 201/04/2102 and by the program ‘Information Society’ under project 1ET100300517. F. Mráz was also supported by the Grant Agency of Charles University in Prague under Grant-No. 358/2006/A-INF/MFF.     

Planar and Grid Graph Reachability Problems

We study the complexity of restricted versions of s-t-connectivity, which is the standard complete problem for . In particular, we focus on different classes of planar graphs, of which grid graphs are an important special case. Our main results are:

Semi on-line scheduling on three processors with known sum of the tasks

We consider a semi on-line version of the multiprocessor scheduling problem on three processors, where the total size of the tasks is known in advance. We prove a lower bound on the competitive ratio of any algorithm and propose a simple algorithm with competitive ratio equal to 1.5. The performance is improved to by a preprocessing strategy. The latter algorithm is only 2% away from the lower bound. Z. Tuza is supported in part by the Hungarian Scientific Research Fund, OTKA grant T-049613.     

Tuples of Disjoint $\mathsf{NP}$ -Sets

Disjoint -pairs are a well studied complexity-theoretic concept with important applications in cryptography and propositional proof complexity. In this paper we introduce a natural generalization of the notion of disjoint -pairs to disjoint k-tuples of -sets for k≥2. We define subclasses of the class of all disjoint k-tuples of -sets. These subclasses are associated with a propositional proof system and possess complete tuples which are defined from the proof system. In our main result we show that complete disjoint -pairs exist if and only if complete disjoint k-tuples of -sets exist for all k≥2. Further, this is equivalent to the existence of a propositional proof system in which the disjointness of all k-tuples is shortly provable. We also show that a strengthening of this conditions characterizes the existence of optimal proof systems. An extended abstract of this paper appeared in the proceedings of the conference CSR 2006 (Lecture Notes in Computer Science 3967, 80–91, 2006). Supported by DFG grant KO 1053/5-1.     

Characterizing Programming Systems Allowing Program Self-Reference

The interest is in characterizing insightfully the power of program self-reference in effective programming systems ( ), the computability-theoretic analogs of programming languages (for the partial computable functions). In an in which the constructive form of Kleene’s Recursion Theorem (KRT) holds, it is possible to construct, algorithmically, from an arbitrary algorithmic task, a self-referential program that, in a sense, creates a self-copy and then performs that task on the self-copy. In an in which the not-necessarily-constructive form of Kleene’s Recursion Theorem (krt) holds, such self-referential programs exist, but cannot, in general, be found algorithmically. In an earlier effort, Royer proved that there is no collection of recursive denotational control structures whose implementability characterizes the in which KRT holds. One main result herein, proven by a finite injury priority argument, is that the in which krt holds are, similarly, not characterized by the implementability of some collection of recursive denotational control structures. On the positive side, however, a characterization of such of a rather different sort is shown herein. Though, perhaps not the insightful characterization sought after, this surprising result reveals that a hidden and inherent constructivity is always present in krt. This paper is an expanded version of [6]. This paper received support from NSF Grant CCR-0208616. “Know thyself.” Greek proverb     

Scheduling with conflicts: online and offline algorithms

We consider the following problem of scheduling with conflicts (swc): Find a minimum makespan schedule on identical machines where conflicting jobs cannot be scheduled concurrently. We study the problem when conflicts between jobs are modeled by general graphs. Our first main positive result is an exact algorithm for two machines and job sizes in {1,2}. For jobs sizes in {1,2,3}, we can obtain a -approximation, which improves on the -approximation that was previously known for this case. Our main negative result is that for jobs sizes in {1,2,3,4}, the problem is APX-hard. Our second contribution is the initiation of the study of an online model for swc, where we present the first results in this model. Specifically, we prove a lower bound of on the competitive ratio of any deterministic online algorithm for m machines and unit jobs, and an upper bound of 2 when the algorithm is not restricted computationally. For three machines we can show that an efficient greedy algorithm achieves this bound. For two machines we present a more complex algorithm that achieves a competitive ratio of when the number of jobs is known in advance to the algorithm.     

Competitive Analysis of Scheduling Algorithms for Aggregated Links

We study an online job scheduling problem arising in networks with aggregated links. The goal is to schedule n jobs, divided into k disjoint chains, on m identical machines, without preemption, so that the jobs within each chain complete in the order of release times and the maximum flow time is minimized. We present a deterministic online algorithm with competitive ratio , and show a matching lower bound, even for randomized algorithms. The performance bound for we derive in the paper is, in fact, more subtle than a standard competitive ratio bound, and it shows that in overload conditions (when many jobs are released in a short amount of time), ’s performance is close to the optimum. We also show how to compute an offline solution efficiently for k=1, and that minimizing the maximum flow time for k,m≥2 is -hard. As by-products of our method, we obtain two offline polynomial-time algorithms for minimizing makespan: an optimal algorithm for k=1, and a 2-approximation algorithm for any k. W. Jawor and M. Chrobak supported by NSF grants OISE-0340752 and CCR-0208856. Work of C. Dürr conducted while being affiliated with the Laboratoire de Recherche en Informatique, Université Paris-Sud, 91405 Orsay. Supported by the CNRS/NSF grant 17171 and ANR Alpage.     

A schedulable utilization bound for the multiprocessor \mathsf{EPDF} Pfair algorithm

The earliest-pseudo-deadline-first ( ) Pfair scheduling algorithm is less expensive than some other known Pfair algorithms, but is not optimal for scheduling recurrent real-time tasks on more than two processors. In prior work, sufficient per-task weight (i.e., utilization) restrictions were established for ensuring that tasks either do not miss their deadlines or have bounded tardiness when scheduled under . Implicit in these restrictions is the assumption that the total system utilization may equal the total available processing capacity (i.e., the total number of processors). This paper considers an orthogonal issue, namely, determining a sufficient restriction on the total utilization of a task set for it to be schedulable (i.e., a schedulable utilization bound) under , assuming that there are no per-task weight restrictions. We prove that a task set with total utilization at most is correctly scheduled under on M processors, regardless of how large each task’s weight is. At present, we do not know whether this value represents the worst-case for , but we do provide a counterexample that shows that it cannot be improved to exceed 86% of the total processing capacity. The schedulable utilization bound we derive is expressed in terms of the maximum weight of any task, and hence, if this value is known, may be used to schedule task sets with total utilization greater than .

Approximately Fair Cost Allocation in Metric Traveling Salesman Games

A traveling salesman game is a cooperative game . Here N, the set of players, is the set of cities (or the vertices of the complete graph) and c _D is the characteristic function where D is the underlying cost matrix. For all S⊆N, define c _D (S) to be the cost of a minimum cost Hamiltonian tour through the vertices of S∪{0} where is called as the home city. Define Core as the core of a traveling salesman game . Okamoto (Discrete Appl. Math. 138:349–369, [2004]) conjectured that for the traveling salesman game with D satisfying triangle inequality, the problem of testing whether Core is empty or not is -hard. We prove that this conjecture is true. This result directly implies the -hardness for the general case when D is asymmetric. We also study approximately fair cost allocations for these games. For this, we introduce the cycle cover games and show that the core of a cycle cover game is non-empty by finding a fair cost allocation vector in polynomial time. For a traveling salesman game, let and ∀ S⊆N, x(S)≤ε⋅c _D (S)} be an ε-approximate core, for a given ε>1. By viewing an approximate fair cost allocation vector for this game as a sum of exact fair cost allocation vectors of several related cycle cover games, we provide a polynomial time algorithm demonstrating the non-emptiness of the log ₂(|N|−1)-approximate core by exhibiting a vector in this approximate core for the asymmetric traveling salesman game. We improve it further by finding a -approximate core in polynomial time for some constant c. We also show that there exists an ε ₀>1 such that it is -hard to decide whether ε ₀-Core is empty or not. A preliminary version of the paper appeared in the third Workshop on Approximation and Online Algorithms (WAOA), 2005.     

Adaptive Energy Management for Incremental Deployment of Heterogeneous Wireless Sensors

We introduce a new modelling assumption for wireless sensor networks, that of node redeployment (addition of sensor devices during protocol evolution) and we extend the modelling assumption of heterogeneity (having sensor devices of various types). These two features further increase the highly dynamic nature of such networks and adaptation becomes a powerful technique for protocol design. Under these modelling assumptions, we design, implement and evaluate a new power conservation scheme for efficient data propagation. Our scheme is adaptive: it locally monitors the network conditions (density, energy) and accordingly adjusts the sleep-awake schedules of the nodes towards improved operation choices. The scheme is simple, distributed and does not require exchange of control messages between nodes. Implementing our protocol in software we combine it with two well-known data propagation protocols and evaluate the achieved performance through a detailed simulation study using our extended version of the network simulator ns-2. We focus on highly dynamic scenarios with respect to network density, traffic conditions and sensor node resources. We propose a new general and parameterized metric capturing the trade-offs between delivery rate, energy efficiency and latency. The simulation findings demonstrate significant gains (such as more than doubling the success rate of the well-known propagation protocol) and good trade-offs achieved. Furthermore, the redeployment of additional sensors during network evolution and/or the heterogeneous deployment of sensors, drastically improve (when compared to “equal total power” simultaneous deployment of identical sensors at the start) the protocol performance (i.e. the success rate increases up to four times while reducing energy dissipation and, interestingly, keeping latency low). This work has been partially supported by the IST Programme of the European Union under contract number IST-2005-15964 ( ), the Programme under the European Social Fund (ESF) and Operational Program for Educational and Vocational Training II (EPEAEK II) and the Programme of GSRT under contract number 03ED568. A preliminary version of this work has appeared in [13].     

On “Exploiting” Node-Heterogeneous Clusters Optimally

It is proved that “FIFO” worksharing protocols provide asymptotically optimal solutions to two problems related to sharing large collections of independent tasks in a heterogeneous network of workstations (HNOW) . In the , one seeks to accomplish as much work as possible on during a prespecified fixed period of L time units. In the , one seeks to complete W units of work by “renting” for as short a time as necessary. The worksharing protocols we study are crafted within an architectural model that characterizes via parameters that measure ’s workstations’ computational and communicational powers. All valid protocols are self-scheduling, in the sense that they determine completely both an amount of work to allocate to each of ’s workstations and a schedule for all related interworkstation communications. The schedules provide either a value for W given L, or a value for L given W, hence solve both of the motivating problems. A protocol observes a FIFO regimen if it has ’s workstations finish their assigned work, and return their results, in the same order in which they are supplied with their workloads. The proven optimality of FIFO protocols resides in the fact that they accomplish at least as much work as any other protocol during all sufficiently long worksharing episodes, and that they complete sufficiently large given collections of tasks at least as fast as any other protocol. Simulation experiments illustrate that the superiority of FIFO protocols is often observed during worksharing episodes of only a few minutes’ duration. A portion of this research was presented at the 15th ACM Symp. on Parallelism in Algorithms and Architectures (2003).     

Solve-and-robustify

Goal separation is often a fruitful approach when solving complex problems. It provides a way to focus on relevant aspects in a stepwise fashion and hence bound the problem solving scope along a specific direction at any point. This work applies goal separation to the problem of synthesizing robust schedules. The problem is addressed by separating the phase of problem solution, which may pursue a standard optimization criterion (e.g., minimal makespan), from a subsequent phase of solution robustification in which a more flexible set of solutions is obtained and compactly represented through a temporal graph, called a Partial Order Schedule ( ). The key advantage of a is that it provides the capability to promptly respond to temporal changes (e.g., activity duration changes or activity start-time delays) and to hedge against further changes (e.g., new activities to perform or unexpected variations in resource capacity). On the one hand, the paper focuses on specific heuristic algorithms for synthesis of s, starting from a pre-existing schedule (hence the name Solve-and-Robustify). Different extensions of a technique called chaining, which progressively introduces temporal flexibility into the representation of the solution, are introduced and evaluated. These extensions follow from the fact that in multi-capacitated resource settings more than one can be derived from a specific fixed-times solution via chaining, and carry out a search for the most robust alternative. On the other hand, an additional analysis is performed to investigate the performance gain possible by further broadening the search process to consider multiple initial seed solutions. A detailed experimental analysis using state-of-the-art rcpsp/max  benchmarks is carried out to demonstrate the performance advantage of these more sophisticated solve and robustify procedures, corroborating prior results obtained on smaller problems and also indicating how this leverage increases as problem size is increased.     

On the complexity of binary samples

Consider a class of binary functions h: X→{ − 1, + 1} on an interval . Define the sample width of h on a finite subset (a sample) S ⊂ X as ω _S (h) =  min _x ∈ S |ω _h (x)| where ω _h (x) = h(x) max {a ≥ 0: h(z) = h(x), x − a ≤ z ≤ x + a}. Let be the space of all samples in X of cardinality ℓ and consider sets of wide samples, i.e., hypersets which are defined as Through an application of the Sauer-Shelah result on the density of sets an upper estimate is obtained on the growth function (or trace) of the class , β > 0, i.e., on the number of possible dichotomies obtained by intersecting all hypersets with a fixed collection of samples of cardinality m. The estimate is .      

Tardiness bounds under global EDF scheduling on a multiprocessor

We consider the scheduling of a sporadic real-time task system on an identical multiprocessor. Though Pfair algorithms are theoretically optimal for such task systems, in practice, their runtime overheads can significantly reduce the amount of useful work that is accomplished. On the other hand, if all deadlines need to be met, then every known non-Pfair algorithm requires restrictions on total system utilization that can approach approximately 50% of the available processing capacity. This may be overkill for soft real-time systems, which can tolerate occasional or bounded deadline misses (i.e. bounded tardiness). In this paper we derive tardiness bounds under preemptive and non-preemptive global when the total system utilization is not restricted, except that it not exceed the available processing capacity. Hence, processor utilization can be improved for soft real-time systems on multiprocessors. Our tardiness bounds depend on the total system utilization and per-task utilizations and execution costs—the lower these values, the lower the tardiness bounds. As a final remark, we note that global may be superior to partitioned for multiprocessor-based soft real-time systems in that the latter does not offer any scope to improve system utilization even if bounded tardiness can be tolerated.

On-line scheduling on an unbounded parallel batch machine to minimize makespan of two families of jobs

We study the on-line scheduling on an unbounded parallel batch machine to minimize makespan of two families of jobs. In this model, jobs arrive over time and jobs from different families cannot be scheduled in a common batch. We provide a best possible on-line algorithm for the problem with competitive ratio . Research supported by NSFC (10671183), NFSC-RGC (70731160633) and SRFDP (20070459002).     

Motion Planning for Haptic Guidance

Haptic devices allow a user to feel either reaction forces from virtual interactions or reaction forces reflected from a remote site during a bilateral teleoperation task. Also, guiding forces can be exerted to train the user in the performance of a virtual task or to assist him/her to safely teleoperate a robot. The generation of guiding forces relies on the existence of a motion plan that provides the direction to be followed to reach the goal from any free configuration of the configuration space (-space). This paper proposes a method to obtain such a plan that interleaves a sampling-based exploration of -space with an efficient computation of harmonic functions. A deterministic sampling sequence (with a bias based on harmonic function values) is used to obtain a hierarchical cell decomposition model of -space. A harmonic function is iteratively computed over the partially known model using a novel approach. The harmonic function is the navigation function used as motion plan. The approach has been implemented in a planner (called the Kautham planner) that, given an initial and a goal configuration, provides: (a) a channel of cells connecting the cell that contains the initial configuration with the cell that contains the goal configuration; (b) two harmonic functions over the whole -space, one that guides motions towards the channel and another that guides motions within the channel towards the goal; and (c) a path computed over a roadmap built with the free samples of the channel. The harmonic functions and the solution path are then used to generate the guiding forces for the haptic device. The planning approach is illustrated with examples on 2D and 3D workspaces. This work was partially supported by the CICYT projects DPI2005-00112 and DPI2007-63665.