A model of sequential computation with Pipelined access to memory

We introduce a new sequential model of computation, called the Logarithmic Pipelined Model (LPM), in which a RAM processor of fixed size has pipelined access to a memory ofm cells in time logm. Our motivation is that the usual assumption that a memory can be accessed in constant time becomes theoretically unacceptable asm increases, while an access time of logm is consistent with VLSI technologies. For a problem II of sizen, IT P, we denote byS(n) the time required by the fastest known sequential algorithm, and byT(n) the time required by the fastest algorithm solving II in the LPM. LettingO(logn) =O(logm), we define several complexity classes; in particular, LP₀ = {II P:T(n) =O(S(n))}, the class of problems for which the LPM is as efficient as the standard model, and LP =IIP:T(n) =O(S(n) logn), where the problems are less adequately solved in the new model. We first study the relations between the LPM and other models of computation. Of particular relevance is comparison with the PRAM model. Then we discuss several problems and derive the relative upper and lower bounds in the LPM. Our results lead to a new organization of parallel algorithms for list-linked structures.This work was supported in part by M.U.R.S.T. of Italy under a research grant.     

Randomized range-maxima in nearly-constant parallel time

Given an array ofn input numbers, therange-maxima problem is that of preprocessing the data so that queries of the type what is the maximum value in subarray [i..j] can be answered quickly using one processor. We present a randomized preprocessing algorithm that runs inO(log^* n) time with high probability, using an optimal number of processors on a CRCW PRAM; each query can be processed in constant time by one processor. We also present a randomized algorithm for a parallel comparison model. Using an optimal number of processors, the preprocessing algorithm runs inO( (n)) time with high probability; each query can be processed inO ( (n)) time by one processor. (As is standard, (n) is the inverse of Ackermann function.) A constant time query can be achieved by some slowdown in the performance of the preprocessing stage.     

An optimal parallel algorithm for triangulating a set of points in the plane

This paper presents an optimal parallel algorithm for triangulating an arbitrary set ofn points in the plane. The algorithm runs inO(logn) time usingO(n) space andO(_n) processors on a Concurrent-Read, Exclusive-Write Parallel RAM model (CREW PRAM). The parallel lower bound on triangulation is (logn) time so the best possible linear speedup has been achieved. A parallel divide-and-conquer technique of subdividing a problem into subproblems is employed.     

A time-optimal parallel algorithm for three-dimensional convex hulls

In this paper we present an O(1/ logn)-time parallel algorithm for computing the convex hull ofn points in ³. This algorithm usesO(@#@ n^1+a) processors on a CREW PRAM, for any constant 0 < 1. So far, all adequately documented parallel algorithms proposed for this problem use time at least O(log² n). In addition, the algorithm presented here is the first parallel algorithm for the three-dimensional convex hull problem that is not based on the serial divide-and-conquer algorithm of Preparata and Hong, whose crucial operation is the merging of the convex hulls of two linearly separated point sets. The contributions of this paper are therefore (i) an O(logn)-time parallel algorithm for the three-dimensional convex hull problem, and (ii) a parallel algorithm for this problem that does not follow the traditional paradigm.This paper was presented in preliminary form at the 9th Annual ACM Symposium on Computational Geometry, San Diego, CA, May 1993 [32]. The work of N. M. Amato was supported in part by an AT&T Bell Laboratories Graduate Fellowship, the Joint Services Electronics Program (U.S. Army, U.S. Navy, U.S. Air Force) under Contract N00014-90-J-1270, and NSF Grant CCR-89-22008. This work was done while N. M. Amato was with the Department of Computer Science at the University of Illinois. The work of F. P. Preparata was supported in part by NSF Grants CCR-91-96152, CCR-91-96176, and ONR Contract N00014-91-J-4052, ARPA order 8225.     

Lot-sizing scheduling with batch setup times

This paper is concerned with scheduling independent jobs on m parallel machines in such a way that the makespan is minimized. Each job j is allowed to split arbitrarily into several parts, which can be individually processed on any machine at any time. However, a setup for uninterrupted s_j time units is required before any split part of job j can be processed on any machine. The problem is strongly NP-hard if the number m of machines is variable and weakly NP-hard otherwise. We give a polynomial-time -approximation algorithm for the former case and a fully polynomial-time approximation scheme for the latter. AMS Subject Classifications: 68M20 · 90B35 · 90C59     

Some Ergodic Results on Stochastic Iterative Discrete Events Systems

This paper deals with the asymptotic behavior of the stochastic dynamics of discrete event systems. In this paper we focus on a wide class of models arising in several fields and particularly in computer science. This class of models may be characterized by stochastic recurrence equations in ^K of the form T(n+1) = _n+1(T(n)) where _n is a random operator monotone and 1—linear. We establish that the behaviour of the extremas of the process T(n) are linear. The results are an application of the sub-additive ergodic theorem of Kingman. We also give some stability properties of such sequences and a simple method of estimating the limit points.     

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.     

Efficient Parallel Manipulations of IBB Coded Images on Meshes with Multiple Broadcasting

The Interpolation-Based Bintree (IBB) is a storage-saving encodingscheme for representing binary images. In this paper, we presentefficient parallel algorithms for important manipulations on IBBcoded images (also called bincodes). Given a set of bincodes, e.g.,B with size n, the 4-neighborfinding and the diagonal-neighbor finding algorithms onB can be accomplished in O(1) time on an n x n mesh computer with multiple broadcasting(MMB). Given two sets of bincodes, B ₁ and B ₂, with size n and m n, respectively, the intersection and unionoperations for B ₁ and B ₂ can be performedin O(1) time on an MMB using processors. With n ² processors, the complementoperation for B can be performed in O(logn) time.     

Die mittlere Additionsdauer eines Paralleladdierwerks

Summary Let E _n be the average number of steps for the addition of two binary numbers of length n (where the addition is carried out by a parallel adder as defined by v. Neumann), and let L _n be the least integer which is not less than the logarithm of n (of base 2). The following inequality is shown: L _n – 1 < E _n < L _n + 1. E _n can be computed recursively. A table of some values of E _n is given in the appendix. We suppose that E _n [log₂ n] + 1/3 holds for large n.     

Agents’ model of uncertainty

Multi-agent systems play an increasing role in sensor networks, software engineering, web design, e-commerce, robotics, and many others areas. Uncertainty is a fundamental property of these areas. Agent-based systems use probabilistic and other uncertainty models developed earlier without explicit consideration of agents. This paper explores the impact of agents on uncertainty models and theories. We compare two methods of introducing agents to uncertainty theories and propose a new theory called the agent-based uncertainty theory (AUT). We show advantages of AUT for advancing multi-agent systems and for solving an internal fundamental question of uncertainty theories, that is identifying coherent approaches to uncertainty. The advantages of AUT are that it provides a uniform agent-based representation and an operational empirical interpretation for several uncertainty theories such as rough set theory, fuzzy sets theory, evidence theory, and probability theory. We show also that the introduction of agents to intuitionist uncertainty formalisms can reduce their conceptual complexity. To build such uniformity the AUT exploits the fact that agents as independent entities can give conflicting evaluations of the same attribute. The AUT is based on complex aggregations of crisp (non-fuzzy) conflicting judgments of agents. The generality of AUT is derived from the logical classification of types (orders) of conflicts in the agent populations. At the first order of conflict, the two agent populations are disjoint and there is no interference of logic values assigned to any statement p and its negation by agents. The second order of conflict models superposition (interference) of logic values for overlapping agent populations where an agent assigns conflicting logic values (true, false) to the same attribute simultaneously.

Multiple dispatch in reflective runtime environment

Message dispatch in object-oriented programming (OOP) involves target method lookup in dispatch table/tree. Reflective environment builds dispatch data-structure at runtime as types can be added at runtime. Hence, algorithms for reflective environments require dynamic data structure for dispatch. In this paper, we propose a tree-based algorithm for multiple dispatch in reflective runtime environment. New classes can be added to the system at runtime. Proposed algorithm performs lookup in time proportional to $\log (n)$ times the polymorphic arguments, where n is number of classes in a system. Proposed algorithm uses type-safe approach for multimethod lookup resolving ambiguities. We compare performance of the proposed algorithm with the dispatch mechanism in commonly used virtual/reflexive systems, e.g., Java and Microsoft's Common Language Runtime (MS-CLR), in respect of efficiency and type-safety.     

Parallel approximation schemes for Subset Sum and Knapsack problems

Summary This paper presents parallel approximation schemes for the Subset Sum, 0–1 Knapsack, and several other optimization problems. These algorithms offer a three-way trade-off among parallel time, the accuracy of the solution, and the number of processors used. The maximum numbers of processors which can be usefully employed depend on n (the size of the input), and the accuracy requirement . The parallel running times of the algorithms are polynomial in both log n and log(1/) when enough processors are used.Parts of this research were done while both authors were at the Department of Computer Science, University of Toronto     

Geometric applications of a matrix-searching algorithm

LetA be a matrix with real entries and letj(i) be the index of the leftmost column containing the maximum value in rowi ofA.A is said to bemonotone ifi ₁ >i ₂ implies thatj(i ₁) J(i ₂).A istotally monotone if all of its submatrices are monotone. We show that finding the maximum entry in each row of an arbitraryn xm monotone matrix requires (m logn) time, whereas if the matrix is totally monotone the time is (m) whenmn and is (m(1 + log(n/m))) whenm<n. The problem of finding the maximum value within each row of a totally monotone matrix arises in several geometric algorithms such as the all-farthest-neighbors problem for the vertices of a convex polygon. Previously only the property of monotonicity, not total monotonicity, had been used within these algorithms. We use the (m) bound on finding the maxima of wide totally monotone matrices to speed up these algorithms by a factor of logn.On leave from the Technion, Haifa, Israel.     

Rationality of reward sharing in multi-agent reinforcement learning

In multi-agent reinforcement learning systems, it is important to share a reward among all agents. We focus on theRationality Theorem of Profit Sharing ⁵⁾ and analyze how to share a reward among all profit sharing agents. When an agent gets adirect reward R (R>0), anindirect reward μR (μ≥0) is given to the other agents. We have derived the necessary and sufficient condition to preserve the rationality as follows;

Visual space geometry derived from occlusion axioms

In our previous work [1] occlusion phenomena were considered as a foundation for development of geometrical structures in the visual field. The laws of occlusion were adapted to form the basis of an axiomatic system. Occlusion is formalized as a ternary relation and its properties include symmetry and transistivity. This leads to the definition of an abstract visual space (AVS). The geometry of an AVS is the subject of this research. Typical examples of an AVS are the convex open subsets of an n-dimensional real affine space for n2 or more generally, the convex open subsets of any n-dimensional affine space over some totally ordered field F, commutative or noncommutative. In an AVS we define such geometrical objects as lines, planes, convex bodies, closed and open subsets, etc. For any n-dimensional (n3) AVS X we construct an n-dimensional projective space P _F ⁿ over a totally ordered commutative or noncommutative field F and produce an embedding i: X xP _F ⁿ such that the image i(X) is open in P _F ⁿ and every line l in X is of the form l=i ^-1 (Li(X)) for some line L in P _F ⁿ. The mapping i and the field F depend on X and are unique up to isomorphism. We obtain a characterization of X via this embedding which is complete in the case of archimedean fields F. If F=R, the field of real numbers, i induces an embedding j: X ¶ A _R ⁿ and j(X) is a convex open subset of an affine space A _R ⁿ. If FR there can exist other types of AVS.     

Trivial Reals

Solovay showed that there are noncomputable reals α such that H(α n) ≤ H(1ⁿ)+O(1), where H is prefix-free Kolmogorov complexity. Such H-trivial reals are interesting due to the connection between algorithmic complexity and effective randomness. We give a new, easier construction of an H-trivial real. We also analyze various computability-theoretic properties of the H-trivial reals, showing for example that no H-trivial real can compute the halting problem (which means that our construction of an H-trivial computably enumerable set is a particularly easy, injury-free construction of an incomplete c.e. set). Finally, we relate the H-trivials to other classes of “highly nonrandom” reals that have been previously studied.     

Approximate fixed point sequence for a finite family of asymptotically pseudocontractive mappings

Let E be a real Banach space and K be a nonempty, closed, convex, and bounded subset of E. Let T_i:K→K, i=1,2,…,N, be N uniformly L-Lipschitzian, uniformly asymptotically regular with sequences {ε_n}, and asymptotically pseudocontractive mappings with sequences , where {ε_n} and , i=1,2,…,N, satisfy certain mild conditions. Let a sequence {x_n} be generated from x₁K by

for all integers n1, where T_n=T_n(modN), {u_n} be a sequence in K, and {λ_n}, {θ_n} and {μ_n} are three real sequences in [0,1] satisfying appropriate conditions; then x_n−T_lx_n→0 as n→∞ for each l{1,2,…,N}.     

Contiguous Search Problem in Sierpiński Graphs

In this paper we consider the problem of capturing an intruder in a particular fractal graph, the Sierpiński graph SG _n . The problem consists of having a team of mobile software agents that collaborate in order to capture the intruder. The intruder is a mobile entity that escapes from the team of agents, moving arbitrarily fast inside the network, i.e., traversing any number of contiguous nodes as long as no other agent resides on them. The agents move asynchronously and they know the network topology they are in is a Sierpiński graph SG _n . We first derive lower bounds on the minimum number of agents, number of moves and time steps required to capture the intruder. We then consider some variations of the model based on the capabilities of the agents: visibility, where the agents can “see” the state of their neighbors and thus can move autonomously; locality, where the agents can only access local information and thus their moves have to be coordinated by a leader. For each model, we design a capturing strategy and we make some observations. One of our goals is to continue a previous study on what is the impact of visibility on complexity: in this topology we are able to reach an optimal bound on the number of agents required by both cleaning strategies. However, the strategy in the visibility model is fully distributed, whereas the other strategy requires a leader. Moreover, the second strategy requires a higher number of moves and time steps. A preliminary version of this paper has been presented at the 4th International Conference on Fun with Algorithms (FUN’07) 17.     

A generalization of ACP using Belnap’s logic

ACP is combined with Belnap’s four-valued logic via conditional composition (if–then–else). We show that the operators of ACP can be seen as instances of more general, conditional operators. For example, both the choice operator + and δ (deadlock) can be seen as instances of conditional composition, and the axiom x + δ = x follows from this perspective. Parallel composition is generalized to the binary conditional merge _ψ where covers the choice between interleaving and synchronization, and ψ determines the order of execution. The instance _BB is ACP’s parallel composition, where B (both) is the truth value that models both true and false in Belnap’s logic. Other instances of this conditional merge are sequential composition, pure interleaving and synchronous merge. We investigate the expression of scheduling strategies in the conditions of the conditional merge.     

How to meet when you forget: log-space rendezvous in arbitrary graphs

Two identical (anonymous) mobile agents start from arbitrary nodes in an a priori unknown graph and move synchronously from node to node with the goal of meeting. This rendezvous problem has been thoroughly studied, both for anonymous and for labeled agents, along with another basic task, that of exploring graphs by mobile agents. The rendezvous problem is known to be not easier than graph exploration. A well-known recent result on exploration, due to Reingold, states that deterministic exploration of arbitrary graphs can be performed in log-space, i.e., using an agent equipped with O(log n) bits of memory, where n is the size of the graph. In this paper we study the size of memory of mobile agents that permits us to solve the rendezvous problem deterministically. Our main result establishes the minimum size of the memory of anonymous agents that guarantees deterministic rendezvous when it is feasible. We show that this minimum size is Θ(log n), where n is the size of the graph, regardless of the delay between the starting times of the agents. More precisely, we construct identical agents equipped with Θ(log n) memory bits that solve the rendezvous problem in all graphs with at most n nodes, if they start with any delay τ, and we prove a matching lower bound Ω(log n) on the number of memory bits needed to accomplish rendezvous, even for simultaneous start. In fact, this lower bound is achieved already on the class of rings. This shows a significant contrast between rendezvous and exploration: e.g., while exploration of rings (without stopping) can be done using constant memory, rendezvous, even with simultaneous start, requires logarithmic memory. As a by-product of our techniques introduced to obtain log-space rendezvous we get the first algorithm to find a quotient graph of a given unlabeled graph in polynomial time, by means of a mobile agent moving around the graph.