Lower bound for scalable Byzantine Agreement

We consider the problem of computing Byzantine Agreement in a synchronous network with n processors, each with a private random string, where each pair of processors is connected by a private communication line. The adversary is malicious and non-adaptive, i.e., it must choose the processors to corrupt at the start of the algorithm. Byzantine Agreement is known to be computable in this model in an expected constant number of rounds. We consider a scalable model where in each round each uncorrupt processor can send to any set of log n other processors and listen to any set of log n processors. We define the loss of an execution to be the number of uncorrupt processors whose output does not agree with the output of the majority of uncorrupt processors. We show that if there are t corrupt processors, then any randomised protocol which has probability at least 1/2 + 1/ logn of loss less than requires at least f rounds. This also shows that lossless protocols require both rounds, and for at least one uncorrupt processor to send messages during the protocol.     

Time efficient k-shot broadcasting in known topology radio networks

The paper considers broadcasting protocols in radio networks with known topology that are efficient in both time and energy. The radio network is modelled as an undirected graph G = (V, E) where |V| = n. It is assumed that during execution of the communication task every node in V is allowed to transmit at most once. Under this assumption it is shown that any radio broadcast protocol requires transmission rounds, where D is the diameter of G. This lower bound is complemented with an efficient construction of a deterministic protocol that accomplishes broadcasting in rounds. Moreover, if we allow each node to transmit at most k times, the lower bound on the number of transmission rounds holds. We also provide a randomised protocol that accomplishes broadcasting in rounds. The paper concludes with a number of open problems in the area. The research of L. Gąsieniec, D.R. Kowalski and C. Su supported in part by the Royal Society grant Algorithmic and Combinatorial Aspects of Radio Communication, IJP - 2006/R2. The research of E. Kantor and D. Peleg supported in part by grants from the Minerva Foundation and the Israel Ministry of Science.     

Renaming in synchronous message passing systems with Byzantine failures

We study the renaming problem in a fully connected synchronous network with Byzantine failures. We show that when the original namespace of the processors is unbounded, this problem cannot be solved in an a priori bounded number of rounds for , where n is the size of the network and t is the number of failures. On the other hand, for n > 3t, we present a Byzantine renaming algorithm that runs in O(lg n) rounds. In addition, we present a fast, efficient strong renaming algorithm for n > t, which runs in rounds, where N ₀ is the value of the highest identifier among all the correct processors.     

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.     

Optimal Deterministic Broadcasting in Known Topology Radio Networks

We consider deterministic broadcasting in radio networks whose nodes have full topological information about the network. The aim is to design a polynomial algorithm, which, given a graph G with source s, produces a fast broadcast scheme in the radio network represented by G. The problem of finding a fastest broadcast scheme for a given graph is NP-hard, hence it is only possible to get an approximation algorithm. We give a deterministic polynomial algorithm which produces a broadcast scheme of length , for every n-node graph of diameter D, thus improving a result of Gąsieniec et al. (PODC 2005) [17] and solving a problem stated there. Unless the inclusion NP BPTIME( holds, the length of a polynomially constructible deterministic broadcast scheme is optimal.A preliminary version of this paper (with a weaker result) appeared in the Proc. 7th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX’2004), August 2004, Harvard University, Cambridge, USA, LNCS 3122, 171–182. Research of the second author supported in part by NSERC discovery grant and by the Research Chair in Distributed Computing of the Université du Québec en Outaouais. Part of this work was done during the second author’s visit at the Max-Planck-Institut für Informatik.     

Simple a posteriori error estimators for the <Emphasis Type="Italic">h</Emphasis>-version of the boundary element method

The h-h/2-strategy is one well-known technique for the a posteriori error estimation for Galerkin discretizations of energy minimization problems. One considers to estimate the error , where is a Galerkin solution with respect to a mesh and is a Galerkin solution with respect to the mesh obtained from a uniform refinement of . This error estimator is always efficient and observed to be also reliable in practice. However, for boundary element methods, the energy norm is non-local and thus the error estimator η does not provide information for a local mesh-refinement. We consider Symm’s integral equation of the first kind, where the energy space is the negative-order Sobolev space . Recent localization techniques allow to replace the energy norm in this case by some weighted L ²-norm. Then, this very basic error estimation strategy is also applicable to steer an h-adaptive algorithm. Numerical experiments in 2D and 3D show that the proposed method works well in practice. A short conclusion is concerned with other integral equations, e.g., the hypersingular case with energy space and , respectively, or a transmission problem. Dedicated to Professor Ernst P. Stephan on the occasion of his 60th birthday.     

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 .     

Quantum Error Correction of Time-correlated Errors

The complexity of the error correction circuitry forces us to design quantum error correction codes capable of correcting a single error per error correction cycle. Yet, time-correlated error are common for physical implementations of quantum systems; an error corrected during the previous cycle may reoccur later due to physical processes specific for each physical implementation of the qubits. In this paper, we study quantum error correction for a restricted class of time-correlated errors in a spin-boson model. The algorithm we propose allows the correction of two errors per error correction cycle, provided that one of them is time-correlated. The algorithm can be applied to any stabilizer code when the two logical qubits and are entangled states of 2 ⁿ basis states in .      

A Novel Class of Symmetric and Nonsymmetric Periodizing Variable Transformations for Numerical Integration

Variable transformations for numerical integration have been used for improving the accuracy of the trapezoidal rule. Specifically, one first transforms the integral via a variable transformation that maps [0,1] to itself, and then approximates the resulting transformed integral by the trapezoidal rule. In this work, we propose a new class of symmetric and nonsymmetric variable transformations which we denote , where r and s are positive scalars assigned by the user. A simple representative of this class is . We show that, in case , or but has algebraic (endpoint) singularities at x = 0 and/or x = 1, the trapezoidal rule on the transformed integral produces exceptionally high accuracies for special values of r and s. In particular, when and we employ , the error in the approximation is (i) O(h ^r ) for arbitrary r and (ii) O(h ^2r ) if r is a positive odd integer at least 3, h being the integration step. We illustrate the use of these transformations and the accompanying theory with numerical examples.      

Fuzzy logic models in a category of fuzzy relations

We investigate interpretations of formulas ψ in a first order fuzzy logic in models which are based on objects of a category SetR(Ω) which consists of Ω-sets, i.e. sets with similarity relations with values in a complete MV-algebra Ω and with morphisms defined as special fuzzy relations between Ω-sets. The interpretations are then morphisms in a category SetR(Ω) from some Ω-set to the object . We define homomorphisms between models in a category SetR(Ω) and we prove that if is a (special) homomorphism of models in a category SetR(Ω) then there is a relation between interpretations of a formula ψ in models . Supported by MSM6198898701, grant 201/07/0191 of GAČR and grant 1M0572.     

A simple population protocol for fast robust approximate majority

We describe and analyze a 3-state one-way population protocol to compute approximate majority in the model in which pairs of agents are drawn uniformly at random to interact. Given an initial configuration of x’s, y’s and blanks that contains at least one non-blank, the goal is for the agents to reach consensus on one of the values x or y. Additionally, the value chosen should be the majority non-blank initial value, provided it exceeds the minority by a sufficient margin. We prove that with high probability n agents reach consensus in O(n log n) interactions and the value chosen is the majority provided that its initial margin is at least . This protocol has the additional property of tolerating Byzantine behavior in of the agents, making it the first known population protocol that tolerates Byzantine agents.     

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.     

On the Relation between States and Maps in Infinite Dimensions

Relations between states and maps, which are known for quantum systems in finitedimensional Hilbert spaces, are formulated rigorously in geometrical terms with no use of coordinate (matrix) interpretation. In a tensor product realization they are represented simply by a permutation of factors. This leads to natural generalizations for infinite-dimensional Hilbert spaces and a simple proof of a generalized Choi Theorem. The natural framework is based on spaces of Hilbert-Schmidt operators and the corresponding tensor products of Hilbert spaces. It is proved that the corresponding isomorphisms cannot be naturally extended to compact (or bounded) operators, nor reduced to the trace-class operators. On the other hand, it is proven that there is a natural continuous map from trace-class operators on (with the nuclear norm) into compact operators mapping the space of all bounded operators on into trace class operators on (with the operator-norm). Also in the infinite-dimensional context, the Schmidt measure of entanglement and multipartite generalizations of state-maps relations are considered in the paper.     

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.     

t-norms induced by metrics on Boolean algebras

Let d _ν be the metric associated with a strictly positive submeasure ν on some Boolean algebra . If d _ν is bounded from above by 1, E _ν=1−d _ν is a (fuzzy) similarity relation on at least w.r.t. the Lstrok ukasiewicz t-norm, but possibly also w.r.t. numerous further t-norms.In this paper, we show that under certain assumptions on and ν, we may associate with ν in a natural way a continuous t-norm w.r.t. which E _ν is a similarity relation and which, in a certain sense, is the weakest such t-norm. Up to isomorphism, every continuous t-norm arises in this way     

Factor congruences in BCK-algebras

In this paper, we characterize factor congruences in the quasivariety of BCK-algebras. As an application we prove that the free algebra over an infinite set of generators is indecomposable in any subvariety of BCK-algebras. We also study the decomposability of free algebras in the variety of hoop residuation algebras and its subvarieties. We prove that free algebras in a non k-potent subvariety of are indecomposable while finitely generated free algebras in k-potent subvarieties have a unique non-trivial decomposition into a direct product of two factors, and one of them is the two-element implication algebra. This paper is partially supported by Universidad Nacional del Sur and CONICET.     

Asymptotic Fourier Coefficients for a C∞ Bell (Smoothed-“Top-Hat”) & the Fourier Extension Problem

In constructing local Fourier bases and in solving differential equations with nonperiodic solutions through Fourier spectral algorithms, it is necessary to solve the Fourier Extension Problem. This is the task of extending a nonperiodic function, defined on an interval , to a function which is periodic on the larger interval . We derive the asymptotic Fourier coefficients for an infinitely differentiable function which is one on an interval , identically zero for , and varies smoothly in between. Such smoothed “top-hat” functions are “bells” in wavelet theory. Our bell is (for x ≥ 0) where where . By applying steepest descents to approximate the coefficient integrals in the limit of large degree j, we show that when the width L is fixed, the Fourier cosine coefficients a _j of on are proportional to where Λ(j) is an oscillatory factor of degree given in the text. We also show that to minimize error in a Fourier series truncated after the Nth term, the width should be chosen to increase with N as . We derive similar asymptotics for the function f(x)=x as extended by a more sophisticated scheme with overlapping bells; this gives an even faster rate of Fourier convergence