Competitive Deadline Scheduling via Additional or Faster Processors

This paper studies on-line scheduling in a single-processor system that allows preemption. The aim is to maximize the total value of jobs completed by their deadlines. It is known that if the on-line scheduler is given a processor faster (say, two times faster) than the off-line scheduler, then there exists an on-line algorithm called that can achieve an O(1) competitive ratio. In this paper, we show that using additional unit-speed processors instead of a faster processor is a possible but not cost effective way to achieve an O(1) competitive ratio. Specifically, we find that-(logk) unit-speed processors are required, where k is the importance ratio. Another contribution of this paper is an improved analysis of the competitiveness of ; this new analysis enables us to show that , when extended to multi-processor systems, can still guarantee an O(1) competitive ratio.     

Parallel Multi-Block ADMM with <Emphasis Type="Italic">o</Emphasis>(1 / <Emphasis Type="Italic">k</Emphasis>) Convergence

This paper introduces a parallel and distributed algorithm for solving the following minimization problem with linear constraints:

$$\begin{aligned} \text {minimize} ~~&f_1(\mathbf{x}_1) + \cdots + f_N(\mathbf{x}_N)\\ \text {subject to}~~&A_1 \mathbf{x}_1 ~+ \cdots + A_N\mathbf{x}_N =c,\\&\mathbf{x}_1\in {\mathcal {X}}_1,~\ldots , ~\mathbf{x}_N\in {\mathcal {X}}_N, \end{aligned}$$

where \(N \ge 2\), \(f_i\) are convex functions, \(A_i\) are matrices, and \({\mathcal {X}}_i\) are feasible sets for variable \(\mathbf{x}_i\). Our algorithm extends the alternating direction method of multipliers (ADMM) and decomposes the original problem into N smaller subproblems and solves them in parallel at each iteration. This paper shows that the classic ADMM can be extended to the N-block Jacobi fashion and preserve convergence in the following two cases: (i) matrices \(A_i\) are mutually near-orthogonal and have full column-rank, or (ii) proximal terms are added to the N subproblems (but without any assumption on matrices \(A_i\)). In the latter case, certain proximal terms can let the subproblem be solved in more flexible and efficient ways. We show that \(\Vert {\mathbf {x}}^{k+1} - {\mathbf {x}}^k\Vert _M^2\) converges at a rate of o(1 / k) where M is a symmetric positive semi-definte matrix. Since the parameters used in the convergence analysis are conservative, we introduce a strategy for automatically tuning the parameters to substantially accelerate our algorithm in practice. We implemented our algorithm (for the case ii above) on Amazon EC2 and tested it on basis pursuit problems with >300 GB of distributed data. This is the first time that successfully solving a compressive sensing problem of such a large scale is reported.

     

Reasoning about temporal properties of rational play

This article is about defining a suitable logic for expressing classical game theoretical notions. We define an extension of alternating-time temporal logic (ATL) that enables us to express various rationality assumptions of intelligent agents. Our proposal, the logic ATLP (ATL with plausibility) allows us to specify sets of rational strategy profiles in the object language, and reason about agents’ play if only these strategy profiles were allowed. For example, we may assume the agents to play only Nash equilibria, Pareto-optimal profiles or undominated strategies, and ask about the resulting behaviour (and outcomes) under such an assumption. The logic also gives rise to generalized versions of classical solution concepts through characterizing patterns of payoffs by suitably parameterized formulae of ATLP. We investigate the complexity of model checking ATLP for several classes of formulae: It ranges from $\Delta_{\mathbf{3}}^{\mathbf{P}}$ to PSPACE in the general case and from $\Delta_{\mathbf{3}}^{\mathbf{P}}$ to $\Delta_{\mathbf{4}}^{\mathbf{P}}$ for the most interesting subclasses, and roughly corresponds to solving extensive games with imperfect information.     

Efficient emulation of single-hop radio network with collision detection on multi-hop radio network with no collision detection

Summary This paper presents an efficient randomized emulation ofsingle-hop radio networkwith collision detection onmulti-hop radio networkwithout collision detection. Each step of the single-hop network is emulated by rounds of the multi-hop network and succeeds with probability 1–. (n is the number of processors,D the diameter and the maximum degree). It is shown how to emulate any polynomial algorithm such that the probability of failure remains . A consequence of the emulation is an efficient randomized algorithm for choosing a leader in a multi-hop network. Reuven Bar-Yehuda was born in Iran, on July 17th 1951. Received B.A., M.Sc., and D.Sc. in Computer Science from the Technion — Israel Institute of Technology, Haifa, Israel, in 1978, 1980, and 1983, respectively. He is currently a Senior Lecturer of Computer Science at the Technion. From 1984 to 1986, he was a visiting assistant professor in the Computer Science Dept. at the Duke Univesity His research interests include computational geometry, VLSI, graph algorithms and distributed algorithms. Oded Goldreich was born in Tel-Aviv, Israel, on February 4th 1957. Received B.A., M.Sc., and D.Sc. in Computer Science from the Technion — Israel Institute of Technology, Haifa, Israel, in 1980, 1982, and 1983, respectively. He is currently an Associate Professor of Computer Science at the Technion. From 1983 to 1986, he was a postdoctoral fellow at MIT's Laboratory for Computer Science. His research interests include cryptography and related areas, relation between randomness and algorithms, and distributed computation. Alon Itai was born in Scotland, on December 12th 1946. Received B.Sc. in Mathematics from the Hebrew University in Jerusalem in 1969. M.Sc., and Ph.D. in Computer Science from the Weizmann Institute of Science, Rehovot, Israel in 1971 and 1976. He is currently an Associate Professor of Computer Science at the Technion. His research interests include randomized and distributed algorithms, computational learning theory and performance evaluation.The second author was partially supported by grant No. 86-00301 from the United States—Israel Bi-national Science Foundation BSF), Jerusalem, Israel.     

On Projection Matrices $$\mathcal{P}^k \to \mathcal{P}^2 ,k = 3,...,6, $$ and their Applications in Computer Vision

Projection matrices from projective spaces have long been used in multiple-view geometry to model the perspective projection created by the pin-hole camera. In this work we introduce higher-dimensional mappings for the representation of various applications in which the world we view is no longer rigid. We also describe the multi-view constraints from these new projection matrices (where k > 3) and methods for extracting the (non-rigid) structure and motion for each application.     

Circuits on cylinders

We consider the computational power of constant width polynomial size cylindrical circuits and nondeterministic branching programs. We show that every function computed by a circuit can also be computed by a constant width polynomial size cylindrical nondeterministic branching program (or cylindrical circuit) and that every function computed by a constant width polynomial size cylindrical circuit belongs to ACC⁰.     

Tracking the Best Expert

We generalize the recent relative loss bounds for on-line algorithms where the additional loss of the algorithm on the whole sequence of examples over the loss of the best expert is bounded. The generalization allows the sequence to be partitioned into segments, and the goal is to bound the additional loss of the algorithm over the sum of the losses of the best experts for each segment. This is to model situations in which the examples change and different experts are best for certain segments of the sequence of examples. In the single segment case, the additional loss is proportional to log n, where n is the number of experts and the constant of proportionality depends on the loss function. Our algorithms do not produce the best partition; however the loss bound shows that our predictions are close to those of the best partition. When the number of segments is k+1 and the sequence is of length &ell, we can bound the additional loss of our algorithm over the best partition by . For the case when the loss per trial is bounded by one, we obtain an algorithm whose additional loss over the loss of the best partition is independent of the length of the sequence. The additional loss becomes , where L is the loss of the best partitionwith k+1 segments. Our algorithms for tracking the predictions of the best expert aresimple adaptations of Vovk's original algorithm for the single best expert case. As in the original algorithms, we keep one weight per expert, and spend O(1) time per weight in each trial.     

Michell cantilevers constructed within trapezoidal domains—Part II: virtual displacement fields

The present second part of the paper deals with the virtual displacement fields associated with the optimality conditions , where σ _T and σ _C represent the allowable values of the tensile and compressive stress, respectively. The displacement fields vanish along a straight segment of a line support and are constructed within an infinite domain bounded by two half-lines. The displacement fields are provided by the integral formulae involving the Lamé fields found in part I of this paper. All the results are expressed in terms of Lommel-like functions. These results make it possible to determine the volumes of the optimal cantilevers designs within the feasible domain considered. Computation of the volumes along with analyses of concrete cantilevers will be the subject of part IV of the present paper.     

Cheating husbands and other stories: A case study of knowledge,action, and communication

The relationship between knowledge and action is a fundamental one: a processor in a computer network (or a robot or a person, for that matter) should base its actions on the knowledge (or information) it has. One of the main uses of communication is passing around information that may eventually be required by the receiver in order to decide upon subsequent actions. Understanding the relationship between knowledge, action, and communication is fundamental to the design of computer network protocols, intelligent robots, etc. By looking at a number of variants of thecheating husbands puzzle, we illustrate the subtle relationship between knowledge, communication, and action in a distributed environment. Yoram Moses received a B.Sc. in mathematics from the Hebrew University, Jerusalem, in 1981, and a Ph.D. in computer science from Stanford University in 1986. He will be spending the 1985/6 school year as a post-doctoral fellow at MIT. His major research interests are distributed systems, artificial intelligence, and the methodological foundations of computer science. Danny Dolev received a B.Sc. in physics from the Hebrew University Jerusalem in 1971, an M.Sc. in applied mathematics from the Weizmann Institute of Science, Israel in 1973, and a Ph.D. in computer science from the Weizmann Institute of Science in 1979. After two years as a post-doctoral fellow at Stanford and a year as a visiting scientist at IBM, he joined the Hebrew University, Jerusalem, in 1982. His major research interests are distributed computing, reliability of distributed systems, and algorithms. Joe Halpern received a B.Sc. in mathematics from the University of Toronto in 1975, and a Ph.D. in mathematics from Harvard University in 1981. In between, he spent two years as the head of the mathematics department at Bawku Secondary School, in Ghana. After a year as a visiting scientist at MIT, he joined IBM in 1982. His major research interests are reasoning about knowledge, distributed computing, and logics of programs.The work of this author was supported in part by DARPA contract N00039-82-C-0250     

Efficient Algorithms for Interface Timing Verification

This paper presents algorithms for computing separations between events that are constrained to obey prespecified relationships in their relative time of occurrence. The algorithms are useful for interface timing verification, where event separations are checked against timing requirements. The first algorithm computes separations when only linear and max constraints exist. The algorithm must converge to correct maximum separation values in a finite number of steps, or report an inconsistence of the constraints, irrespective of the existence of infinite constraint bounds or infinite event separations. It is conjectured to run in time, where V is the number of events, and E is the number of relationships between them. The other algorithms extend the first, and compute event separations in the NP-complete version of the problem where min constraints exist. Experiments demonstrate the algorithms are efficient in practice.     

Object-oriented cam design through the internet

We have developed a Web-based interactive cam design package under the programming paradigm of the language environment. This package was initially developed as a teaching and learning tool for educational use in an undergraduate Computer-Aided Mechanism Design course. Because the system is Web-based and implemented through a client/server model with the user interface through the Web browser, it is easy to use and maintain. The system can also be used to solve practical engineering cam design problems with flat or roller followers and with translating or oscillating motion types. The system can be used to generate the cam profile, transmission angle, position, velocity, and acceleration of the follower. Once a cam/follower system is designed, animation of the cam/follower system can be performed. At the end of the design, the CNC code for manufacturing the designed cam can also be produced through our Web-based cam design system. The package consists of a number of modules including various Web pages, common gateway interface (CGI) programs, a program called cam.ch, and the CCam class which performs the necessary computation for cam design. Two different versions of the cam design package have been designed and implemented. One runs the cam design program on the client machine as a applet, and the other runs the cam design program on the Web server through CGI. In this paper, details of design and implementation of Web-based cam design package will be described. Two application examples with different motion types for the follower will be used to illustrate features of the applet-based and CGI-based implementation schemes. The ideas of the Web-based software design presented in this paper can be applied to other application areas.     

Two-Parameter Discrete Systems over a Residue Ring and Their Properties

A class of two-parameter discrete systems defined on the ring of class of residues of integers modulo m is studied. All solutions are shown to be periodic, stability conditions (equality of solutions to zero, beginning from a certain instant) and a controllability condition are formulated. Controllability is shown to guarantee stabilizability.     

Cubature formulae for nearly singular and highly oscillating integrals

The paper deals with the approximation of integrals of the type

$$\begin{aligned} I(f;{\mathbf {t}})=\int _{{\mathrm {D}}} f({\mathbf {x}}) {\mathbf {K}}({\mathbf {x}},{\mathbf {t}}) {\mathbf {w}}({\mathbf {x}}) d{\mathbf {x}},\quad \quad {\mathbf {x}}=(x_1,x_2),\quad {\mathbf {t}}\in \mathrm {T}\subseteq \mathbb {R}^p, \ p\in \{1,2\} \end{aligned}$$

where \({\mathrm {D}}=[-\,1,1]^2\), f is a function defined on \({\mathrm {D}}\) with possible algebraic singularities on \(\partial {\mathrm {D}}\), \({\mathbf {w}}\) is the product of two Jacobi weight functions, and the kernel \({\mathbf {K}}\) can be of different kinds. We propose two cubature rules determining conditions under which the rules are stable and convergent. Along the paper we diffusely treat the numerical approximation for kernels which can be nearly singular and/or highly oscillating, by using a bivariate dilation technique. Some numerical examples which confirm the theoretical estimates are also proposed.

     

One-bit algorithms

Many algorithms in distributed systems assume that the size of a single message depends on the number of processors. In this paper, we assume in contrast that messages consist of a single bit. Our main goal is to explore how the one-bit translation of unbounded message algorithms can be sped up by pipelining. We consider two problems. The first is routing between two processors in an arbitrary network and in some special networks (ring, grid, hypercube). The second problem is coloring a synchronous ring with three colors. The routing problem is a very basic subroutine in many distributed algorithms; the three coloring problem demonstrates that pipelining is not always useful. Amotz Bar-Noy received his B.Sc. degree in Mathematics and Computer Science in 1981, and his Ph.D. degree in Computer Science in 1987, both from the Hebrew University of Jerusalem, Israel. Between 1987 and 1989 he was a post-doctoral fellow in the Department of Computer Science at Stanford University. He is currently a visiting scientist at the IBM Thomas J. Watson Research Center. His current research interests include the theoretical aspects of distributed and parallel computing, computational complexity and combinatorial optimization. Joseph (Seffi) Naor received his B.A. degree in Computer Science in 1981 from the Technion, Israel Institute of Technology. He received his M.Sc. in 1983 and Ph.D. in 1987 in Computer Science, both from the Hebrew University of Jerusalem, Israel. Between 1987 and 1988 he was a post-doctoral fellow at the University of Southern California, Los Angeles, CA. Since 1988 he has been a post-doctoral fellow in the Department of Computer Science at Stanford University. His research interests include combinatorial optimization, randomized algorithms, computational complexity and the theoretical aspects of parallel and distributed computing. Moni Naor received his B.A. in Computer Science from the Technion, Israel Institute of Technology, in 1985, and his Ph.D. in Computer Science from the University of California at Berkeley in 1989. He is currently a visiting scientist at the IBM Almaden Research Center. His research interests include computational complexity, data structures, cryptography, and parallel and distributed computation.Supported in part by a Weizmann fellowship and by contract ONR N00014-85-C-0731Supported by contract ONR N00014-88-K-0166 and by a grant from Stanford's Center for Integrated Systems. This work was done while the author was a post-doctoral fellow at the University of Southern California, Los Angeles, CAThis work was done while the author was with the Computer Science Division, University of California at Berkeley, and Supported by NSF grant DCR 85-13926     

On the complexity of graph reconstruction

In the wake of the resolution of the four-color conjecture, the graph reconstruction conjecture has emerged as one focal point of graph theory. This paper considers thecomputational complexity of decision problems (Deck Checking andLegitimate Deck), construction problems (Preimage Construction), and counting problems (Preimage Counting) related to the graph reconstruction conjecture. We show that:

Generating Model Checkers from Algebraic Specifications

There is a great deal of research aimed toward the development of temporal logics and model checking algorithms which can be used to verify properties of systems. In this paper, we present a methodology and supporting tools which allow researchers and practitioners to automatically generate model checking algorithms for temporal logics from algebraic specifications. These tools are extensions of algebraic compiler generation tools and are used to specify model checkers as mappings of the form , where L _s is a temporal logic source language and L _t is a target language representing sets of states of a model M, such that . The algebraic specifications for a model checker define the logic source language, the target language representing sets of states in a model, and the embedding of the source language into the target language. Since users can modify and extend existing specifications or write original specifications, new model checking algorithms for new temporal logics can be easily and quickly developed; this allows the user more time to experiment with the logic and its model checking algorithm instead of developing its implementation. Here we show how this algebraic framework can be used to specify model checking algorithms for CTL, a real-time CTL, CTL*, and a custom extension called CTL ^e that makes use of propositions labeling the edges as well as the nodes of a model. We also show how the target language can be changed to a language of binary decision diagrams to generate symbolic model checkers from algebraic specifications.     

Behavior of confined fluids in nanoslit pores: the normal pressure tensor

The aim of our research is to develop a theory, which can predict the behavior of confined fluids in nanoslit pores. The nanoslit pores studied in this work consist of two structureless and parallel walls in the xy plane located at z = 0 and z = H, in equilibrium with a bulk homogeneous fluid at the same temperature and at a given uniform bulk density. We have derived the following general equation for prediction of the normal pressure tensor P _zz of confined inhomogeneous fluids in nanoslit pores:

Adaptive Anomaly Detection in Transaction-Oriented Networks

Adaptive algorithms for real-time and proactive detection of network/service anomalies, i.e., soft performance degradations, in transaction-oriented wide area networks (WANs) have been developed. These algorithms (i) adaptively sample and aggregate raw transaction records to compute service-class based traffic intensities, in which potential network anomalies are highlighted; (ii) construct dynamic and service-class based performance thresholds for detecting network and service anomalies; and (iii) perform service-class based and real-time network anomaly detection. These anomaly detection algorithms are implemented as a real-time software system called TRISTAN ( ansaction n antaneous nomaly otification), which is deployed in the AT&T Transaction Access Services (TAS) network. The TAS network is a commercially important, high volume (millions of transactions per day), multiple service classes (tens), hybrid telecom and data WAN that services transaction traffic such as credit card transactions in the US and neighboring countries. TRISTAN is demonstrated to be capable of automatically and adaptively detecting network/service anomalies and correctly identifying the corresponding "guilty" service classes in TAS. TRISTAN can detect network/service faults that elude detection by the traditional alarm-based network monitoring systems.     

High Order Algorithm for the Time-Tempered Fractional Feynman–Kac Equation

We provide and analyze the high order algorithms for the model describing the functional distributions of particles performing anomalous motion with power-law jump length and tempered power-law waiting time. The model is derived in Wu et al. (Phys Rev E 93:032151, 2016), being called the time-tempered fractional Feynman–Kac equation named after Richard Feynman and Mark Kac who first considered the model describing the functional distribution of normal motion. The key step of designing the algorithms is to discretize the time tempered fractional substantial derivative, being defined as

$$\begin{aligned} {^S\!}D_t^{\gamma ,\widetilde{\lambda }} G(x,p,t)\!=\!D_t^{\gamma ,\widetilde{\lambda }} G(x,p,t)\!-\!\lambda ^\gamma G(x,p,t) \end{aligned}$$

with \(\widetilde{\lambda }=\lambda + pU(x),\, p=\rho +J\eta ,\, J=\sqrt{-1}\), where

$$\begin{aligned} D_t^{\gamma ,\widetilde{\lambda }} G(x,p,t) =\frac{1}{\varGamma (1-\gamma )} \left[ \frac{\partial }{\partial t}+\widetilde{\lambda } \right] \int _{0}^t{\left( t-z\right) ^{-\gamma }}e^{-\widetilde{\lambda }\cdot (t-z)}{G(x,p,z)}dz, \end{aligned}$$

and \(\lambda \ge 0\), \(0<\gamma <1\), \(\rho >0\), and \(\eta \) is a real number. The designed schemes are unconditionally stable and have the global truncation error \(\mathscr {O}(\tau ^2+h^2)\), being theoretically proved and numerically verified in complex space. Moreover, some simulations for the distributions of the first passage time are performed, and the second order convergence is also obtained for solving the ‘physical’ equation (without artificial source term).