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.     

Compact separator decompositions in dynamic trees and applications to labeling schemes

This paper presents an efficient scheme maintaining a separator decomposition representation in dynamic trees using asymptotically optimal labels. In order to maintain the short labels, the scheme uses relatively low message complexity. In particular, if the initial dynamic tree contains only the root, then the scheme incurs an O(log⁴ n) amortized message complexity per topology change, where n is the current number of vertices in the tree. As a separator decomposition is a fundamental decomposition of trees used extensively as a component in many static graph algorithms, our dynamic scheme for separator decomposition may be used for constructing dynamic versions to these algorithms. The paper then shows how to use our dynamic separator decomposition to construct efficient labeling schemes on dynamic trees, using the same message complexity as our dynamic separator scheme. Specifically, we construct efficient routing schemes on dynamic trees, for both the designer and the adversary port models, which maintain optimal labels, up to a multiplicative factor of O(log log n). In addition, it is shown how to use our dynamic separator decomposition scheme to construct dynamic labeling schemes supporting the ancestry and NCA relations using asymptotically optimal labels, as well as to extend a known result on dynamic distance labeling schemes. Supported in part at the Technion by an Aly Kaufman fellowship. Supported in part by a grant from the Israel Science Foundation.     

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.     

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.     

Translational lemmas for DLOGTIME-uniform circuits,alternating TMs,and PRAMs

We present translational lemmas for the three standard models of parallel computation, and apply them to obtain tight hierarchy results. It is shown that, for arbitrarily small rational constant , (i) there is a language which can be accepted by a -uniform circuit family of depth and size but not by any -uniform circuit family of depth and size , (ii) there is a language which can be accepted by a -time -space ATM with l worktapes but not by any -time -space ATM with the same l worktapes if the number of tape symbols is fixed, and (iii) there is a language which can be accepted by a -time PRAM with processors but not by any -time PRAM with processors. Here, c > 0, d ≥ 1, r ₁ > 1, and r ₂ ≥ 1 are arbitrary rational constants, and l ≥ 2 is an arbitrary integer. Preliminary versions of different parts of this paper appeared in Proc. MCU 2004 (LNCS 3354) and Proc. FCT 2005 (LNCS 3623).     

Snap-stabilization and PIF in tree networks

The contribution of this paper is threefold. First, we present the paradigm of snap-stabilization. A snap- stabilizing protocol guarantees that, starting from an arbitrary system configuration, the protocol always behaves according to its specification. So, a snap-stabilizing protocol is a time optimal self-stabilizing protocol (because it stabilizes in 0 rounds). Second, we propose a new Propagation of Information with Feedback (PIF) cycle, called Propagation of Information with Feedback and Cleaning (). We show three different implementations of this new PIF. The first one is a basic cycle which is inherently snap-stabilizing. However, the first PIF cycle can be delayed O(h ²) rounds (where h is the height of the tree) due to some undesirable local states. The second algorithm improves the worst delay of the basic algorithm from O(h ²) to 1 round. The state requirement for the above two algorithms is 3 states per processor, except for the root and leaf processors that use only 2 states. Also, they work on oriented trees. We then propose a third snap-stabilizing PIF algorithm on un-oriented tree networks. The state requirement of the third algorithm depends on the degree of the processors, and the delay is at most h rounds. Next, we analyze the maximum waiting time before a PIF cycle can be initiated whether the PIF cycle is infinitely and sequentially repeated or launch as an isolated PIF cycle. The analysis is made for both oriented and un-oriented trees. We show or conjecture that the two best of the above algorithms produce optimal waiting time. Finally, we compute the minimal number of states the processors require to implement a single PIF cycle, and show that both algorithms for oriented trees are also (in addition to being time optimal) optimal in terms of the number of states. WARNING: The concept of snap-stabilization was first introduced in [12]. The concept evolved over the last eight years. We take this evolution in consideration in this paper, which includes the early results published in [10] and [12]. In particular, infinite repetition of computation cycles is a requirement of self-stabilizing systems. This is not required in snap-stabilization because snap-stabilization ensures that the first completed computation cycle is executed according to the specification of the problem. The correctness proofs conform to this basic property.     

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.      

Labeling Schemes for Dynamic Tree Networks

Distance labeling schemes are composed of a marker algorithm for labeling the vertices of a graph with short labels, coupled with a decoder algorithm allowing one to compute the distance between any two vertices directly from their labels (without using any additional information). As applications for distance labeling schemes concern mainly large and dynamically changing networks, it is of interest to study distributed dynamic labeling schemes. The current paper considers the problem on dynamic trees, and proposes efficient distributed schemes for it. The paper first presents a labeling scheme for distances in the dynamic tree model, with amortized message complexity O(log² n) per operation, where n is the size of the tree at the time the operation takes place. The protocol maintains O(log² n) bit labels. This label size is known to be optimal even in the static scenario. A more general labeling scheme is then introduced for the dynamic tree model, based on extending an existing static tree labeling scheme to the dynamic setting. The approach fits a number of natural tree functions, such as distance, separation level, and flow. The main resulting scheme incurs an overhead of an O(log n) multiplicative factor in both the label size and amortized message complexity in the case of dynamically growing trees (with no vertex deletions). If an upper bound on n is known in advance, this method yields a different tradeoff, with an O(log² n/log log n) multiplicative overhead on the label size but only an O(log n/log log n) overhead on the amortized message complexity. In the fully dynamic model the scheme also incurs an increased additive overhead in amortized communication, of O(log² n) messages per operation.     

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.     

Population Variance under Interval Uncertainty: A New Algorithm

In statistical analysis of measurement results, it is often beneficial to compute the range V of the population variance when we only know the intervals of possible values of the x_i. In general, this problem is NP-hard; a polynomialtime algorithm is known for the case when the measurements are sufficiently accurate, i.e., when for all In this paper, we show that we can efficiently compute V under a weaker (and more general) condition .     

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     

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.     

Generalized fuzzy filters of <Emphasis Type="Italic">R</Emphasis><Subscript>0</Subscript>-algebras

In this paper, we introduce the notions of interval valued -fuzzy filters and interval valued -fuzzy Boolean (implicative) filters in R ₀-algebras and investigate some of their related properties. Some characterization theorems of these generalized fuzzy filters are derived. In particular, we prove that an interval valued fuzzy set F in R ₀-algebras is an interval valued -fuzzy Boolean filter if and only if it is an interval valued -fuzzy implicative filter.     

On the possibility of practically obfuscating programs towards a unified perspective of code protection

Barak et al. gave a first formalization of obfuscation, describing an obfuscator as an efficient, probabilistic “compiler” that takes in input a program P and produces a new program that has the same functionality as P but is unintelligible. This means that any result an obfuscated program can compute is actually computable given only an input/output access (called oracle access) to the program P: we call such results trivial results. On the basis of this informal definition, they suggest a formal definition of obfuscation based on oracle access to programs and show that no obfuscator can exist according to this definition. They also try to relax the definition and show that, even with a restriction to some common classes of programs, there exists no obfuscator. In this work, we show that their definition is too restrictive and lacks a fundamental property, that we formalize by the notion of oracle programs. Oracle programs are an abstract notion which basically refers to perfectly obfuscated programs. We suggest a new definition of obfuscation based on these oracle programs and show that such obfuscators do not exist either. Considering the actual implementations of “obfuscators”, we define a new kind of obfuscators, -obfuscators. These are obfuscators that hide non trivial results at least for time . By restricting the -requirement to deobfuscation (that is outputting an intelligible program when fed with an obfuscated program in input), we show that such obfuscators do exist. Practical -obfuscation methods are presented at the end of this paper: we focus more specifically on code protection techniques in a malware context. Based on the fact that a malware may fulfill its action in an amount of time which may be far larger than the analysis time of any automated detection program, these obfuscation methods can be considered as efficient enough to greatly thwart automated analysis and put check on any antivirus software. This research has been conducted while on stay at the Laboratoire de virologie et de cryptologie.     

On the complexity of graph self-assembly in accretive systems

We study the complexity of the Accretive Graph Assembly Problem (). An instance of consists of an edge-weighted graph G, a seed vertex in G, and a temperature τ. The goal is to determine if the graph G can be assembled by a sequence of vertex additions starting from the seed vertex. The edge weights model the forces of attraction and repulsion, and determine which vertices can be added to a partially assembled graph at the given temperature. A vertex can be added when the total weight to its already built neighbors in the graph is at least τ. The assembly process is sequential meaning that only one vertex can be added at a time. Our first result is that is NP-complete even on planar graphs with maximum degree 3 when edges have only two different types of weights. This resolves the complexity of in the sense that the problem is poly-time solvable when either the maximum degree is at most 2 or the number of distinct edge weights is one, and is NP-complete otherwise. Our second result is a dichotomy theorem that completely characterizes the complexity of on graphs with maximum degree 3 and two distinct weights: w _p and w _n . We give a simple system of linear constraints on w _p , w _n , and τ that determines whether the problem is NP-complete or is poly-time solvable. In the process of establishing this dichotomy, we give a poly-time algorithm to solve a non-trivial class of Finally, we consider the optimization version of where the goal is to assemble a largest-possible induced subgraph of the given input graph. We show that even on graphs that can be assembled and have maximum degree 3, it is NP-hard to assemble a (1/n ^1-ε)-fraction of the input graph for any here n denotes the number of vertices in G.     

Computing Population Variance and Entropy under Interval Uncertainty: Linear-Time Algorithms

In statistical analysis of measurement results it is often necessary to compute the range of the population variance when we only know the intervals of possible values of the x _i . While can be computed efficiently, the problem of computing is, in general, NP-hard. In our previous paper “Population Variance under Interval Uncertainty: A New Algorithm” (Reliable Computing 12 (4) (2006), pp. 273–280) we showed that in a practically important case we can use constraints techniques to compute in time O(n · log(n)). In this paper we provide new algorithms that compute (in all cases) and (for the above case) in linear time O(n). Similar linear-time algorithms are described for computing the range of the entropy when we only know the intervals of possible values of probabilities p _i . In general, a statistical characteristic ƒ can be more complex so that even computing ƒ can take much longer than linear time. For such ƒ, the question is how to compute the range in as few calls to ƒ as possible. We show that for convex symmetric functions ƒ, we can compute in n calls to ƒ.