Our goal in this paper is to discuss our experience with process migration in the Charlotte distributed operating system. We also draw upon the experience of other operating systems in which migration has been implemented. A process migration facility in a distributed operating system dynamically relocates processes among the component machines. A successful process migration facility is not easy to design and implement. Foremost, a general-purpose migration mechanism should be able to support a range of policies to meet various goals, such as load distribution, and improved concurrency, and reduced communication. We discuss how Charlotte's migration mechanism detaches a running process from its source environment, transfers it, and attaches it into a new environment on the destination machine. Our mechanism succeeds in handling communication and machine failures that occur during the transfer. Migration does not affect the course of execution of the migrant nor that of any process communicating with it. The migration facility adds negligible overhead to the distributed operating system and provides fast process transfer.
This paper presents algorithms for barrier synchronization in point-to-point interconnection networks. We present algorithms and lower bounds for the deBruijn, hypercube, quadratic, and general undirected networks. All the algorithms achieve optimal dissemination time and close to optimal number of messages. For all the networks, the communication pattern is composed of rounds, during each of which some nodes send to some of their neighbors. After hearing enough messages, each node is certain that all nodes have entered the barrier and therefore may proceed.
Service rebalancing is a method for designing programs that adhere to the client/server model. Decisions about the division of labor between client and server are made dynamically at runtime rather than at design time. Service rebalancing may improve performance, because the division of effort is based upon an evaluation of the current environment. Other benefits of service rebalancing include on-the-fly updating of modules, a degree of load balancing, sharing of code common to several clients, encouragement of neatly modularized programs, and the elimination of an absolute division of effort between client and server. In this paper we discuss the benefits, problems and issues of service rebalancing. Our implementation, Equanimity, is described in some detail. Finally, we compare service rebalancing with previous work and discuss future plans.
This paper defines several serial and parallel game-tree search methods and compares them by experiment. The algorithms are alpha-beta, mandatory work first, principal-variation splitting, tree splitting, ER, and delay splitting. All have been implemented in a common environment provided by the DIB package. This revision corrects an error of the initial version.
This paper presents PCSMA, an extension to the CSMA/CD protocol (used in the Ethernet) to support both conventional datagram traffic and real-time traffic. The protocol provides predictable packet-delivery bounds for real-time traffic. It does not require changes to existing Ethernet controllers for datagram traffic. Under the new protocol, periodic sources follow a variation of the CSMA protocol that requires them to reserve transmission slots before they can begin transmission. This protocol is intended particularly for use in the integrated network in a manufacturing shop. Periodic sources include multiple sensors generating disparate types and rates of data. We have carried out an extensive performance evaluation of the protocol using a simulation model. The results are impressive: PCSMA shows fewer collisions than CSMA, equivalent delays for conventional traffic, and no failures to meet deadlines for periodic traffic.
This paper describes the Viva File System or VIFS, a technique for high-performance file allocation on disks. VIFS uses bitmaps to represent both free blocks on the disk and allocated blocks in each file. Allocation bitmaps provide a very fast method of finding blocks close to the last allocated block in a file. Fragments (partial blocks) are used to store the overflow from the last file block; the minimum size of a fragment is chosen when the file system is initialized. Conventional file systems, such as the Berkeley Fast File System (FFS), can store a file containing 96KB of data without using indirect blocks and around 16 MB of data for each indirect block. With the same block size, VIFS can store up to about 10 MB of data without using indirect blocks and up to 500 MB of data per indirect block. The design of VIFS allows some previously synchronous operations to occur asynchronously, resulting in significant speed improvements over FFS. VIFS provides multiple read-ahead to maintain its high speed when several processes are competing for disk accesses. We provide experimental measurements taken from an implementation of Viva in a BSD 4.3 kernel. The measurements show that VIFS is significantly faster than FFS for nearly all file system operations.
Service rebalancing provides a way to determine an efficient division of effort between a client and its server. Decisions concerning this division of labor are made at runtime rather than at design time. Evaluating the current environment in which the client and server are executing and moving code between client and server based upon this evaluation can enhance the performance of client-server programs. Advantages of service rebalancing include the elimination of a static division between client and server, on-the-fly updating of modules, load balancing, sharing of common code between multiple clients, and enforcement of neatly modularized programming. In this paper we introduce service rebalancing and discuss some of the related problems, issues and solutions. We discuss our implementation, Equanimity, in some detail. Finally, we present our experimental results and comparisons to related work.
The Unify system is exploring scalable approaches for designing distributed multicomputers that support a shared memory paradigm. To achieve massive scalability, unify employs highly efficient communication protocols to support new weak consistency sharing models. In particular, Unify introduces the notion of spatial consistency and a non-standard memory type called sequential segments. The combination of out-of-order spatial consistency and sequential segments increases concurrency, reduces the need for synchronization, and allows the use of highly efficient non-atomic multicast protocols. Our experience shows that there is a logical and intuitive connection mapping between sequential segments and a wide variety of parallel and distributed applications that require support for shared information. Moreover, the use of sequential segments results in simplified code and efficiency comparable to that of optimized message passing systems.
Qddb is a very popular database suite designed for applications in which the data is logically a set of records, each of which refers to an entire structured entity. Each record represents values from relational tables that are joined when data are entered.This paper presents schema and tuple trees, the underlying structure of a Qddb database. Instead of a set of full relational rows representing the join of several tables, the tuple tree represents the tables in a compressed form. Related data are stored and displayed together, which allows the application designer to build an application in a relatively small amount of time.
The presentation of data in Qddb is unusual but intuitive; the user usually views a subset of a full relational row at any given time. This presentation is largely the cause of Qddb's popularity.
Measuring machine performance within a network, especially with regard to parallelized applications, is an important issue. In this paper we examine the problem of computing the efficiency of distributed computations when executed on a heterogeneous mix of machines. We propose the calculation of {\em effective efficiency}, which is based upon the effective number of processors involved in the computation rather than the actual number of machines. Our experiments show that effective efficiency is a more realistic measurement of heterogeneous processors performance than traditional efficiency. Effective efficiency can be used to evaluate various cluster configurations with respect to a specific application or evaluate applications with respect to a fixed configuration.
In the framework of Network Morphology, realizational models of natural-language morphology have customarily been defined in DATR, a language for lexical knowledge representation designed and implemented by Roger Evans and Gerald Gazdar. We show that certain kinds of morphological analyses that are wholly consonant with the general program of Network Morphology are not directly expressible in existing forms of DATR; we therefore propose and exemplify KATR, an extension of DATR whose motivation is to accommodate these desired kinds of morphological analyses. The proposed modifications are motivated by the need to represent a word's morphosyntactic property as essentially unordered; to account for the incidence of nonlocal sandhi phenomena; to define common patterns of inflectional syncretism; and to allow certain morphological rules to apply in "expanded mode". Although KATR affords morphological definitions that are more streamlined than those afforded by DATR, its generative capacity is no greater than that of DATR, since both languages are capable of emulating a Turing machine.
Intuitively, a set of principal parts for a paradigm P is a minimal subset of P's members from which all of P's other members can be deduced. The practical utility of principal parts for language pedagogy has long been recognized. Principal parts can be seen as a pedagogical idealization of an important feature of first language acquisition: language learners' reliance on the implicative relationships among the forms in a lexeme's paradigm to deduce that lexeme's full inventory of forms. This paper develops the concepts of static, adaptive, and dynamic principal parts and suggests how to use them to build a framework for morphological typology.
A lexeme's PRINCIPAL PARTS are a subset of the cells in its paradigm from which all of the other cells in the paradigm can be deduced. There are at least two ways of conceiving of principal parts: under the STATIC conception, the same cells in the paradigm of every lexeme are that lexeme's principal parts; under the DYNAMIC conception, the cells constituting a lexeme's principal parts may vary from one lexeme to another. We define a lexeme's paradigm as MAXIMALLY TRANSPARENT if any cell in that paradigm could function as that lexeme's sole dynamic principal part; inflection classes can be distinguished according to the kind and extent of their deviation from the ideal of maximal transparency. In general, paradigms that deviate from this ideal (i) require additional principal parts and/or (ii) admit fewer alternative principal-part analyses than would be logically possible, given their number of principal parts. We illustrate with evidence from Comaltepec Chinantec (Oto-Manguean; Mexico); drawing on a computational analysis of dynamic principal parts in this language, we demonstrate that its conjugation classes are in some instances maximally transparent and in other instances embody one or both of deviations (i) and (ii). We propose formal measures of PARADIGM PREDICTABILITY and CELL PREDICTABILITY that allow degrees of deviation to be represented precisely. We discuss the implications of our findings for the No Blur Principle (Cameron-Faulkner & Carstairs-McCarthy 2000); drawing on evidence from Fur (Nilo-Saharan; Sudan), we show that this principle cannot be maintained. Finally, we compare the principal-part systems of Comaltepec Chinantec and Fur, which demonstrate that paradigmatic transparency is an important domain of typological variation.
The problem of secure routing in mobile ad hoc networks is long-standing and has been extensively studied by researchers. Recently, techniques of aggregating signatures have been applied to authenticate on demand routing protocols in mobile ad hoc networks. In this paper, we propose an efficient, single round multisignature scheme, CLFSR-M, constructed using cubic (third-order) linear feedback shift register (LFSR) sequences. The scheme, CLFSR-M is derived from a 2-party signature scheme CLFSR-S, formed using a well-known variant of the generalized ElGamal signature scheme. The multisignature has been engineered to produce an efficient technique to authenticate route discovery in the dynamic source routing (DSR) protocol. Our technique supports authentication of cached routes. Delegating special functions to nodes or assuming the existence of a trusted third party to distribute certified public keys is not practical in mobile ad hoc networks. We consider a fully distributed mechanism of public key distribution and present two variations of trust policies, based on PGP, for effective management of individual and aggregate public keys. Finally, we perform a theoretical analysis including correctness and security of CLFSR-M and also present a performance (computation and communication costs, storage overhead) comparison of the proposed scheme with existing ones.
Communication-Induced Checkpointing (CIC) protocols are classified into two categories in the literature: \emph{Index}-based and \emph{Model}-based. In this paper, we discuss the intrinsic relation between the two categories and provide our classification of CIC protocols based on how they achieve the same goal of ensuring Z-Cycle Free (ZCF) property by tracking the checkpoint and communication pattern (CCP) that can lead to Z-cycles and preventing them. Then, based on our Transitive Dependency Enabled TimeStamp ($TDE\_TS$) mechanism, we present our Fully Informed aNd Efficient \emph{(\bf FINE)} algorithm which can not only improve the performance of Fully Informed \emph{(\bf FI)} CIC protocol proposed by Helary et al. but also decrease the overhead of information piggybacked with application messages.