Database research and practice has brought up a large body of knowledge and experience. This experience and knowledge is based on solutions for database structures that occur and reoccur in many applications in a similar form. We may distinguish two classes of such solutions: reference models that can be used as a blueprint for a fully fledged schema and stereotypes that are general solutions.

Many fundamental problems in the area of distributed systems such as security, reliable routing, network survivability and broadening available bandwidth can be addressed through the use of disjoint paths between communication endpoints. Therefore, distributed solutions to the disjoint paths problem are of crucial importance to these fundamental problems. Disjoint paths naturally exist in traditional networks; however, these networks provide no guarantees regarding the presence and the number of available disjoint paths. On the other hand, network topologies structured based on Caley graphs such as hypercube, star networks and their variations possess many desirable properties related to disjoint paths. Therefore, it is anticipated that backbones of future networks will be structured following some Caley graph topologies. In this paper, we present a simple novel stabilizing and inherently stabilizing algorithm to route messages over all node-disjoint paths of optimal length from one non-faulty process to another in at most n+1 rounds in an n-dimensional hypercube network in the presence of crash failures. The proposed algorithm can tolerate up to 2n−⌈log (n+1)⌉ process/link failures in the network and a maximum of ⌊(L−2)/3⌋ process/link failures on each disjoint path, where L is the number of processes on a disjoint path and the distance between any two failed processes/links is at least three. The proposed algorithm tolerates a large number of process and link failures, while delivering all n messages over optimal-length disjoint paths in the presence of maximum permissible process/link failures on each path. This is achieved by a simple uniform distributed algorithm using only local knowledge of failure locations.

Lee codes have been intensively studied for more than 40 years. Interest in these codes has been triggered by the Golomb-Welch conjecture on the existence of the perfect error-correcting Lee codes. In this paper, we deal with the existence and enumeration of diameter perfect Lee codes. As main results, we determine all q for which there exists a linear diameter-4 perfect Lee code of word length n over Zq, and prove that for each n ≥ 3, there are uncountable many diameter-4 perfect Lee codes of word length n over Z. This is in a strict contrast with perfect error-correcting Lee codes of word length n over Z as there is a unique such code for n=3, and its is conjectured that this is always the case when 2n+1 is a prime. We produce diameter perfect Lee codes by an algebraic construction that is based on a group homomorphism. This will allow us to design an efficient algorithm for their decoding. We hope that this construction will turn out to be useful far beyond the scope of this paper.

The node-disjoint paths problem deals with finding node-disjoint paths from a source node s to target node t, where t ¿ s. Two paths from s to t are said to be node-disjoint iff they do not have any common vertices except for their endpoints. Distributed solutions to the node-disjoint paths problem have numerous applications such as secure message transmission, reliable routing, and network survivability. In this paper, we present a simple distributed algorithm that is both stabilizing and inherently stabilizing under a realistic model that describes system interfaces and implementation issues in detail to route messages over all shortest node-disjoint paths from one process to another in an n-dimensional hypercube network.

Gray codes, where two consecutive codewords differ in exactly one position by plusmn1, are given. In a single radix code, all dimensions have the same base, sayk, whereas in a mixed radix code the base in one dimension can be different from the base in another dimension. Constructions of new classes of mixed radix Gray codes are presented. It is shown how acyclicmixedradixGraycodecorresponds to a Hamiltonian cycle in a mixed radix toroidal graph. It is then shown how these codes can be used as a basis for constructing edge disjoint Hamiltonian cycles in mixed radix toroidal networks when the number of dimensions, n = 2rfor some r ges 0.

Gray codes, where two consecutive codewords differ in exactly one position by plusmn1, are given. In a single-radix code, all dimensions have the same base, say, kappa, whereas, in a mixed-radix code, the base in one dimension can be different from the base in another dimension. Constructions of new classes of mixed-radix Gray codes are presented. It is shown how these codes can be used as a basis for constructing edge-disjoint Hamiltonian cycles in mixed-radix toroidal networks when the number of dimensions n = 2rfor some r ges 0. Efficient algorithms for the generation of these codes are then shown.

A construction of perfect/quasiperfect Lee distance codes in Z/sub K//sup 2/ is introduced. For this class of codes, a constant time encoding scheme is defined, the minimum code distance is derived, and the maximum covering radius is calculated. Efficient decoding schemes are investigated and developed. In general, a code of this class can be decoded in O(t/sub 1/), where t/sub 1/ is the number of errors that can be corrected. Special cases, however, can be decoded in constant time.