On the complexity of global computation in the presence of link failures: the general case

Summary This paper presents (m logn) and (mn) messages lower bounds on the problem of computing a gobal sensitive function in biderectional networks with link failures (i.e., dynamically changing topology), wheren andm are the total number of nodes and links in the network. The (m logn) lower bound is under the assumption thatn is a-priori known to the nodes, while the second bound is for the case in which such knowledge is not available. A global sensitive function ofn variables is a function that may not be computed without the knowledge of the values of all then variables (e.g. maximum, sum, etc). Thus, computing such a function at one node of a distributed network requires this node to communicate with every other node in the network. Though lower bounds higher than (m) messages are known for this problem in the context of link failures, none holds for dense bidirectional networks. Moreover, we are not aware of any other nontrivial lower bound higher than (m) for dense bidirectional networks. Yehuda Afek received a B.Sc. in Electrical Engineering from the Technion and an M.Sc. and Ph.D. in Computer Science from the University of California, Los-Angeles. In 1985 he joined the Distributed Systems Research Department in AT&T Bell Laboratories as a Member of Technical Staff. In 1988 he joined the Computer Science Department in Tel-Aviv University, where he now holds a permanent position. From 1989 to 1994 he was also a consultant for AT&T Bell Laboratories. His interests include communication protocols, distributed computing and asynchronous shared memory systems. Danny Hendler was born in Kiryat-Haim near Haifa, Israel, on April 17th 1961. He received his B.Sc. and M.Sc. in Computer Science from Tel-Aviv University, Israel, in 1986 and 1993, respectively. In the past 8 years he has worked as a free lance software-consultant, specializing mainly in communication, telephony and voice-mail applications.     

The optimal read-once branching program complexity for the direct storage access function

Branching programs are computation models measuring the space of (Turing machine) computations. Read-once branching programs (BP1s) are the most general model where each graph-theoretical path is the computation path for some input. Exponential lower bounds on the size of read-once branching programs are known since a long time. Nevertheless, there are only few functions where the BP1 size is asymptotically known exactly. In this paper, the exact BP1 size of a fundamental function, the direct storage access function, is determined.     

A note on monotone complexity and the rank of matrices

We shall give simpler proofs of some lower bounds on monotone computations. We describe a simple condition on combinatorial structures, such that the rank of the matrix associated with these structures gives lower bounds on monotone span program size and monotone formula size. We also prove an upper bound on the rank of the corresponding matrices, and show that such structures can be constructed from self-avoiding families. As a corollary, we obtain an upper bound on the size of self-avoiding families, which solves a problem posed by Babai and Gál [Combinatorica 19 (3) (1999) 301-319].     

Randomized function evaluation on a ring

LetR be a unidirectional asynchronous ring ofn identical processors each with a single input bit. Letf be any cyclic nonconstant function ofn boolean variables. Moran and Warmuth (1986) prove that anydeterministic algorithm that evaluatesf onR has communication complexity (n logn) bits. They also construct a family of cyclic nonconstant boolean functions that can be evaluated inO(n logn) bits by a deterministic algorithm.This contrasts with the following new results:

Computational complexity of distributed detection problems with information constraints

For a system consisting of a set of sensors S = {S₁, S₂, …, S_m} and a set of objects O = {O₁, O₂, …, O_n}, there are information constraints given by a relation R S × O such that (S_i, O_j) R if and only if S_i is capable of detecting O_j. Each (S_i, O_j) R is assigned a confidence factor (a positive real number) which is either explicitly given or can be efficiently computed. Given that a subset of sensors have detected obstacles, the detection problem is to identify a subset H O with the maximum confidence value. The computational complexity of the detection problem, which depends on the nature of the confidence factor and the information constraints, is the main focus of this paper. This problem exhibits a myriad of complexity levels ranging from a worst-case exponential (in n) lower bound in a general case to an O(m + n) time solvability. We show that the following simple versions of a detection problem are computationally intractable: (a) deterministic formulation, where confidence factors are either 0 or 1; (b) uniform formulation where (S_i, O_j) R, for all S_i S, O_j O; (c) decomposable systems under multiplication operation. We then show that the following versions are solvable in polynomial (in n) time: (a) single object detection; (b) probabilistically independent detection; (c) decomposable systems under additive and nonfractional multiplicative measures; and (d) matroid systems.     

A simple proof of the uniform consensus synchronous lower bound

We give a simple and intuitive proof of an f+2 round lower bound for uniform consensus. That is, we show that for every uniform consensus algorithm tolerating t failures, and for every f?t−2, there is an execution with f failures that requires f+2 rounds.     

Stabilizing data-link over non-FIFO channels with optimal fault-resilience

Self-stabilizing systems have the ability to converge to a correct behavior when started in any configuration. Most of the work done so far in the self-stabilization area assumed either communication via shared memory or via FIFO channels.This paper is the first to lay the bases for the design of self-stabilizing message passing algorithms over unreliable non-FIFO channels. We propose an optimal stabilizing data-link layer that emulates a reliable FIFO communication channel over unreliable capacity bounded non-FIFO channels (the channel capacity is known to the protocol).     

Lower bounds for the non-linear complexity of algebraic computation trees with integer inputs

Andrew Yao proved some lower bounds for algebraic computation trees with integer inputs. In his key result he proved bounds on the number of components of the leaf space of a homogeneous decision tree derived from a computation tree. In this paper we present a shorter and more conceptual proof. We introduce the concept of aregulated tree as a generalization of a regular tree which has the advantage of allowing the same lower bounds on the non-linear portion of the complexity. The proof is an application of a result of Ben-Or.     

Partition arguments in multiparty communication complexity

Consider the “Number in Hand” multiparty communication complexity model, where k players holding inputs x₁,…,x_k∈{0,1}ⁿ communicate to compute the value f(x₁,…,x_k) of a function f known to all of them. The main lower bound technique for the communication complexity of such problems is that of partition arguments: partition the k players into two disjoint sets of players and find a lower bound for the induced two-party communication complexity problem.In this paper, we study the power of partition arguments. Our two main results are very different in nature:

(i)

For randomized communication complexity, we show that partition arguments may yield bounds that are exponentially far from the true communication complexity. Specifically, we prove that there exists a 3-argument function f whose communication complexity is Ω(n), while partition arguments can only yield an Ω(logn) lower bound. The same holds for nondeterministiccommunication complexity.

(ii)

For deterministic communication complexity, we prove that finding significant gaps between the true communication complexity and the best lower bound that can be obtained via partition arguments, would imply progress on a generalized version of the “log-rank conjecture” in communication complexity. We also observe that, in the case of computing relations (search problems), very large gaps do exist.

We conclude with two results on the multiparty “fooling set technique”, another method for obtaining communication complexity lower bounds.     

The complexity of updating snapshot objects

This paper proves Ω(m) lower bounds on the step complexity of UPDATE operations for space-optimal wait-free implementations of an m-component snapshot object from historyless objects. These lower bounds follow from lower bounds for a new, more general class of implementations from base objects of any type. This work extends a similar lower bound by Israeli and Shirazi for implementations of m-component single-writer snapshot objects from single-writer registers.     

Larger lower bounds on the OBDD complexity of integer multiplication

Integer multiplication as one of the basic arithmetic functions has been in the focus of several complexity theoretical investigations and ordered binary decision diagrams (OBDDs) are one of the most common dynamic data structures for Boolean functions. Recently, the question whether the OBDD complexity of the most significant bit of integer multiplication is exponential has been answered affirmatively. In this paper a larger general lower bound is presented using a simpler proof. Furthermore, we prove a larger lower bound for the variable order assumed to be one of the best ones for the most significant bit. Moreover, the best known lower bound on the OBDD complexity for the so-called graph of integer multiplication is improved.     

On the message complexity of binary byzantine agreement under crash failures

Summary The binary Byzantine Agreement problem requiresn–1 receivers to agree on the binary value broadcast by a sender even when some of thesen processes may be faulty. We investigate the message complexity of protocols that solve this problem in the case of crash failures. In particular, we derive matching upper and lower bounds on the total, worst and average case number of meassages needed in the failure-free executions of such protocols.More specifically, we prove that any protocol that tolerates up tot faulty processes requires a total of at leastn+t–1 messages in its failure-free executions —and, therefore, at least [(n+t–1)/2] messages in the worst case and min (P ₀,P ₁)·(n+t–1) meassages in the average case, whereP _v is the probability that the value of the bit that the sender wants to broadcast isv. We also give protocols that solve the problem using only the minimum number of meassages for these three complexity measures. These protocols can be implemented by using 1-bit messages. Since a lower bound on the number of messages is also a lower bound on the number of meassage bits, this means that the above tight bounds on the number of messages are also tight bounds on the number of meassage bits. Vassos Hadzilacos received a BSE from Princeton University in 1980 and a PhD from Harvard University in 1984, both in Computer Science. In 1984 he joined the Department of Computer Science at the University of Toronto where he is currently an Associate Professor. In 1990–1991 he was visiting Associate Professor in the Department of Computer Science at Cornell University. His research interests are in the theory of distributed systems. Eugene Amdur obtained a B. Math from the University of Waterloo in 1986 and a M.Sc. from the University of Toronto in 1988. He is currently employed by the Vision and Robotics group at the University of Toronto in both technical and research capacities. His current areas of interest are vision, robotics, and networking. Samuel Weber received his B.Sc. in Mathematics and Computer Science and his M.Sc. in Computer Science from the University of Toronto. Currently, he is at Cornell University as a Ph.D. student in Computer Science with a minor in Psychology. His research interests include distributed systems, and the semantics of programming languages.     

On the complexity of computation in the presence of link failures: the case of a ring

Summary We investigate the message complexity of distributed computations on rings of asynchronous processors. In such computations, each processor has an initial local value and the task is to compute some predetermined function of all local values. Our work deviates from previous works concerning the complexity of ring computations in that we consider the effect oflink failures. A link is said to fail if some message sent through it never reaches its destination. We show that the message complexity of any function, which is sensitive to all its inputs, is (n logn) whenn, the number of processors, is a-priori known; and is (n ² ) whenn is not known. Interestingly, these tight bounds do not depend on whether the identity of a leader is a-priori known before the computation starts. These results stand in sharp contrast to the situation in asynchronous rings with no link failures, where the message complexity is affected by the a-priori knowledge of a leader but is not affected by the knowledge ofn. Oded Goldreich was born in Tel-Aviv, Israel, on February 4th 1957. Received B.A., M.Sc., and D.Sc. in Computer Science from the Technion — Israel Institute of Technology, Haifa, Israel, in 1980, 1982, and 1983, respectively. He is currently an Associate Professor of Computer Science in the Technion. From 1983 to 1986, he was a postdoctoral fellow in MIT's Laboratory for Computer Science. His research interests include cryptography and related areas, relation between randomness and algorithms, and distributed computation. Luiba Shrira was born in Vilnius, Lithuania. Received B.A., M.Sc., and D.Sc. in Computer Science from the Technion—Israel Institute of Technology, Haifa, Israel in 1977, 1980, and 1985, respectively. from 1986 to 1989 she was a postdoctoral fellow at Laboratory for Computer science at MIT, where she is currently a Research Associate. Her research interests include highly-available and reliable distributed algorithms and systems, persistent object systems, and programming methodology.Part of the work has been done while the first author was in the Laboratory for Computer Science of MIT and the second author was in the Computer Science Department of the Technion. First author was partially supported by a Weizmann Postdoctoral Fellowship, an IBM Postdoctoral Fellowship, and Albert Einstein Research Fund (through Technion's V.P.R. Fund)     

On the OBDD complexity of the most significant bit of integer multiplication

Integer multiplication as one of the basic arithmetic functions has been in the focus of several complexity theoretical investigations. Ordered binary decision diagrams (OBDDs) are one of the most common dynamic data structures for boolean functions. Among the many areas of application are verification, model checking, computer-aided design, relational algebra, and symbolic graph algorithms. In this paper it is shown that the OBDD complexity of the most significant bit of integer multiplication is exponential answering an open question posed by Wegener (2000) [18].     

The complexity of changing colourings with bounded maximum degree

Let G be a graph, x,y∈V(G), and ?:V(G)→[k] a k-colouring of G such that ?(x)=?(y). If then the following question is NP-complete: Does there exist a k-colouring ?^′ of G such that ?^′(x)≠?^′(y)? Conversely, if then the problem is polynomial time.     

Exponential space complexity for OBDD-based reachability analysis

Ordered binary decision diagrams (OBDDs) are one of the most common dynamic data structures for Boolean functions. Nevertheless, many basic graph problems are known to be PSPACE-hard if their input graphs are represented by OBDDs. Computing the set of nodes that are reachable from some source s∈V in a digraph G=(V,E) is an important problem in computer-aided design, hardware verification, and model checking. Until now only exponential lower bounds on the space complexity of a restricted class of OBDD-based algorithms for the reachability problem have been known. Here, the result is extended by presenting an exponential lower bound for the general reachability problem. As a by-product a general exponential lower bound is obtained for the computation of OBDDs representing all connected node pairs in a graph, the transitive closure.     

A tight lower bound for job scheduling with cancellation

The Job Scheduling with Cancellation problem is a variation of classical scheduling problems in which jobs can be cancelled while waiting for execution. In this paper we prove a tight lower bound of 5 for the competitive ratio of any deterministic online algorithm for this problem, for the case where all jobs have the same processing time.     

Dynamic FTSS in asynchronous systems: The case of unison

Distributed fault-tolerance can mask the effect of a limited number of permanent faults, while self-stabilization provides forward recovery after an arbitrary number of transient faults hit the system. FTSS (Fault-Tolerant Self-Stabilizing) protocols combine the best of both worlds since they tolerate simultaneously transient and (permanent) crash faults. To date, deterministic FTSS solutions either consider static (i.e. fixed point) tasks, or assume synchronous scheduling of the system components.In this paper, we present the first study of deterministic FTSS solutions for dynamic tasks in asynchronous systems, considering the unison problem as a benchmark. Unison can be seen as a local clock synchronization problem as neighbors must maintain digital clocks at most one time unit away from each other, and increment their own clock value infinitely often. We present several impossibility results for this difficult problem and propose an FTSS solution (when the problem is solvable) for the state model that exhibits optimal fault-containment.