International Journal of Foundations of Computer Science

A key issue in performing tree structured parallel computations is to distribute process components of a parallel program over processors in a parallel computer at run time such that both the maximum load and dilation are minimized. The main contribution of this paper is the application of recurrence relations in studying the performance of a dynamic tree embedding algorithm in hypercubes. We develop recurrence relations that characterize the expected load in randomized tree embeddings where, a tree grows by letting its nodes to take random walks of short distance. By using these recurrence relations, we are able to calculate the expected load on each processor. Therefore, for constant dilation embeddings, we are able to evaluate expected loads numerically and analytically. The applicability of recurrence relations is due to the recursive structure of trees and the fact that embeddings of the subtrees of a process node are independent of each other. Our methodology does not depend on the hypercube topology. Hence, it can be applied to studying dynamic tree growing in other networks.

We propose a completely general, informed randomized dynamic load balancing method called random seeking (RS) suitable for parallel algorithms with characteristics found in many search algorithms used in artificial intelligence and operations research and many divide-and-conquer algorithms. In it, source processors randomly seek out sink processors for load balancing by flinging "probe" messages. These probes not only locate sinks, but also collect load distribution information which is used to efficiently regulate load balancing activities. We empirically compare RS with a well-known randomized dynamic load balancing method, the random communication (RC) strategy, by using them in parallel best-first branch-and-bound algorithms on up to 512 processors of a parallel system. We find that the RC execution times are more than those of RS by 16–67% when used to perform combined dynamic quantitative and qualitative load balancing, and by 9–74% when used to perform only dynamic quantitative load balancing.

We introduce a new model of random graphs, that of random regular graphs with edge faults (which we denote by ), obtained by selecting the edges of a random member of the set of all regular graphs of degree r independently and with probability p. We can thus represent a communication network in which the links fail independently and with probability f =1-p.

In order to deal with this new model, we extend the notion of configurations and the translation lemma between configurations and random regular graphs provided by B. Bollobás, by introducing the concept of random configurations, to account for edge faults, and by providing an extended translation lemma between random configurations and graphs.

We investigate important connectivity properties of by estimating the ranges of r, f for which, with high probability, graphs a) are highly connected b) become disconnected and c) admit a giant connected component of small diameter.

A secret sharing scheme is a method which allows a dealer to share a secret among a set of participants in such a way that only qualified subsets of participants can recover the secret. The collection of subsets of participants that can reconstruct the secret in this way is called access structure. The rank of an access structure is the maximum cardinality of a minimal qualified subset. A secret sharing scheme is perfect if unqualified subsets of participants obtain no information regarding the secret. The dealer's randomness is the number of random bits required by the dealer to setup a secret sharing scheme. The efficiency of the dealer's randomness is the ratio between the amount of the dealer's randomness and the length of the secret. Because random bits are a natural computational resource, it is important to reduce the amount of randomness used by the dealer to setup a secret sharing scheme. In this paper, we propose some decomposition constructions for perfect secret sharing schemes with access structures of constant rank. Compared with the best previous results, our constructions have some improved upper bounds on the dealer's randomness and on the efficiency of the dealer's randomness.

Asynchronous and Synchronous languages have been in use for the specification of reactive systems. One of the main distinguishing features of these two classes lies in the way nondeterminism is used for the specification of programs. From this viewpoint, we analyze CSP (a typical asynchronous language) and ESTEREL (a synchronous language). The synchronous language Esterel is based on the notions of determinism, input nondeterminacy and parallelism whereas CSP is built on the notions of nondeterminism, concurrency and distribution. The main objectives of the study are to assess:

• The role of nondeterminism in the specification of the behaviour and realization of programs: A clear distinction between local and global nondeterminism enables us to distinguish between implementational nondeterminism and environmental/input nondeterminism. The results in this direction would enable one to achieve observable determinism where the implementational choices can be hidden and thus, analyze the program behaviour with reference to the real environmental nondeterminism in the specification. This leads to a proper refinement of specifications and aids in deriving distributed implementations of finite state transition systems that are not necessarily deterministic.

• The implementability of asynchronous languages through synchronous languages. The implementability of asynchronous languages in synchronous languages not only provides a realistic implementation but also provides higher level abstractions (such as multi-process interactions) for reactive specifications using features such as broadcast, interrupts, exception handling mechanisms etc.

By defining a general max and a general min operator for complexity classes we obtain that there are other interesting classes of optimization functions besides Krentel's class OptP. We investigate the behavior of these operators on the polynomial hierarchy, in particular we study the inclusion structure of the classes max · P, max · NP, max · coNP, min · P, min · NP, and min · coNP. It turns out that our operators when applied to the polynomial hierarchy yield a refinement of Krentel's hierarchy of optimization functions. We prove that this refinement is strict unless the polynomial hierarchy collapses and show that the refinement is useful to exactly classify optimization functions. Moreover, our investigations shed new light on Krentel's result that every function from some level of the polynomial hierarchy can be characterized in terms of an optimization function.

Two decision trees are called decision equivalent if they represent the same function, i.e., they yield the same result for every possible input.

We prove that given a decision tree and a number, to decide if there is a decision equivalent decision tree of size at most that number is NP-complete. As a consequence, finding a decision tree of minimal size that is decision equivalent to a given decision tree is an NP-hard problem.

This result differs from the well-known result of NP-hardness of finding a decision tree of minimal size that is consistent with a given training set. Instead our result is a basic result for decision trees, apart from the setting of inductive inference.

On the other hand, this result differs from similar results for BDDs and OBDDs: since in decision trees no sharing is allowed, the notion of decision tree size is essentially different from BDD size.