In hypercube multiprocessors it is important for the resource manager to be able to recognize and allocate subcubes of adequate sizes. Known allocation schemes, such as Gray code allocation strategy, do not consider hypercube in which there are faulty processors. However, faulty processors destroy some of the subcubes which resource manager can recognize searching on the current allocation list. This decreases the allocation performance. We propose a fault tolerant allocation algorithm which reconstucts allocaton list in order to remedy damege caused by faults. First, one measure of goodness of allocation list is introsuced referred to as a subcube recogizability. Then, general rules for allocation list restructuring are formulated. Accordingly, a two-step algorithm is developed which builds a new allocation list with improved subcube recognizability. Namely, the number and/or size of fault-free recognizable subcubes on the new list are maximal, for the given distribution of faults. Such a graceful degradation of allocation performance in injured hypercube is achieved just by means of prosessor readdressing. At last, the correctness and optimality of the algorithm are proved.

This paper considers processor utilization in faulty hypercube multiprocessor. The utilization is proportional to the continuity of processor allocation model based on Gray code. Busy and faulty processors make this model fragmented. That prevents assigning of larger tasks onto hypercube and decreases processor utilization. A set of procedures is derived which reassigns active tasks so that a new task configuration along with faulty processors makes as little damage as possible to the continuity of allocation model. First, a hypercube fragmentation measure is defined and a task reassigning technique presented. Then, procedures are given which determine: (1) active tasks to be reassigned, (2) their new optimal locations and (3) the shortest reassigning paths. At last, it is proved that while increasing processor utilization, presented scheme minimizes task reconfiguration overhead.

In this paper an approach to formal specification and verification of ISDN services in LOTOS is presented. As for specification, it is shown that LOTOS can be effectively applied to describe different levels of ISDN service specifications. At the higher level, only the external behaviour of the network is specified. On the other hand, at the lower level, specifications include the behaviour of network components such as switching systems, where each switching system can be specified independently of each other. Such specification style, proves suitable for verification of specifications by using the concepts of the simulation relation.