SELF-STABILIZING
DEPTH-FIRST TOKEN CIRCULATION IN ASYNCHRONOUS
MESSAGE-PASSING SYSTEMS
Franck
Petit, Vincent Villain
Abstract.
Self-stabilization
was first introduced by Dijkstra. A self-stabilizing system, regardless of the
initial states of the processors and initial messages in the links, is
guaranteed to converge to the intended behavior in finite time.
This is a very desirable
property for systems to tolerate arbitrary transient faults. This paper proposes
the first self-stabilizing depth-first token circulation algorithm for
message-passing systems. The algorithm deals with the dynamic networks, i.e.,
the topology of the network may change during the execution of the algorithm.
The size of the messages is five bits only. Once the system is stabilized, the
message complexity is {O}(m D),
where D
and m are the upper bound of node's
degree and the number of links of the network, respectively.
FUNCTION
ORIENTED HISTORY REPRESENTATION IN DATABASES
Lázsló Kovács,
Costas Vassilakis
Abstract.
In
the past years the management of temporal data has attracted numerous
researchers resulting to a large number of temporal data extensions to the
relational and object oriented data models. In this paper, the proposed temporal
data model focuses on the functional characteristics of the histories. The paper
introduces a set oriented description of the calendars together with a function
oriented history concept with a history-algebra.
The completeness of the proposed model with respect to the
reduced temporal algebra TA is also proven. The expressive power of the
proposed model is demonstrated in the end of the paper by a hospital example.
A
NEW BFS PARENT ARRAY ENCODING OF t-ARY TREES
Selim G. Akl,
Stephan Olariu, Ivan Stojmenovic
Abstract.
We
introduce a new breadth first search (BFS) parent array encoding of trees as
integer sequences. The new representation enables the inclusion of
parent-children relations in a straightforward way, which is not the case with
the existing representations. We also introduce a children array representation
for binary trees and a simple algorithm for generating binary trees (including
parent-children relations) using the notation. The algorithm can
be applied to generate well-formed parenthesis strings in a simple way. Two
generalizations to the case of children array representation for t-ary trees are also given.
ANALYTICAL
MODEL OF DISTRIBUTED COMPUTER NETWORK
Ivan Hanuliak
Abstract. The paper describes development, realisation and verification of the new analytical model for the study of the basic parameters (end-to-end delay, performance etc.) of distributed computer networks. The suggested model considers for every node of the computer network, one part for own node activities (communication functions) and another one for modelling of the node channel for data transmission. In case of using multiprocessor system as modern node communication processor, the model for own node activities is M/D/r system and that for every node transmission channel is M/M/1 system. The analytical model includes derivation of the correction factor to account the real non exponential nature of the input to individual transmission channels. The achieved results of the developed model are compared with the results of the common analytical and simulation models to estimate the improvement. Likewise, the corrected analytical model was tested under various range of parameters, which influence the architecture of distributed computer network and which are interested from the view of practical using.
ABSTRACT
AND-PARALLEL MACHINES
Naomi Lindenstrauss,
Nachum Dershowitz
Abstract. Several abstract models of fine-grained parallelism, suited to symbolic programming languages, are suggested. The first, the and-parallel Turing machine, can be viewed as a generalization of the deterministic Turing machine in which the infinite tape is replaced by an infinite tree-like tape on which processors work in parallel. With this model one can express in a very natural way communication between processors, suspension, and synchronization. There are examples in which the processing time is polylogarithmic in the size of the input while for a nondeterministicTuring machine that looks at its input the time must be at least of the order of magnitude of the size of the input. Then a stronger model, the parallel rewriting machine, is introduced. Transitions are formulated as rewrite rules, resulting in a machine that is much easier to program. This also adds a `pointer capability' to the previous machine. Since this machine gets the program in a form that reflects its meaning, problems of synchronization are easily handled - rewrite rules just cannot be applied before arguments reach the right form. In both models a processor can launch other processors on subcomputations, but processing at a parent node must wait for answers from all of its "children''. One can introduce more powerful models that contain the possibility of an interrupt - if the answer from one child (or several children) is sufficient to continue the computation at the parent, the computation started by the other children can and should be interrupted. These interrupt machines are much more powerful than the previous two, but it does not seem to be much more difficult to implement them. Although the machines considered are very powerful - the parallel rewriting machine can compute the permanent in polynomial time and the and-parallel Turing machine with interrupt can simulate a nondeterministic Turing machine and an alternating Turing machine - they can be seen as models of realistic machines if time and space are suitably restricted.