Multi-core programming remains a major software development and maintenance challenge because of data races, deadlock, non-deterministic failures and complex performance issues. In this paper, we describe EXCITE-VM, a system that provides snapshot isolation transactions on shared memory to facilitate programming and to improve the performance of parallel applications. With snapshots, an application thread is not exposed to the committed changes of other threads until it receives the updates by explicitly creating a new snapshot. Snapshot isolation enables low overhead lockless read operations and improves fault tolerance by isolating each thread from the transient, uncommitted writes of other threads. This paper describes how EXCITE-VM implements snapshot isolation transactions efficiently by manipulating virtual memory mappings and using a novel copy-on-read mechanism with a customized page cache. Compared to conventional software transactional memory systems, EXCITE-VM provides up to 2.2x performance improvement for the STAMP benchmark suite and up to 1000x speedup for a modified benchmark having long running read-only transactions. Furthermore, EXCITE-VM achieves a 2x performance improvement on a Memcached benchmark and the Yahoo Cloud Server Benchmarks. Finally, EXCITE-VM improves fault tolerance and offers features such as low-overhead concurrent audit and analysis.

Transactional memory represents an attractive conceptual model for programming concurrent applications. Unfortunately, high transaction abort rates can cause significant performance degradation. Conventional transactional memory realizations not only pessimistically abort transactions on every read-write conflict but also because of false sharing, cache evictions, TLB misses, page faults and interrupts. Consequently, the use of transactions needs to be restricted to a very small number of operations to achieve predictable performance, thereby, limiting its benefit to programming simplification. In this paper, we investigate snapshot isolation transactional memory in which transactions operate on memory snapshots that always guarantee consistent reads. By exploiting snapshots, an established database model of transactions, transactions can ignore read-write conflicts and only need to abort on write-write conflicts. Our implementation utilizes a memory controller that supports multiversion memory, to efficiently support snapshotting in hardware.We show that snapshot isolation can reduce the number of aborts in some cases by three orders of magnitude and improve performance by up to 20x.

Bitmap represents an efficient indexing structure for querying large amounts of data and is widely deployed in data-warehouse applications. While the size of a bitmap scales linearly with the number of rows in a table, due to its sparseness, it can be greatly reduced via compression based on run-length encoding. However, updating a compressed bitmap is expensive due to the encoding and decoding overheads, in particular, as re-compression can change the compressed sequence length and data layout. Due to this problem, bitmap indices only perform well for read-only workloads.

Transactional memory systems providing snapshot isolation enable concurrent access to shared data without incurring aborts on read-write conflicts. Reducing aborts is extremely relevant as it leads to higher concurrency, greater performance, and better predictability. Unfortunately, snapshot isolation does not provide serializability as it allows certain anomalies that can lead to subtle consistency violations. While some mechanisms have been proposed to verify the correctness of a program utilizing snapshot isolation transactions, it remains difficult to repair incorrect applications. To reduce the programmer’s burden in this case, we present a technique based on dynamic code and graph dependency analysis that automatically corrects existing snapshot isolation anomalies in transactional memory programs. Our evaluation shows that corrected applications retain the performance benefits characteristic of snapshot isolation over conventional transactional memory systems.

Programming language and operating system support for efficient concurrency-safe access to shared data is a key concern for the effective use of multi-core processors. Most research has focused on the software model of multiple threads accessing this data within a single shared address space. However, many real applications are actually structured as multiple separate processes for fault isolation and simplified synchronization. In this paper, we describe the HICAMP architecture and its innovative memory system, which supports efficient concurrency safe access to structured shared data without incurring the overhead of inter-process communication. The HICAMP architecture also provides support for programming language and OS structures such as threads, iterators, read-only access and atomic update. In addition to demonstrating that HICAMP is beneficial for multi-process structured applications, our evaluation shows that the same mechanisms provide substantial benefits for other areas, including sparse matrix computations and virtualization.

Sparse matrix-vector multiply (SpMV) is a critical task in the inner loop of modern iterative linear system solvers and exhibits very little data reuse. This low reuse means that its performance is bounded by main-memory bandwidth. Moreover, the random patterns of indirection make it difficult to achieve this bound. We present sparse matrix storage formats based on deduplicated memory. These formats reduce memory traffic during SpMV and thus show significantly improved performance bounds: 90x better in the best case. Additionally, we introduce a matrix format that inherently exploits any amount of matrix symmetry and is at the same time fully compatible with non-symmetric matrix code. Because of this, our method can concurrently operate on a symmetric matrix without complicated work partitioning schemes and without any thread synchronization or locking. This approach takes advantage of growing processor caches, but incurs an instruction count overhead. It is feasible to overcome this issue by using specialized hardware as shown by the recently proposed Hierarchical Immutable Content-Addressable Memory Processor, or HICAMP architecture.

In this paper, we extensively tune and then compare the performance of web servers based on three different server architectures. The μserver utilizes an event-driven architecture, Knot uses the highly-efficient Capriccio thread library to implement a thread-per-connection model, and WatPipe uses a hybrid of events and threads to implement a pipeline-based server that is similar in spirit to a staged event-driven architecture (SEDA) server like Haboob.

We provide three key missing pieces of a general theory of information distance [3, 23, 24]. We take bold steps in formulating a revised theory to avoid some pitfalls in practical applications. The new theory is then used to construct a question answering system. Extensive experiments are conducted to justify the new theory.

We show that a set of independently developed spam filters may be combined in simple ways to provide substantially better filtering than any of the individual filters. The results of fifty-three spam filters evaluated at the TREC 2005 Spam Track were combined post-hoc so as to simulate the parallel on-line operation of the filters. The combined results were evaluated using the TREC methodology, yielding more than a factor of two improvement over the best filter. The simplest method -- averaging the binary classifications returned by the individual filters -- yields a remarkably good result. A new method -- averaging log-odds estimates based on the scores returned by the individual filters -- yields a somewhat better result, and provides input to SVM- and logistic-regression-based stacking methods. The stacking methods appear to provide further improvement, but only for very large corpora. Of the stacking methods, logistic regression yields the better result. Finally, we show that it is possible to select a priori small subsets of the filters that, when combined, still outperform the best individual filter by a substantial margin.

Scalable reliable multicast protocols have been the focus of recent research, tackling the problem of efficient reliable data delivery to an arbitrarily large number of receivers. Yet, the common applications of multicast, such as multi-point file delivery, or video streaming from a media server, typically only involve a moderate number of receivers, such as a thousand or fewer. Moreover, because of the limited deployment of these specialized multicast protocols, it is common, when feasible, for applications to use multiple TCP connections instead, one for each receiver, to implement multi-point delivery, causing a significant demand on the transmission server and the downstream links. We describe a multicast extension to TCP, called single-source multicast optimization (SMO), that optimizes this case of multipoint delivery, providing the benefits of multicast together with the familiar features and API of TCP. Our results from experiments based on a Linux implementation and performed on a testbed show that TCP-SMO requires just a modest extension to the TCP implementation and provides scalable performance of multicast up to over a thousand receivers, thereby satisfying the common case requirements. In addition, used with TCP-RTM (real-time mode), TCP-SMO also supports real-time multimedia multicast applications well.

Conventional QoS mechanisms have focused primarily on providing better than normal service for some flows over others. With networks moving to much higher speeds and reasonable provisioning, best efforts access to network resources is adequate for common applications except when a belligerent flow attempts to consume an excessive amount of bandwidth. Any mechanism that attempts to contain such a flow must be able to operate at wirespeed in hardware. In this environment, conventional QoS mechanisms are not sufficient, either because they do not have mechanisms to contain these belligerent flows or because they are not practical to implement in hardware. In this paper we describe dynamic buffer limiting (DBL), a buffer and queue management mechanism designed to recognize and handle belligerent flows at very high speed and suitable for hardware implementation.

Forward error correction (FEC) has been proposed as a technique for implementing efficient reliable multicast (RM). However, FEC incurs costs in encode/decode delay and implementation complexity. How much benefit is provided relative to these costs and how dependent is the benefit on the specific RM protocol? In this paper, we evaluate the benefits of FEC for RM, considering both proactive and reactive use with three RM recovery techniques: duplicate avoidance, limited scope multicast and subcast. Our simulation-based results indicate that FEC provides little benefit for an efficient RM protocol like OTERS and introduces extra delay for multi-point streaming data applications.

In the IP multicast model, a set of hosts can be aggregated into a group of hosts with one address, to which any host can send. However, Internet TV, distance learning, file distribution and other emerging large-scale multicast applications strain the current realization of this model, which lacks a basis for charging, lacks access control, and is difficult to scale.This paper proposes an extension to IP multicast to support the channel model of multicast and describes a specific realization called EXPlicitly REquested Single-Source (EXPRESS) multicast. In this model, a multicast channel has exactly one explicitly designated source, and zero or more channel subscribers. A single protocol supports both channel subscription and efficient collection of channel information such as subscriber count. We argue that EXPRESS addresses the aforementioned problems, justifying this multicast service model in the Internet.

Systems need to run a larger and more diverse set of applications, from real-time to interactive to batch, on uniprocessor and multiprocessor platforms. However, most schedulers either do not address latency requirements or are specialized to complex real-time paradigms, limiting their applicability to general-purpose systems.In this paper, we present Borrowed-Virtual-Time (BVT) Scheduling, showing that it provides low-latency for real-time and interactive applications yet weighted sharing of the CPU across applications according to system policy, even with thread failure at the real-time level, all with a low-overhead implementation on multiprocessors as well as uniprocessors. It makes minimal demands on application developers, and can be used with a reservation or admission control module for hard real-time applications.

This paper presents a reliable multicast protocol (OTERS) that organizes receivers into a fusion tree that matches the multicast delivery tree of the source and uses this tree to fuse NAKs and subcast retransmissions. The protocol requires two extensions to the current Internet network layer, namely multicast route backtracing and subcasting. We argue that these extension are simple, natural and low overhead extensions for the Internet. Simulations of six reliable multicast protocols demonstrate that our approach substantially reduces the recovery latency and the traffic load compared to previously proposed approaches.

Distributed interactive simulation systems are growing to include well over 100,000 dynamic entities for applications such as multiplayer video games, military and industrial training, and collaborative engineering. In these applications, each host receives updates (such as position and orientation) from remote entities, models and renders the scene, and performs other tasks such as collision detection. The number of entities places a heavy burden on both the networking resources and computational resources available to the application. To address these limitations, some systems have aggregated information about groups of simulation entities according to their organizational structure or their location within the virtual world. However traditional aggregation techniques are inadequate because remote hosts need to access entities based on both their organization and their virtual world position. This paper describes projection aggregations, a technique for grouping entities by both their organization and location. Remote hosts use projections to control which entities are represented locally and at what level-of-detail. We describe how projection aggregations are implemented in a networked environment and demonstrate how they reduce network bandwidth and computational requirements. Finally, we argue that projection aggregations represent a general-purpose framework for representing all simulation entities, thereby supporting evolution of entity models.

Remote procedure call (RPC) integrates distributed processing with conventional programming languages. However traditional RPC lacks support for forms of communication such as datagrams, multicast, and streams that fall outside the strict request-response model. Emerging applications such as Distributed Interactive Simulation (DIS) and Internet video require scalable, reliable, and efficient communication. Applications are often forced to meet these requirements by resorting to the error-prone ad-hoc message-based programming that characterized applications prior to the introduction of RPC. In this paper we describe an object-oriented RPC system that supports specialization for functionality and performance, allowing applications to modify and tune the RPC system to meet individual requirements. Our experiences with functional extensions to support reliable multicast and specializations to support streaming of performance-critical RPCs indicate that a wide range of communication semantics can be supported without resorting to ad-hoc messaging protocols.

Corporate network firewalls are well-understood and are becoming commonplace. These firewalls establish a security perimeter that aims to block (or heavily restrict) both incoming and outgoing network communication. We argue that these firewalls are neither effective nor appropriate for academic or corporate research environments needing to maintain information security while still supporting the free exchange of ideas. In this paper we present the Stanford University Research Firewall (SURF), a network firewall design that is suitable for a research environment. While still protecting information and computing resources behind the firewall, this firewall is less restrictive of outward information flow than the traditional model; can be easily deployed; and can give internal users the illusion of unrestricted e-mail, anonymous FTP, and WWW connectivity to the greater Internet. Our experience demonstrates that an adequate firewall for a research environment can be constructed for minimal cost using off-the-shelf software and hardware components.

No abstract available.

Reliable multicast communication is important in large-scale distributed applications. For example, reliable multicast is used to transmit terrain and environmental updates in distributed simulations. To date, proposed protocols have not supported these applications' requirements, which include wide-area data distribution, low-latency packet loss detection and recovery, and minimal data and management over-head within fine-grained multicast groups, each containing a single data source.In this paper, we introduce the notion of Log-Based Receiver-reliable Multicast (LBRM) communication, and we describe and evaluate a collection of log-based receiver reliable multicast optimizations that provide an efficient, scalable protocol for high-performance simulation applications. We argue that these techniques provide value to a broader range of applications and that the receiver-reliable model is an appropriate one for communication in general.

l,oggged [Itrhra[ 71teruory ( LVM ) provides a log of writes to ol]e or more sImcified regions of the virtual address space.I,ogging is useflll for applications that, require rollback and/ur perslstjenre slich as parallel simulations and memory-mapped obje( t-oriented databases It can also }Je Ilsed for olltpllt,, de})nggmg and chstrihuted consistency maintenance.Tlus }japer describes logged virtual memory as an extensiou of the standard virtual memory system software and harxiwarr.our l,rotot,ype implementation and some perforrrance measurements from this prototype.Based on these measurements and the experience with our prototype, we arglle that logged virtual memory can be supported with moclest, extensions to standard virtual memory systems, provides significant benefit to applications and servers, and is faster than other log-generation technicples.

Causally and totally ordered communication support (CATOCS) has been proposed as important to provide as part of the basic building blocks for constructing reliable distributed systems. In this paper, we identify four major limitations to CATOCS, investigate the applicability of CATOCS to several classes of distributed applications in light of these limitations, and the potential impact of these facilities on communication scalability and robustness. From this investigation, we find limited merit and several potential problems in using CATOCS. The fundamental difficulty with the CATOCS is that it attempts to solve problems at the communication level in violation of the well-known "end-to-end" argument.

article Free Access Share on Application-controlled physical memory using external page-cache management Authors: Kieran Harty View Profile , David R. Cheriton View Profile Authors Info & Claims ACM SIGPLAN NoticesVolume 27Issue 9Sept. 1992 pp 187–197https://doi.org/10.1145/143371.143511Published:01 September 1992Publication History 85citation1,023DownloadsMetricsTotal Citations85Total Downloads1,023Last 12 Months53Last 6 weeks2 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

Congestioncontrol is an important problem in high-speed computer networks.Networks must limit the packet load that they accept to avoid excessive packet loss and delay.Hosts must limit their transmission rates to match what the network can handle at any given time or else suffer high sender cooperation, to provide protection from misbehaving senders, and to keep offered load close to network capacity at all times.Our analytic and simulation results show that the algorithm converges, without oscillation, to a small and stable overload, and that it provides a bounded and predictable level of packet loss to cooperating senders.

A packet-switching network with photonic data path, Blazenet, that provides low delay and has minimal memory requirements is described. It can be extended to support multicast and priority delivery. The Blazenet design is described, addressing the issues of packet-switching and traffic congestion. A detailed switching node design is presented. Extended features that can be incorporated into Blazenet's design-priority traffic, limiting packet lifetime, and broadcast and multicast-are described. Some issues of the higher layers that have direct implication on Blazenet's operation are presented.>

Multicasting, the transmission of a packet to a group of hosts, is an important service for improving the efficiency and robustness of distributed systems and applications. Although multicast capability is available and widely used in local area networks, when those LANs are interconnected by store-and-forward routers, the multicast service is usually not offered across the resulting internetwork . To address this limitation, we specify extensions to two common internetwork routing algorithms—distance-vector routing and link-state routing—to support low-delay datagram multicasting beyond a single LAN. We also describe modifications to the single-spanning-tree routing algorithm commonly used by link-layer bridges, to reduce the costs of multicasting in large extended LANs. Finally, we discuss how the use of multicast scope control and hierarchical multicast routing allows the multicast service to scale up to large internetworks.

The problem of building a scalable shared memory multiprocessor can be reduced to that of building a scalable memory hierarchy, assuming interprocessor communication is handled by the memory system. In this paper, we describe the VMP-MC design, a distributed parallel multi-computer based on the VMP multiprocessor design, that is intended to provide a set of building blocks for configuring machines from one to several thousand processors. VMP-MC uses a memory hierarchy based on shared caches, ranging from on- chip caches to board-level caches connected by busses to, at the bottom, a high-speed fiber optic ring. In addition to describing the building block components of this architecture, we identify the key performance issues associated with the design and provide performance evaluation of these issues using trace-drive simulation and measurements from the VMP. This work was sponsored in part by the Defense Advanced Re- search Projects Agency under Contract N00014-88-K-0619.

Communication in modern distributed systems demands low-latency transaction-oriented communication rather than stream-oriented communication as in the past. The performance and functionality of current standard transport protocols has become a major limitation in the move to higher-speed networks and larger-scale, more sophisticated distributed systems. An overview is presented of the versatile message transaction protocol (VMTP) developed to address these limitations. The authors then present measurements of VMTP performance in actual use in the V distributed system, showing that its performance matches their objectives.>

A clear target for computer communication technology is to support a high-performance global internetwork. Current internetworking approaches use either concatenated virtual circuits, as in X.75, or a “universal” internetwork datagram, as in the DoD Internet IP protocol and the ISO connectionless network protocol (CLNP). Both approaches have significant disadvantages.This paper describes Sirpent™ (Source Internetwork Routing Protocol with Extended Network Transfer)1, a new approach to an internetwork architecture that makes source routing the basis for interconnection, rather than an option as in IP. Its benefits include simple switching with low per-packet processing and delay, support for accounting and congestion control, and scalability to a global internetwork. It also supports flexible, user-controlled routing such as required for security, policy-based routing and realtime applications. We also propose a specific internetwork protocol, called VIPER™2, as a realization of the Sirpent approach.

Caching introduces the overhead and complexity of ensuring consistency, reducing some of its performance benefits. In a distributed system, caching must deal with the additional complications of communication and host failures.

Naming is an important aspect of distributed system design. A naming system allows users and programs to assign character-string names to objects, and subsequently use the names to refer to those objects. With the interconnection of clusters of computers by wide-area networks and internetworks, the domain over which naming systems must function is growing to encompass the entire world. In this paper we address the problem of a global naming system, proposing a three-level naming architecture that consists of global, administrational, and managerial naming mechanisms, each optimized to meet the performance, reliability, and security requirements at its own level. We focus in particular on a decentralized approach to the lower levels, in which naming is handled directly by the managers of the named objects. Client-name caching and multicast are exploited to implement name mapping with almost optimum performance and fault tolerance. We also show how the naming system can be made secure. Our conclusions are bolstered by experience with an implementation in the V distributed operating system.

VMP is an experimental multiprocessor being developed at Stanford University, suitable for high-performance workstations and server machines. Its primary novelty lies in the use of software management of the per-processor caches and the design decisions in the cache and bus that make this approach feasible. The design and some uniprocessor trace-driven simulations indicating its performance have been reported previously. Initial experience with the VMP design, based on a running prototype as well as various refinements to the design, is presented. Performance evaluation is based both on measurement of actual execution as well as trace-driven simulation of multiprocessor executions from the Mach operating system.>

Current host network interface protocols limit performance visible to applications, waste critical host resources such as system bus and main memory bandwidth, and offer little protection against network malfunctions or hostile remote users. The authors present UNDIP, a host-network interface protocol that addresses these problems. The protocol is adaptable to networks with widely different switching techniques, different host system architectures, and different transport protocols. The authors describe the key design aspects as well as an implementation of UNDIP on a prototype network adapter board for the VMP multiprocessor system. They also show the performance advantage of UNDIP using preliminary measurements derived from the prototype.>

Current communication architectures suffer from a growing collection of protocols in the host operating systems, gateways and applications, resulting in increasing implementation and maintenance cost, unreliability and difficulties with interoperability. The remote procedure call (RPC) approach has been used in some distributed systems to contain the diversity of application layer protocols within the procedure call abstraction. However, the same technique cannot be applied to lower layer protocols without violating the strict notion of layers.

High performance computer communication between multiprocessor nodes requires significant improvements over conventional host-to-network adapters. Current host-to-network adapter interfaces impose excessive processing, system bus and interrupt overhead on a multiprocessor host. Current network adapters are either limited in function, wasting key host resources such as the system bus and the processors, or else intelligent but too slow, because of complex transport protocols and because of an inadequate internal memory architecture. Conventional transport protocols are too complex for hardware implementation and too slow without it.

An extended record facility is described that supports multi-module records by providing:

Communication systems are undergoing a change in use from stream to request-response or transaction communication. In addition, communication systems are becoming increasingly based on high-speed, low delay, low error rate channels. These changes call for a new generation of networks, network interfaces, and transport protocol design. The performance characteristics of request-response protocols on these high-performance networks should guide the design of this new generation, yet relatively little data of this nature is available.

A log service provides efficient storage and retrieval of data that is written sequentially (append-only) and not subsequently modified. Application programs and subsystems use log services for recovery, to record security audit trails, and for performance monitoring. Ideally, a log service should accommodate very large, long-lived logs, and provide efficient retrieval and low space overhead.

A uniform I/O interface allows programs to be written relatively independently of specific I/O services and yet work with a wide variety of the I/O services available in a distributed environment. Ideally, the interface provides this uniform access without excessive complexity in the interface or loss of performance. However, a uniform interface does not arise from careful design of individual system interfaces alone; it requires explicit definition. In this paper, the UIO (uniform I/O) system interface that has been used for the past five years in the V distributed operating system is described, with the focus on the key design issues. This interface provides several extensions beyond the I/O interface of UNIX™, including support for record I/O, locking, atomic transactions, and replication, as well as attributes that indicate whether optional semantics and operations are available. Experience in using and implementing this interface with a variety of different I/O services is described, along with the performance of both local and network I/O. It is concluded that the UIO interface provides a uniform I/O system interface with significant functionality, wide applicability, and no significant performance penalty.

VMP is an experimental multiprocessor that follows the familiar basic design of multiple processors, each with a cache, connected by a shared bus to global memory. Each processor has a synchronous, virtually addressed, single master connection to its cache, providing very high memory bandwidth. An unusually large cache page size and fast sequential memory copy hardware make it feasible for cache misses to be handled in software, analogously to the handling of virtual memory page faults. Hardware support for cache consistency is limited to a simple state machine that monitors the bus and interrupts the processor when a cache consistency action is required. In this paper, we show how the VMP design provides the high memory bandwidth required by modern high-performance processors with a minimum of hardware complexity and cost. We also describe simple solutions to the consistency problems associated with virtually addressed caches. Simulation results indicate that the design achieves good performance providing data contention is not excessive.

This paper studies the performance of single-user workstations that access files remotely over a local area network. From the environmental, economic, and administrative points of view, workstations that are diskless or that have limited secondary storage are desirable at the present time. Even with changing technology, access to shared data will continue to be important. It is likely that some performance penalty must be paid for remote rather than local file access. Our objectives are to assess this penalty and to explore a number of design alternatives that can serve to minimize it. Our approach is to use the results of measurement experiments to parameterize queuing network performance models. These models then are used to assess performance under load and to evahrate design alternatives. The major conclusions of our study are: (1) A system of diskless workstations with a shared file server can have satisfactory performance. By this, we mean performance comparable to that of a local disk in the lightly loaded case, and the ability to support substantial numbers of client workstations without significant degradation. As with any shared facility, good design is necessary to minimize queuing delays under high load. (2) The key to efficiency is protocols that allow volume transfers at every interface (e.g., between client and server, and between disk and memory at the server) and at every level (e.g., between client and server at the level of logical request/response and at the level of local area network packet size). However, the benefits of volume transfers are limited to moderate sizes (8-16 kbytes) by several factors. (3) From a performance point of view, augmenting the capabilities of the shared file server may be more cost effective than augmenting the capabilities of the client workstations. (4) Network contention should not be a performance problem for a lo-Mbit network and 100 active workstations in a software development environment.

The extensive use of local networks is beginning to drive requirements for internetwork facilities that connect these local networks. In particular, the availability of multicast addressing in many local networks and its use by sophisticated distributed applications motivates providing multicast across internetworks.

Article Free Access Share on Preemptable remote execution facilities for the V-system Authors: Marvin M. Theimer Computer Science Department, Stanford University, Stanford, CA Computer Science Department, Stanford University, Stanford, CAView Profile , Keith A. Lantz Computer Science Department, Stanford University, Stanford, CA Computer Science Department, Stanford University, Stanford, CAView Profile , David R. Cheriton Computer Science Department, Stanford University, Stanford, CA Computer Science Department, Stanford University, Stanford, CAView Profile Authors Info & Claims SOSP '85: Proceedings of the tenth ACM symposium on Operating systems principlesDecember 1985 Pages 2–12https://doi.org/10.1145/323647.323629Published:01 December 1985Publication History 227citation736DownloadsMetricsTotal Citations227Total Downloads736Last 12 Months33Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

The V kernel supports an abstraction of processes, with operations for interprocess communication, process management, and memory management. This abstraction is used as a software base for constructing distributed systems. As a distributed kernel, the V kernel makes intermachine boundaries largely transparent. In this environment of many cooperating processes on different machines, there are many logical groups of processes. Examples include the group of tile servers, a group of processes executing a particular job, and a group of processes executing a distributed parallel computation. In this paper we describe the extension of the V kernel to support process groups. Operations on groups include group interprocess communication, which provides an application-level abstraction of network multicast. Aspects of the implementation and performance, and initial experience with applications are discussed.

Local networking can be treated as a subset of internetworking for remote terminal access and file transfer. However, a distributed operating system, such as the V-System uses a local network more as an extended backplane than a fast, minature long-haul network.

The distributed V kernel is a message-oriented kernel that provides uniform local and network interprocess communication. It is primarily being used in an environment of diskless workstations connected by a high-speed local network to a set of file servers. We describe a performance evaluation of the kernel, with particular emphasis on the cost of network file access. Our results show that over a local network:

Thoth is a portable real-time operating system which has been developed at the University of Waterloo. Various configurations of Thoth have been running since May 1976; it is currently running on two minicomputers with quite different architectures (Texas Instruments 990 and Data General NOVA).

This paper studies methods for finding minimum spanning trees in graphs. Results include 1. several algorithms with $O(m\log \log n)$ worst-case running times, where n is the number vertices and m is the number of edges in the problem graph; 2. an $O(m)$ worst-case algorithm for dense graphs (those for which m is $\Omega (n^{1 + \varepsilon } )$ for some positive constant $\varepsilon $); 3. an $O(n)$ worst-case algorithm for planar graphs; 4. relationships with other problems which might lead general lower bound for the complexity of the minimum spanning tree problem.