Formal design methods are becoming increasingly recognised as being useful for specifying complex systems. Incorporating formal methods in the early stages of a design process introduces the possibility of using mathematical techniques, hence improving the effectiveness of a design process. The Z notation has been applied mainly to specifying software, although it has also been used for specifying hardware and general systems. The Z notation fulfils two functions in this thesis. The first function is as a notation for representing specifications of complex systems, and the second function is as a notation for representing implementations of the same complex systems. The suitability of the Z notation for these functions is investigated in three studies. Both the specifications and implementations are represented as unified collections of Schemas that describe the behaviour in response to each set of input conditions. In each of the studies, both the specifications and implementations of the complex system take place at an early stage in a design process. Throughout this thesis non rigorous proof sketches prove that the implementations meet the requirements of the specifications.

The objective of this thesis is the unified investigation of a wide range of fundamental parallel methods that are transportable amongst pragmatic parallel machines having different number of processors, different periodicity of global synchronization and different bandwidth of inter-processor communication. The computational model adopted is the bulk-synchronous parallel (BSP) model, which abstracts the characteristics of parallel machines into three numerical parameters p, L and g, that quantify, respectively, processors, periodicity and bandwidth - the model differentiates memory that is local to a processor from memory that is non-local, yet, for the sake of universality, does not differentiate network proximity. The BSP parameters p, L and g, together with the problem size n, are employed to measure the performance, and consequently, the transportability of parallel methods across machines having different values of these parameters. We show that optimality to within small multiplicative constant factors close to one can be achieved for a multiplicity of fundamental computational problems by transportable algorithms and data structures that can be applied for a wide range of values of the BSP parameters. While these algorithms and data structures are fairly simple themselves, description of their performance in terms of these parameters is somewhat complicated. The main reward for quantifying these complications, is that it enables software to be written once and for all that can be migrated efficiently amongst a variety of parallel machines. The methods considered in this thesis - both theoretically and experimentally - embody deterministic and randomized techniques for the efficient realization of fundamental algorithms (broadcasting, computing parallel-prefixes, load-balancing, list-contracting, merging, sorting, integer-sorting, selecting, searching and hashing), data structures (heaps, search trees and hash tables) and applications (computational geometry, parallel model simulations and structured query language primitives).

Distributed systems are gradually being accepted as the dominant computing paradigm of the future. However, due to the diversity and multiplicity of resources, and the need for transparency to users, global resource management raises many questions. On the performance level the potential benefits of the load balancing in resolving the occasional congestion experienced by some nodes while others are idle or lightly loaded are commonly accepted. It is also acknowledged that no single load balancing algorithm deals satisfactorily with the changing system characteristics and dynamic workload environment. In modelling distributed systems for load balancing, optimistic assumptions of system characteristics are commonly made, with no evaluation of alternative system design options such as communications protocols. When realistic assumptions are made on system attributes such as communication bandwidth, load balancing overheads, and workload model, doubts are cast on the capability of load balancing to improve the performance of distributed systems significantly. A taxonomy is developed for the components as well as the attributes aspects of load balancing algorithms to provide a common terminology and a comprehensive view to load balancing in distributed systems. For adaptive algorithms the taxonomy is extended to identify the issues involved and the ways of adding adaptability along different dimensions. A design methodology is also outlined. A review of related work is used to identify the most promising load balancing strategies and the modelling assumptions made in previous load balancing studies. Subsequently the research problems addressed in this thesis and the design of new algorithms are detailed. A simulated system developed to allow an experimentation with various load balancing algorithms under different workload models and system attributes is described. Based on the nature of the file system structure and the classes of nodes processing speed involved, different models of loosely-coupled distributed systems can be defined. Four models are developed: disk-based homogeneous nodes, diskless homogeneous nodes, diskless heterogeneous nodes, and disk-based heterogeneous nodes. The nodes are connected through a broadcast transfer device. A set of representative load balancing algorithms covering a range of strategies are evaluated and compared for the four models of distributed systems. The algorithms developed include a new algorithm called Diffuse based on explicit adaptability for the homogeneous systems. In the case of heterogeneous systems, novel modifications are made to a number of algorithms to take into account the heterogeneity of nodes speed. The evaluation on homogeneous systems is two-fold: an assessment of the effect of system attributes on the performance of the distributed system subject to these algorithms, and a comparison of the relative merits of the algorithms using different performance metrics, and in particular a classification of the performance of the Diffuse algorithm with regard to others in the literature. For the heterogeneous systems the performance of the adapted algorithms is compared to that of the standard versions and to the no load balancing case. As a result of this evaluation, for a set of combinations of performance objectives, distributed system attributes, and workload environment, we identify the most . appropriate load balancing algorithm and optimal values for adjustable parameters of the algorithm.

Computer technology, particularly at the circuit level, is fast approaching its physical limitations. As future needs for greater power from computing systems grows, increases in circuit switching speed (and thus instruction speed) will be unable to match these requirements. Greater power can also be obtained by incorporating several processing units into a single system. This ability to increase the performance of a system by the addition of processing units is one of the major advantages of multiprocessor systems. Four major characteristics of multiprocessor systems have been identified (28) which demonstrate their advantage. These are:- Throughput Flexibility Availability Reliability The additional throughput obtained from a multiprocessor has been mentioned above. This increase in the power of the system can be obtained in a modular fashion with extra processors being added as greater processing needs arise. The addition of extra processors also has (in general) the desirable advantage of giving a smoother cost-performance curve ( 63). Flexibility is obtained from the increased ability to construct a system matching the user 'requirements at a given time without placing restrictions upon future expansion. With multiprocessor systems; the potential also exists of making greater use of the resources within the system. Availability and reliability are inter-related. Increased availability is achieved, in a well designed system, by ensuring that processing capabilities can be provided to the user even if one (or more) of the processing units has failed. The service provided, however, will probably be degraded due to the reduction in processing capacity. Increased reliability is obtained by the ability of the processing units to compensate for the failure of one of their number. This recovery may involve complex software checks and a consequent decrease in available power even when all the units are functioning.

No description available.

No description available.

The thesis is concerned with the transmission and reception of digital data at 19,200 bit/s over voice-frequency telephone channels. Following a feasibility study based on both practical and theoretical constraints, the telephone network itself is investigated to determine methods of circuit characterisation and the causes and effects of distortion and other signal impairments.

No description available.

Thesis (M.S.)--Virginia Polytechnic Institute and State University, 1994. / Vita. Abstract. Includes bibliographical references (leaves 116-117). Also available via the Internet.

No description available.