Object replication is a common approach to enhance the availability of distributed data-intensive services and storage systems. Many such systems are known to have highly skewed object request probability distributions. In this paper, we propose an object replication degree customization scheme that maximizes the expected service availability under given object request probabilities, object sizes, and space constraints (e.g., memory/storage capacities). In particular, we discover that the optimal replication degree of an object should be linear in the logarithm of its popularity-to-size ratio. We also study the feasibility and effectiveness of our proposed scheme using applications driven by real-life system object request traces and machine failure traces. When the data object popularity distribution is known a priori, our proposed customization can achieve 1.32-2.92 "nines" increase in system availability (or 21-74% space savings at the same availability level) compared to uniform replication. Results also suggest that our scheme requires a moderate amount of replica creation/removal overhead (weekly changes involve no more than 0.24% objects and no more than 0.11% of total data size) under realistic object request popularity changes.

A multi-object operation incurs communication or synchronization overhead when the requested objects are distributed over different nodes. The object pair correlations (the probability for a pair of objects to be requested together in an operation) are often highly skewed and yet stable over time for real-world distributed applications. Thus, placing strongly correlated objects on the same node (subject to node space constraint) tends to reduce communication overhead for multi-object operations. This paper studies the optimization of correlation-aware data placement. First, we formalize a restricted form of the problem as a variant of the classic Quadratic Assignment problem and we show that it is NP-hard. Based on a linear programming relaxation, we then propose a polynomial-time approximation algorithm that finds an object placement with communication overhead at most two times that of the optimal placement. We further show that the computation cost can be reduced by limiting the optimization scope to a relatively small number of most important objects. We quantitatively evaluate our approach on keyword index placement for full-text search engines using real traces of 3.7 million web pages and 6.8 million search queries. Compared to the correlation-oblivious random object placement, our approach achieves 37-86% communication overhead reduction on a range of optimization scopes and system sizes. The communication reduction is 30-78% compared to a correlation-aware greedy approach.

Bloom filters are compact set representations that support set membership queries with small, one-sided error probabilities. Standard Bloom filters are oblivious to object popularity in sets and membership queries. However, sets and queries in many distributed applications follow known, stable, highly skewed distributions (e.g., Zipf-like). This paper studies the problem of minimizing the false-positive probability of a Bloom filter by adapting the number of hashes used for each data object to its popularity in sets and membership queries. We model the problem as a constrained nonlinear integer program and propose two polynomial-time solutions with bounded approximation ratios -- one is a 2-approximation algorithm with O(Nc) running time (c ≥ 6 in practice); the other is a (2+ε)-approximation algorithm with running time O(N2/ε)$, ε > 0. Here N denotes the total number of distinct data objects that appear in sets or queries. We quantitatively evaluate our proposed approach on two distributed applications (cooperative caching and full-text keyword searching) driven by real-life data traces. Compared to standard Bloom filters, our data popularity-conscious Bloom filters achieve up to 24 and 27 times false-positive probability reduction for the two applications respectively. The quantitative evaluation also validates our solution's bounded approximation ratio to the optimal.

Network structure construction and global state maintenance are expensive in large-scale dynamic peer-to-peer (P2P) networks. With inherent topology independence and low state maintenance overhead, random walk is an excellent tool in such network environments. However, the current uses are limited to unguided or heuristic random walks with no guarantee on their converged node visitation probability distribution. Such a convergence guarantee is essential for strong analytical properties and high performance of many P2P applications. In this paper, we investigate an approach for random walks to converge to application-desired node visitation probability distributions while only requiring information about the direct neighbors of each peer. Our approach is guided by the Metropolis-Hastings algorithm for Monte Carlo Markov Chain sampling. Our contributions are threefold. First, we analyze the convergence time of the random walk node visitation probability distribution on common P2P network topologies. Second, we analyze the fault tolerance of our random walks in dynamic networks with potential walker losses. Third, we present the effectiveness of random walks in assisting three realistic network applications: random membership subset management, search, and load balancing. Both search and load balancing desire random walks with biased node visitation distributions to achieve application-specific goals. Our analysis, simulations, and Internet experiment demonstrate the advantage of our random walks compared with alternative topology-independent index-free approaches.

No abstract available.

Existing random membership management algorithms provide each node with a small, uniformly random subset of global participants. However, many applications would benefit more from non-uniform random member subsets. For instance, non-uniform gossip algorithms can provide distance-based propagation bounds and thus information can reach nearby nodes sooner. In another example, Kleinberg shows that networks with random long-links following distance-based non-uniform distributions exhibit better routing performance than those with uniformly randomized topologies. In this paper, we propose a scalable non-uniform random membership management algorithm, which provides each node with a random membership subset with application-specified probability e.g., with probability inversely proportional to distances. Our algorithm is the first non-uniform random membership management algorithm with proved convergence and bounded convergence time. Moreover, our algorithm does not put specific restrictions on the network topologies and thus has wide applicability.

Maintaining a monotonic labeling of an ordered list during the insertion of n items requires $\Omega$(n log n) individual relabelings, in the worst case, if the number of usable labels is only polynomial in n. This follows from a lower bound for a new problem, prefix bucketing.

We show that a Turing machine with two single-head one-dimensional tapes cannot recognize the set.

No abstract available.

This is a complete exposition of a tight version of a fundamental theorem of computational complexity due to Levin: The inherent space complexity of any partial function is very accurately specifiable in a Π1 way, and every such specification that is even Σ2 does characterize the complexity of some partial function, even one that assumes only the values 0 and 1.

. We show that a Turing machine with two single-head one-dimensional tapes cannot recognize the set f x2x 0 j x 2 f0; 1g and x 0 is a prefix of x g in real time, although it can do so with three tapes, two two-dimensional tapes, or one two-head tape, or in linear time with just one tape. In particular, this settles the longstanding conjecture that a two-head Turing machine can recognize more languages in real time if its heads are on the same one-dimensional tape than if they are on separate one-dimensional tapes. 1. Introduction The Turing machines commonly used and studied in computer science have separate tapes for input/output and for storage, so that we can conveniently study both storage as a dynamic resource and the more complex storage structures required for efficient implementation of practical algorithms [HS65]. Early researchers [MRF67] asked specifically whether two-head storage is more powerful if both heads are on the same one-dimensional storage tape than if t...

For any fixed k , a remarkably simple single-tape Turing machine can simulate k independent counters in real time.

In this paper we describe a new linear-time string-matching algorithm requiring neither dynamic storage allocation nor other high-level capabilities. The algorithm can be implemented to run in linear time even on a six-head two-way finite automaton. Moreover, the automaton requires only “{= , ≠}- branching” [1]. (Decisions depend on which of the six scanned pattern or text symbols and positions are the same, but not on the particular symbols or how many symbols there are. Hence the same algorithm works even for an infinite alphabet.) A “real-time” implementation is possible on such a multihead finite automaton with a few more heads.

Single-head tapes are used to simulate multihead Turing machine tape units without loss.For one-dimensional tapes, the new simulations are simpler and use far fewer tapes than prevj known simulations.For multidimensional tapes, the results are entirely new.

If the time bounds defining two nondeterministic complexity classes are too close for separation by the two known techniques, then they are almost too close for separation by any relativizable technique. Proof of an analogous result for space would be a major breakthrough, implying $\operatorname{NSPACE}(\log n) = \operatorname{DSPACE}(\log n)$.

Static, descriptional complexity (program size) [16, 9] can be used to obtain lower bounds on dynamic, computational complexity (such as running time). We describe and discuss this “information-theoretic approach” in the following section. Paul introduced it in [13], to obtain restricted lower bounds on the time complexity of sorting. We use the approach here to obtain lower time bounds for on-line simulation of one abstract storage unit by another. A major goal of our work is to promote the approach.

The string-matching problem is to find all instances (as contiguous substrings) of a “pattern” character string x in a longer “text" string ”. The naive algorithm, trying the pattern from scratch starting at each successive text position, requires only a fixed number of auxiliary storage locations but time proportional to $|x|\cdot|Y|$ (worst case). On the other hand, the fast algorithm of Knuth, Morris, and Pratt requires only time proportional to $|Y|$ but extra space proportional to $|x|$ (every case). Algorithms described in this paper reduce the extra space used by the Knuth–Morris–Pratt algorithm down to $O(\log |x|)$, and the time for the naive algorithm down to $O(|x|^\varepsilon |y|)$ for any fixed $\varepsilon > 0$. Also described are implementations on two-way multihead finite automata and multitape Turing machines.

Let P1 = {w ~ X*:w = w R, [w I > 1} be the set of all nontnvial pahndromes over X A hneartime on-hne recogmtmn algorithm is presented for P~ ("palstar") on a random-access machine with addmon and umform cost criterion Also presented are a hnear-tlme on-line recognmon algorithm for P~ on a muitltape Turmg machine and a recognition algorithm for Pt 2 on a two-way deterministic pushdown automaton.The correctness of these algorithms is based on new "cancellation iemmas" for the languages P~ and P~

AaSTancr.A recurslve padding technique is used to obtain conditions sufficient for separation of nondetermlmsttc multltape Turlng machine time complexity classes If T2 is a running time and Tl(n + 1) grows more slowly than T~(n), then there is a language which can be accepted nondetermmlstlcally within time bound T~ but which cannot be accepted nondetermlnlStlcally within time bound T1.If even T~(n + f(n)) grows more slowly than Tz(n), where f is the very slowly growing "rounded reverse" of some real-time countable function, then there is such a language over a single-letter alphabet.The strongest known dmgonalization results for both deterministic and nondetermlmstlc time complexity classes are reviewed and orgamzed for comparison with the results of the new padding technique KEY WOADS ^NO PHaASrS: Turlng machine, complexity class, complexity hierarchy, time complexity, nondetermmism, padding, recursmn theorem, dmgonahzatmn, single-letter alphabet CR CAa~ORIES 5 23, 5.25, 5.26, 5 27 This paper represents a portion of the first author's Ph D d~ssertatlon [25] written at M.

Correction of a string x into a language L is the problem of finding a string $y \in L$ to which x can be edited at least cost. The edit operations considered here are single-character deletions, single-character insertions, and single-character substitutions, each at an independent cost that does not depend on context. Employing a linear-time algorithm for solving single-origin graph shortest distance problems, it is shown how to correct a string of length n into the language accepted by a counter automaton in time proportional to $n^2 $ on a RAM with unit operation cost function. The algorithm is uniform over counter automata and edit cost functions; and it is shown how the correction time depends on the size of the automaton, the nature of the cost function, and the correction cost itself. For less general cases, potentially faster algorithms are described, including a linear-time algorithm for the case that very little correction is necessary and that the automaton’s counter activity is determined by the input alone. Specializing the main result to counter automata which do not use their counters gives general linear-time correction into regular languages.

The string-matching problem is to find all instances (as contiguous substrings) of a “pattern” character string x in a longer “text string ”. The naive algorithm, trying the pattern from scratch starting at each successive text position, requires only a fixed number of auxiliary storage locations but time proportional to $|x|\cdot|Y|$ (worst case). On the other hand, the fast algorithm of Knuth, Morris, and Pratt requires only time proportional to $|Y|$ but extra space proportional to $|x|$ (every case). Algorithms described in this paper reduce the extra space used by the Knuth–Morris–Pratt algorithm down to $O(\log |x|)$, and the time for the naive algorithm down to $O(|x|^\varepsilon |y|)$ for any fixed $\varepsilon > 0$. Also described are implementations on two-way multihead finite automata and multitape Turing machines.

Just as the Church-Turing thesis has simplified proofs of computability [8], efficient simulations of one computer model by another have simplified proofs of complexity upper bounds. A good example of this is Fischer, Meyer, and Rosenberg's real-time simulation of multihead Turing machines by multitape Turing machines [5]. Without this result, for example, even Slisenko [11] may have found it hopeless to show that a multitape Turing machine can recognize palindromes in real time. In this paper we give a comparatively simple proof of the Fischer-Meyer-Rosenberg result, dramatically reduce the number of single-head tapes required for the simulation, and generalize the result to multidimensional tapes. In the case of Slisenko's palindrome-recognizer, for example, our best simulation brings the number of tapes for a multitape Turing machine implementation down from 41 to 20.

It is shown by simulation that every language accepted within time $n^d$ by a nondeter-ministic one-dimensional Turing machine is accepted in linear time by a nondeterministic d-dimensional iterative array. Conversely, every language accepted in linear time by such an iterative array is accepted within time $n^{d+1}$ by a nondeterministic one-dimensional Turing machine. It follows that the class of languages accepted in linear time by nondeterministic multidimensional iterative arrays is precisely Karp’s class NP, that nondeterministic $(d + 2)$-dimensional iterative arrays are more powerful than nondeterministic d-dimensional iterative arrays, and that nondeterministic two-dimensional iterative arrays are more powerful than the entire class of nondeterministic multidimensional Turing machines. Related deterministic results are surveyed and summarized for comparison.

Let P1 = {w ε Σ*:w = wR, |w| ≫ 1} be the set of all nontrivial palindromes over Σ. In Part I, we present a linear-time on-line recognition algorithm for P1* ("palstar") on a random-access machine with addition and uniform cost criterion. We also present a lineartime on-line recognition algorithm for P12 on a multitape Turing machine and a recognition algorithm for P12 on a two-way deterministic pushdown automaton. The correctness of these algorithms is based on new "cancellation lemmas" for the languages P1* and P12. In Part II, we present real-time recognition algorithms for the languages {wxyxz ε Σ*: |w|=r|x|, |y|=s|x|, |z|=t|x|} and {wxyxRz ε Σ*: |w|=r|x|, |y|=s|x|, |z|=t|x|} on multitape Turing machines, for arbitrary fixed r, s, and t.

Let NIA(d) be the family of languages accepted within linear time by nondeterministic d-dimensional iterative arrays. (On-line deterministic multidimensional iterative arrays have been studied by Cole [2].) It has been observed [8] that every language accepted by a one-dimensional single-head Turing machine simultaneously within time n2 and space n is in NIA(2). Our main result (Theorem 2) generalizes this observation to NTIME(nd) @@@@ NIA(d), where NTIME(T(n)) is the family of languages accepted within time T(n) by nondeterministic one-dimensional multihead Turing machines.

The study of partition relations for cardinal numbers introduced by Erdös and his school in the 1950's has, for the past several years, had a profound impact in logic. Unfortunately, quite early in their development, it was noticed by Rado [1] that the potentially most fruitful class of such relations, infinite exponent partition relations, were always in contradiction with the axiom of choice (AC). As a result, such relations were overlooked. This turned out to be a mistake; for, as has been noticed recently, a close study of infinite exponent partition relations is both interesting and rewarding. For example, there are weakened versions of such relations which are provable in ZF and which have valuable applications in recursion theory and set theory. In addition, the pure theory of these relations, like that of the axiom of determinateness, is fruitful as well as elegant. For more background here one should refer to [3]. At any rate, with a more detailed look at infinite exponent partition relations came a more refined version of Rado's original theorem. Specifically, Rado used the full axiom of choice to carefully construct partitions to violate any desired relation—a more sophisticated look at the actual theory of such relations indicated how one could put together some desired partitions using only well-ordered choice [3]. The distinction between well-ordered choice and full choice is by no means vacuous in this context. For Mathias has shown [4] that the simplest infinite exponent partition relation, ω → (ω)ω, is consistent with countable choice (well-ordered choice of length ℵ0) and, in fact, is consistent with dependent choice.