On the computability power and the robustness of set agreement-oriented failure detector classes

Solving agreement problems deterministically, such as consensus and k-set agreement, in asynchronous distributed systems prone to an unbounded number of process failures has been shown to be impossible. To circumvent this impossibility, unreliable failure detectors for the crash failure model have been widely studied. These are oracles that provide information on failures. The exact nature of such information is defined by a set of abstract properties that a particular class of failure detectors satisfy. The weakest class of such failure detectors that allow to solve consensus is Ω. This paper considers failure detector classes from the literature that solve k-set agreement in the crash failure model, and studies their relative power. It shows that the family of failure detector classes (1 ≤ x ≤ n), and (0 ≤ y ≤ n), can be “added” to provide a failure detector of the class Ω ^z (1 ≤ z ≤ n, a generalization of Ω). It also characterizes the power of such an “addition”, namely, , can construct Ω ^z iff y + z > t, and can construct Ω ^z iff x + z > t + 1, where t is the maximum number of processes that can crash in a run. As an example, the paper shows that, while allows solving 2-set agreement (but not consensus) and allows solving t-set agreement (but not (t − 1)-set agreement), a system with failure detectors of both classes can solve consensus for any value of t. More generally, the paper studies the failure detector classes , and Ω ^z , and shows which reductions among these classes are possible and which are not. The paper also presents a message-passing Ω ^k -based k-set agreement protocol and shows that Ω ^k is not enough to solve (k − 1)-set agreement. In that sense, it can be seen as a step toward the characterization of the weakest failure detector class that allows solving the k-set agreement problem. An extended abstract of this paper has appeared in the proceedings of PODC 2006 [20]. This work has been supported partially by a grant from LAFMI (Franco-Mexican Lab in Computer Science), the European Network of Excellence ReSIST and PAPIIT-UNAM.     

Uniform stabilization for linear systems with persistency of excitation: the neutrally stable and the double integrator cases

Consider the controlled system dx/dt = Ax + α(t)Bu where the pair (A, B) is stabilizable and α(t) takes values in [0, 1] and is persistently exciting, i.e., there exist two positive constants μ, T such that, for every t ≥ 0, ${\int_t^{t+T}\alpha(s){\rm d}s \geq \mu}Consider the controlled system dx/dt = Ax + α(t)Bu where the pair (A, B) is stabilizable and α(t) takes values in [0, 1] and is persistently exciting, i.e., there exist two positive constants μ, T such that, for every t ≥ 0, . In particular, when α(t) becomes zero the system dynamics switches to an uncontrollable system. In this paper, we address the following question: is it possible to find a linear time-invariant state-feedback u = Kx, with K only depending on (A, B) and possibly on μ, T, which globally asymptotically stabilizes the system? We give a positive answer to this question for two cases: when A is neutrally stable and when the system is the double integrator. Notation  A continuous function is of class , if it is strictly increasing and is of class if it is continuous, non-increasing and tends to zero as its argument tends to infinity. A function is said to be a class -function if, for any t ≥ 0, and for any s ≥ 0. We use |·| for the Euclidean norm of vectors and the induced L ₂-norm of matrices.     

Many-to-Many Communication in Radio Networks

Radio networks model wireless data communication when the bandwidth is limited to one wave frequency. The key restriction of such networks is mutual interference of packets arriving simultaneously at a node. The many-to-many (m2m) communication primitive involves p participant nodes from among n nodes in the network, where the distance between any pair of participants is at most d. The task is to have all the participants get to know all the input messages. We consider three cases of the m2m communication problem. In the ad-hoc case, each participant knows only its name and the values of n, p and d. In the partially centralized case, each participant knows the topology of the network and the values of p and d, but does not know the names of the other participants. In the centralized case, each participant knows the topology of the network and the names of all the participants. For the centralized m2m problem, we give deterministic protocols, for both undirected and directed networks, working in time, which is provably optimal. For the partially centralized m2m problem, we give a randomized protocol for undirected networks working in time with high probability (whp), and we show that any deterministic protocol requires time. For the ad-hoc m2m problem, we develop a randomized protocol for undirected networks that works in time whp. We show two lower bounds for the ad-hoc m2m problem. One lower bound states that any randomized protocol for the m2m ad hoc problem requires expected time. Another lower bound states that for any deterministic protocol for the m2m ad hoc problem, there is a network on which the protocol requires time when n−p(n)=Ω(n) and d>1, and that it requires Ω(n) time when n−p(n)=o(n). The results of this paper appeared in a preliminary form in “On many-to-many communication in packet radio networks” in Proceedings of the 10th Conference on Principles of Distributed Systems (OPODIS), Bordeaux, France, 2006, Lecture Notes in Computer Science 4305, Springer, Heidelberg, pp. 258–272. The work of B.S. Chlebus was supported by NSF Grant 0310503.     

Alternating time versus deterministic time: A separation

Paulet al. [12] proved that deterministic Turing machines can be speeded up by a factor of log*t (n) using four alternations; that is, DTIME(t(n) log*t(n)) σ₄(t(n)). Balcázaret al. [1] noted that two alternations are sufficient to achieve this speed-up of deterministic Turing machines; that is, DTIME(t(n) log*t(n)) Σ₂(t (n)). We supply a proof of this speed-up and using that show that for each time-constructible functiont(n), DTIME(t(n)) ⊂ Σ₂(t(n)); that is, two alternations are strictly more powerful than deterministic time. An important corollary is that at least one (or both) of the immediate generalizations of the result DTIME(n) ⊂ NTIME(n) [12] must be true: NTIME(n) ≠ co-NTIME(n) or, for each time-constructible functiont(n), DTIME(t (n)) ⊂ NTIME(t (n)). This work was supported in part by NSF Grant CCR-8909071. The preliminary version of the work was done when the author was a graduate student at The Ohio State University.     

Topology on the set of R 0 semantics for R 0 algebras

This paper introduces the concepts of R ₀ valuation, R ₀ semantic, countable R ₀ category , R ₀ fuzzy topological category , etc. It is established in a natural way that the fuzzy topology δ and its cut topology on the set Ω _M consisting of all R ₀ valuations of an R ₀ algebra M, and some properties of fuzzy topology δ and its cut topology are investigated carefully. Moreover, the representation theorem for R ₀ algebras by means of fuzzy topology is given, that is to say the category is equivalent to the category . By studying the relation between valuations and filters, the Loomis–Sikorski theorem for R ₀ algebras is obtained. As an application, K-compactness of the R ₀ logic is discussed.     

Combining the Perceptron Algorithm with Logarithmic Simulated Annealing

We present results of computational experiments with an extension of the Perceptron algorithm by a special type of simulated annealing. The simulated annealing procedure employs a logarithmic cooling schedule , where is a parameter that depends on the underlying configuration space. For sample sets S of n-dimensional vectors generated by randomly chosen polynomials , we try to approximate the positive and negative examples by linear threshold functions. The approximations are computed by both the classical Perceptron algorithm and our extension with logarithmic cooling schedules. For and , the extension outperforms the classical Perceptron algorithm by about 15% when the sample size is sufficiently large. The parameter was chosen according to estimations of the maximum escape depth from local minima of the associated energy landscape.      

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 .      

Approximation Algorithms for Multi-Criteria Traveling Salesman Problems

We analyze approximation algorithms for several variants of the traveling salesman problem with multiple objective functions. First, we consider the symmetric TSP (STSP) with γ-triangle inequality. For this problem, we present a deterministic polynomial-time algorithm that achieves an approximation ratio of and a randomized approximation algorithm that achieves a ratio of . In particular, we obtain a 2+ε approximation for multi-criteria metric STSP. Then we show that multi-criteria cycle cover problems admit fully polynomial-time randomized approximation schemes. Based on these schemes, we present randomized approximation algorithms for STSP with γ-triangle inequality (ratio ), asymmetric TSP (ATSP) with γ-triangle inequality (ratio ), STSP with weights one and two (ratio 4/3) and ATSP with weights one and two (ratio 3/2). A preliminary version of this work has been presented at the 4th Workshop on Approximation and Online Algorithms (WAOA 2006) (Lecture Notes in Computer Science, vol. 4368, pp. 302–315, 2007). B. Manthey is supported by the Postdoc-Program of the German Academic Exchange Service (DAAD). He is on leave from Saarland University and has done part of the work at the Institute for Theoretical Computer Science of the University of Lübeck supported by DFG research grant RE 672/3 and at the Department of Computer Science at Saarland University.     

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.     

Quantum Algorithms for Matching Problems

We present quantum algorithms for the following matching problems in unweighted and weighted graphs with n vertices and m edges:

Max-Stretch Reduction for Tree Spanners

A tree t-spanner T of a graph G is a spanning tree of G whose max-stretch is t, i.e., the distance between any two vertices in T is at most t times their distance in G. If G has a tree t-spanner but not a tree (t−1)-spanner, then G is said to have max-stretch of t. In this paper, we study the Max-Stretch Reduction Problem: for an unweighted graph G=(V,E), find a set of edges not in E originally whose insertion into G can decrease the max-stretch of G. Our results are as follows: (i) For a ring graph, we give a linear-time algorithm which inserts k edges improving the max-stretch optimally. (ii) For a grid graph, we give a nearly optimal max-stretch reduction algorithm which preserves the structure of the grid. (iii) In the general case, we show that it is -hard to decide, for a given graph G and its spanning tree of max-stretch t, whether or not one-edge insertion can decrease the max-stretch to t−1. (iv) Finally, we show that the max-stretch of an arbitrary graph on n vertices can be reduced to s′≥2 by inserting O(n/s′) edges, which can be determined in linear time, and observe that this number of edges is optimal up to a constant.     

On Division in Extreme and Mean Ratio and its Connection to a Particular Re-Expression of the Golden Quadratic Equation x 2 − x − 1 = 0

The golden quadratic x² − x − 1 = 0, when re-expressed as (x)(1) = 1/(x − 1), x = 1.618, can be interpreted as the algebraic expression of division in extreme and mean ratio (DEMR) of a line of length x = 1.618 into a longer section of length 1 and a smaller of length (x − 1). It can, however, also be interpreted as the formulation of the area of a golden rectangle of sides x = 1.618 and 1, and as the system of equations constituted by y =  x, and y = 1/(x − 1). Based on the well-known connection existing between the first two of these interpretations, the authors address the problem of finding out the thread connecting the golden rectangle with the system of equations referred to above. The results obtained indicate first that this system, like the golden rectangle, also carries in its geometry the essential traits of DEMR; and, second, that it implicitly subsumes the simpler rectangular geometry of its alternative interpretation. The process of developing these connections brought forward a heretofore apparently unreported golden trapezoid of sides Φ, 1, ϕ and .     

Parallel merging with restriction

In this paper, we study the merging of two sorted arrays and on EREW PRAM with two restrictions: (1) The elements of two arrays are taken from the integer range [1,n], where n=Max(n ₁,n ₂). (2) The elements are taken from either uniform distribution or non-uniform distribution such that , for 1≤i≤p (number of processors). We give a new optimal deterministic algorithm runs in time using p processors on EREW PRAM. For ; the running time of the algorithm is O(log ^(g) n) which is faster than the previous results, where log ^(g) n=log log ^(g−1) n for g>1 and log ⁽¹⁾ n=log n. We also extend the domain of input data to [1,n ^k ], where k is a constant.

Classifications of Dense Languages

Let X be a finite alphabet containing more than one letter. A dense language over X is a language containing a disjunctive language. A language L is an n-dense language if for any distinct n words there exist two words such that In this paper we classify dense languages into strict n-dense languages and study some of their algebraic properties. We show that for each n ≥ 0, the n-dense language exists. For an n-dense language L, n ≠ 1, the language L ∩ Q is a dense language, where Q is the set of all primitive words over X. Moreover, for a given n ≥ 1, the language L is such that , then for some m, n ≤ m ≤ 2n + 1. Characterizations on 0-dense languages and n-dense languages are obtained. It is true that for any dense language L, there exist such that for some. We show that everyn-dense language, n ≥ 0, can be split into disjoint union of infinitely many n-dense languages.