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.

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).     

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).     

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.     

Strong non-standard completeness for fuzzy logics

In this paper we are going to introduce the notion of strong non-standard completeness (SNSC) for fuzzy logics. This notion naturally arises from the well known construction by ultraproduct. Roughly speaking, to say that a logic is strong non-standard complete means that, for any countable theory Γ over and any formula φ such that , there exists an evaluation e of -formulas into a -algebra such that the universe of is a non-Archimedean extension of the real unit interval [0,1], e is a model for Γ, but e(φ) < 1. Then we will apply SNSC to prove that various modal fuzzy logics allowing to deal with simple and conditional probability of infinite-valued events are complete with respect to classes of models defined starting from non-standard measures, that is measures taking value in .     

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.     

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”.     

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.     

On the impact of objective function transformations on evolutionary and black-box algorithms

Different objective functions characterize different problems. However, certain fitness transformations can lead to easier problems although they are still a model of the considered problem. In this article, the class of not worsening transformations for a simple population-based evolutionary algorithm (EA) is described completely. That is the class of functions that transfers easy problems in easy ones and difficult problems in difficult ones. Surprisingly, this class for the rank-based EA equals that for all black-box algorithms. The importance of the black-box algorithms' knowledge of the transformation is also pointed out. Hence, a comparison with the class of not worsening transformations for a similar EA which applies fitness-proportional selection, shows that is a proper superset of . Moreover, is a proper subset of the corresponding class for random search. Finally, the minimal and maximal classes of not worsening transformations are described completely, too.     

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.     

Improving the lazy Krivine machine

Krivine presents the  machine, which produces weak head normal form results. Sestoft introduces several call-by-need variants of the  machine that implement result sharing via pushing update markers on the stack in a way similar to the TIM and the STG machine. When a sequence of consecutive markers appears on the stack, all but the first cause redundant updates. Improvements related to these sequences have dealt with either the consumption of the markers or the removal of the markers once they appear. Here we present an improvement that eliminates the production of marker sequences of length greater than one. This improvement results in the  machine, a more space and time efficient variant of . We then apply the classic optimization of short-circuiting operand variable dereferences to create the call-by-need  machine. Finally, we combine the two improvements in the  machine. On our benchmarks this machine uses half the stack space, performs one quarter as many updates, and executes between 27% faster and 17% slower than our ℒ variant of Sestoft’s lazy Krivine machine. More interesting is that on one benchmark ℒ, , and consume unbounded space, but consumes constant space. Our comparisons to Sestoft’s Mark 2 machine are not exact, however, since we restrict ourselves to unpreprocessed closed lambda terms. Our variant of his machine does no environment trimming, conversion to deBruijn-style variable access, and does not provide basic constants, data type constructors, or the recursive let. (The Y combinator is used instead.)     

On-line graph coloring of {\mathbb{P}_5}-free graphs

Kierstead et al. (SIAM J Discret Math 8:485–498, 1995) have shown 1 that the competitive function of on-line coloring for -free graphs (i.e., graphs without induced path on 5 vertices) is bounded from above by the exponential function . No nontrivial lower bound was known. In this paper we show the quadratic lower bound . More precisely, we prove that is the exact competitive function for ()-free graphs. In this paper we also prove that 2 - 1 is the competitive function of the best clique covering on-line algorithm for ()-free graphs.     

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.     

The Calculus of Relations as a Foundation for Mathematics

A variable-free, equational logic $\mathcal{L}^\timesA variable-free, equational logic based on the calculus of relations (a theory of binary relations developed by De Morgan, Peirce, and Schr?der during the period 1864–1895) is shown to provide an adequate framework for the development of all of mathematics. The expressive and deductive powers of are equivalent to those of a system of first-order logic with just three variables. Therefore, three-variable first-order logic also provides an adequate framework for mathematics. Finally, it is shown that a variant of may be viewed as a subsystem of sentential logic. Hence, there are subsystems of sentential logic that are adequate to the task of formalizing mathematics. This paper is an expanded version of a talk given by the author at the Special Session on Automated Reasoning in Mathematics and Logic, held March 8–10, 2002, at the Georgia Institute of Technology, during the Joint Southeastern Section MAA/Southeast Regional AMS Meeting. The session was organized by Johan G. F. Belinfante.     

Cardinal interpolation with periodic polysplines on strips

Abstract  We obtain a multivariate extension of a classical result of Schoenberg on cardinal spline interpolation. Specifically, we prove the existence of a unique function in , polyharmonic of order p on each strip , , and periodic in its last n variables, whose restriction to the parallel hyperplanes , , coincides with a prescribed sequence of n-variate periodic data functions satisfying a growth condition in . The constructive proof is based on separation of variables and on Micchelli’s theory of univariate cardinal -splines. Keywords: cardinal -splines, polyharmonic functions, multivariable interpolation Mathematics Subject Classification (2000): 41A05, 41A15, 41A63     

A local approach to concept generation

Generating concepts defined by a binary relation between a set of properties and a set of objects is one of the important current problems encountered in Data Mining and Knowledge Discovery in Databases. We present a new algorithmic process which computes all the concepts, without requiring an exponential-size data structure, and with a good worst-time complexity analysis, which makes it competitive with the best existing algorithms for this problem. Our algorithm can be used to compute the edges of the lattice as well at no extra cost.      

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 .