waashk/acm huggingface dataset:
the implementation of guaranteed, reliable, secure broadcast networks  this paper depicts a conceptually simple and easy to implement protocol that provides reliable and secure broadcast/multicast communication. the methodology used in this protocol is surprisingly simple. three logical nodes are enforced in the network - a central retransmitter, a designated acknowledger, and a (many when needed) playback recorder(s). through the coordinated service of the three nodes, every user node can be guaranteed to receive all broadcast messages in the correct temporal order. a fourth logical node, the security controller, can be added to the protocol to provide security-related services such as user authentication, message encryption, etc. this protocol (grsb - guaranteed, reliable, secure broadcast) can be implemented in many types of networks - local area networks, wide area networks, as well as satellite communications. some of its implementation and performance issues are also discussed in the paper.  lawrence c. n. tseung keh-chiang yu
edmund: a multicast kernel for distributed application  although many local area networks and operating systems support the use of multicast communications, multicast communications have remained primarily an interesting research tool. however, the growing research interest in multimedia and hypermedia for knowledge-based models and cooperative work environments, and the need for object migration in distributed systems, suggest that there are other applications that could benefit from the use of multicast.  this paper presents an overview of edmund, a light weight kernel that supports interprocess multicast messaging on a network of intel 80286 personal computers, as well as some of our preliminary research results which demonstrate the uses and benefits of multicast communication.  larry hughes
transputer-based parallel processing products  computer system architects (csa) designs, manufactures, and sells products which use parallel processing to provide low-cost, high-compute performance to the scientific, engineering, and educational marketplace. through its close ties with industry and university research, csa remains on the leading edge of parallel processing technology.  the company was started in 1981 as a consulting firm, offering contract design of high speed computer architectures. contracts with companies such as hewlett-packard, burroughs, and floating point systems provided the internal funding for development of a family of computing products using inmos transputers. the transputer is a high-performance 32-bit microprocessor specifically designed to function as a component processor in a network of processors.  corporate computer system architects
organization of invalidation reports for energy-efficient cache invalidation in mobile environments in a wireless environment, mobile clients often cache frequently accessed data to reduce contention on the limited wireless bandwidth. however, it is difficult for clients to ascertain the validity of theory cache content because of their frequent disconnection. one promising cache invalidation approach is the bit-sequences scheme that organizes invalidation reports as a set of binary bit sequences with an associated set of timestamps. the report is periodically broadcast by the server to clients listening to the communication channel. while the approach has been shown to be effective, it is not energy efficient as clients are expected to examine the entire invalidation report. in this paper, we reexamine the bit -sequences method and study different organizations of the invalidation report to facilitate clients to selectively tune to the portion of the report that are of interest to them. this allows the clients to minimize the power consumption when invalidating their cache content. we conducted extensive studies based on a simulation model. our study shows that, compared to the bit-sequences approach, the proposed schemes are not only equally effective in salvaging the cache content but are more efficient in energy uti. kian-lee tan
comparing software and hardware schemes for reducing the cost of branches  pipelining has become a common technique to increase throughput of the instruction fetch, instruction decode, and instruction execution portions of modern computers. branch instructions disrupt the flow of instructions through the pipeline, increasing the overall execution cost of branch instructions. three schemes to reduce the cost of branches are presented in the context of a general pipeline model. ten realistic unix domain programs are used to directly compare the cost and performance of the three schemes and the results are in favor of the software-based scheme. for example, the software-based scheme has a cost of 1.65 cycles/branch vs. a cost of 1.68 cycles/branch of the best hardware scheme for a highly pipelined processor (11-stage pipeline). the results are 1.19 (software scheme) vs. 1.23 cycles/branch (best hardware scheme) for a moderately pipelined processor (5-stage pipeline).  w. w. hwu t. m. conte p. p. chang
tree multicast strategies in mobile, multishop wireless networks  tree multicast is a well established concept in wired networks. two versions, per- source tree multicast (e.g., dvmrp) and shared tree multicast (e.g., core based tree), account for the majority of the wireline implementations. in this paper, we extend the tree multicast concept to wireless, mobile, multihop networks for applications ranging from ad hoc networking to disaster recovery and battlefield. the main challenge in wireless, mobile networks is the rapidly changing environment. we address this issue in our design by: (a) using "soft state"; (b) assigning different roles to nodes depending on their mobility (2-level mobility model); (c) proposing an adaptive scheme which combines shared tree and per-source tree benefits, and (d) dynamically relocating the shared tree rendezvous point (rp). a detailed wireless simulation model is used to evaluate various multicast schemes. the results show that per-source trees perform better in heavy loads because of the more efficient traffic distribution; while shared trees are more robust to mobility and are more scalable to large network sizes. the adaptive tree multicast scheme, a hybrid between shared tree and per-source tree, combines the advantages of both and performs consistently well across all load and mobility scenarios. the main contributions of this study are: the use of a 2-level mobility model to improve the stability of the shared tree, the development of a hybrid, adaptive per-source and shared tree scheme, and the dynamic relocation of the rp in the shared tree.  mario gerla ching-chuan chiang lixia zhang
calculating availability and performability measures of repairable computer systems using randomization  repairable computer systems are considered, the availability behavior of which can be modeled as a homogeneous markov process. the randomization method is used to calculate various measures over a finite observation period related to availability modeling of these systems. these measures include the distribution of the number of events of a certain type, the distribution of the length of time in a set of states, and the probability of a near- coincident fault. the method is then extended to calculate performability distributions. the method relies on coloring subintervals of the finite observation period based on the particular application, and then calculating the measure of interest using these colored intervals.  edmundo de souza e silva h. richard gail
a comparison of two token-passing bus protocols  a well known disadvantage of standard token-passing in ring and bus networks is the waste of channel bandwidth often seen in lightly loaded or asymmetric systems. it is possible to make use of the broadcast mechanism in token bus systems to distribute nearly up-to-date information about the state of individual stations to the entire system. one such scheme involves the determination of a randomly varying set of more active stations. these stations are given a chance to form a second logical ring above the standard logical ring that characterizes the token bus. the transmission cycles of the system can thus be made to alternate between standard token-passing and transmission cycles, and the cycles of token-passing and transmission within the logical ring of more active stations. we assume that each station makes at most one transmission when given the chance to transmit. for poisson arrivals and otherwise general input distributions, the cycle-time distribution of the token is derived for each kind of cycle. an important random variable is the random token turnaround time seen by individual stations. for lightly loaded stations this time tends to be larger than for heavily loaded stations. the distribution of this random time, simple performance measures, and a comparative measure of stability, showing the adaptive scheme to be more stable than the standard, are obtained.  v rego
a pragmatic view of distributed processing systems  this course provides an overview of state-of-the-art concepts and problems associated with implementing a distributed processing system. it defines what constitutes a distributed system and discusses contemporary models of distributed systems. the tutorial describes case studies including ethernet, hyperchannel, nestar, cluster bus, and ungerman-bass net-one systems. a survey of design issues associated with system software, interconnection topology, and new hardware concepts is presented before concluding with observations on future system concepts.  kenneth j. thurber
can dataflow subsume von neumann computing?  we explore the question: "what can a von neumann processor borrow from dataflow to make it more suitable for a multiprocessor?" starting with a simple, "risc-like" instruction set, we show how to change the underlying processor organization to make it multithreaded. then, we extend it with three instructions that give it a fine-grained, dataflow capability. we call the result p-risc, for "parallel risc." finally, we discuss memory support for such multiprocessors. we compare our approach to existing mimd machines and to other dataflow machines.  r. s. nikhil
energy efficiency of tcp in a local wireless environment  the focus of this paper is to analyze the energy consumption performance of various versions of tcp, namely, tahoe, reno and newreno, for bulk data transfer in an environment where channel errors are correlated. we investigate the performance of a single wireless tcp connection by modeling the correlated packet loss/error process (e.g., as induced by a multipath fading channel) as a first-order markov chain. based on a unified analytical approach, we compute the throughput and energy performance of various versions of tcp. the main findings of this study are the (1) error correlations significantly affect the energy performance of tcp (consistent with analogous conclusions for throughput), and in particular they result in considerably better performance for tahoe and newreno than iid errors, and (2) the congestion control mechanism implemented by tcp does a good job at saving energy as well, by backing off and idiling during error bursts. an interesting conclusion is that, unlike throughput, the energy efficiency metric may be very sensitive to the tcp version used and to the choice of the protocol parameters, so that large gains appear possible.  michele zorzi ramesh r. rao
comparison of hypercube, hypernet, and symmetric hypernet architectures  hypercube has been the most popular topology for developing multiprocessor supercomputers because of its connectivity, regularity, symmetry and algorithmic mapping properties. however, if a hypercube needs to be expanded at some future time, both hardware configuration and communication software of each node has to be altered because its node degree is not constant. hwang and ghosh proposed a new interconnection network called hypernet which has a constant node degree and is easily expandable. however, its components count increases unsymmetrically with the increase in size. we propose a new topology called symmetric hypernet which grows symmetrically with the increase in dimension and hierachical level. the nodes in the symmetric net are functionally and physically separated as io nodes and computation nodes to avoid traffic congestion and message delays. the io nodes are placed uniformly among the processing nodes. the system can be dynamically partitioned into subsystems, each of which may be dedicated to serve a user's request(s). the system analysis can be done with the help of analytical models to serve a user's request(s). the system analysis can be done with the help of analytical models to determine how different structures would affect system performance.  r. p. kaushal j. s. bedi
issues in using darpa domain names for computer mail  although the principle goal of the darpa domain name project is to provide a distributed name resolution mechanism for host names in the darpa internet, it is envisioned that the domain naming scheme will also support names for mailboxes in a global mail system that extends to mail networks beyond the darpa internet. in addition to overviewing the fundamental ideas behind the domain name scheme and outlining a proposal for using domain names as an umbrella naming system for computer mail, we discuss the administrative and technical problems involved in using domain names in the global mail system.  douglas e. comer larry l. peterson
workload characterization (tutorial): issues and approaches  workload characterization is that branch of performance evaluation which concerns itself with the measurement and modeling of the workloads to be processed by the system being evaluated. since all performance indices of interest are workload-dependent, there is no evaluation study that does not require the characterization of one or more workloads. in spite of the importance of the problem, our knowledge in this area leaves much to be desired.  the tutorial addresses the main issues, both resolved and unresolved, in the field, and surveys the major approaches that have been proposed and are in use. modern methods for designing executable artificial workloads, as well as the applications of these techniques in system procurement, system tuning, and capacity planning are emphasized.  domenico ferrari
distributed shared memory in a loosely coupled distributed system  this work outlines the development and performance validation of an architecture for distributed shared memory in a loosely coupled distributed computing environment. this distributed shared memory may be used for communication and data exchange between communicants on different computing sites; the mechanism will operate transparently and in a distributed manner. this paper describes the architecture of this mechanism and metrics which will be used to measure its performance. we also discuss a number of issues related to the overall design and what research contribution such an implementation can provide to the computer science field.  b. d. fleisch
local management of a global resource in a communication network  this paper introduces a new distributed data object called resource controller that provides an abstraction for managing the consumption of a global resource in a distributed system. examples of resources that may be managed by such an object include; number of messages sent, number of nodes participating in the protocol, and total cpu time consumed.  the resource controller object is accessed through a procedure that can be invoked at any node in the network. before consuming a unit of resource at some node, the controlled algorithm should invoke the procedure at this node, requesting a permit or a rejection.  the key characteristics of the resource controller object are the constraints that it imposes on the global resource consumption. an (m, w)-controller guarantees that the total number of permits granted is at most m; it also ensures that, if a request is rejected, then at least m---w permits are eventually granted, even if no more requests are made after the rejected one.  in this paper, we describe several message and space- efficient implementations of the resource controller object. in particular, we present an (m, w)-controller whose message complexity is o(n log2n log(m/(w \\+ 1)) where n is the total number of nodes. this is in contrast to the o(nm) message complexity of a fully centralized controller which maintains a global counter of the number of granted permits at some distinguished node and relays all the requests to the node.  yehuda afek baruch awerbuch serge plotkin michael saks
location-aware mobile applications based on directory services  location-aware applications are becoming increasingly attractive due to the widespread dissemination of wireless networks and the emergence of small and cheap locating technologies. we developed a location information server that simplifies and speeds up the development of these applications by offering a set of generic location retrieval and notification services to the application. the data model and the access protocols of these services are based on the x.500 directory service and the lightweight directory access protocol ldap since these are becoming the standard attribute-value-pair retrieval mechanisms for internet and intranet environments. this approach establishes a smooth migration path from conventional to location-aware applications. the paper presents the location information server concepts, defines its directory data model and access services, and discusses the implementation options of the loca- tion information server.  henning maass
a minimal duplex connection capability in the top three layers of the osi reference model  a minimal duplex connection capability is described as the ability to open, close, abort, and transfer data through a duplex connection between two application processes. the goal of this paper is to describe a minimal duplex connection capability for the top three layers of the open systems interconnection (osi) reference model that will be appropriate for use by very small open systems such as home computers. such a connection capability would allow these small systems to interconnect with machines of arbitrary size. the approach taken is to use only the parameters on service primitives that are absolutely required to accomplish this connection service. the protocol and services necessary to accomplish such a minimal connection are described for the application, presentation, and session layers of the osi reference model. the existing draft proposals for services and protocol for the session layer provide a basis for this duplex connection service. a minor modification to the session draft proposals is suggested. the services for the presentation and application layer are defined in terms of the tentative service primitives being considered in the international standards efforts. the transparent initial context defined for the presentation layer is used to minimize the work of that layer. the benefits of this minimal duplex connection capability are then discussed from the point of view of very small open systems.  m. f. dolan
an analysis of naming conventions for distributed computer systems  name servers that collectively manage a global name space facilitate sharing of resources in a large internetwork by providing means of locating named objects. the efficiency with which the name space can be managed is strongly influenced by the adopted naming convention. structured name spaces are shown to simplify name space management from both an administrative and system viewpoint. formulae have been derived which allow one to quantitatively measure the effect of the distributed name server configuration on a given client's level of performance. in general, the cost of a name server query can be reduced by distributing replicated copies of name server database entries in a way that exploits the locality of clients' reference patterns.  douglas b. terry
automatically tuned collective communications  the performance of the mpi's collective communications is critical in most mpi-based applications. a general algorithm for a given collective communication operation may not give good performance on all systems due to the differences in architectures, network parameters and the storage capacity of the underlying mpi implementation. in this paper we discuss an approach in which the collective communications are tuned for a given system by conducting a series of experiments on the system. we also discuss a dynamic topology method that uses the tuned static topology shape, but re-orders the logical addresses to compensate for changing run time variations. a series of experiments were conducted comparing our tuned collective communication operations to various native vendor mpi implementations. the use of the tuned collective communications resulted in about 30 percent to 650 percent improvement in performance over the native mpi implementations.  sathish s. vadhiyar graham e. fagg jack dongarra
performance models of token ring local area networks  this paper presents a simple heuristic analytic algorithm for predicting the "response times" of messages in asymmetric token ring local area networks. a description of the token ring and the model is presented in section 2 the algorithm is described in section 3 and the empirical results in section 4. the analytic results were compared against a detailed simulation model and the results are extremely close over a wide range of models.  local area networks (or lans) offer a very attractive solution to the problem of connecting a large number of devices distributed over a small geographic area. they are an inexpensive readily expandable and highly flexible communications media. they are the backbone of the automated office - a significant component of the office of the future.  this importance of lans in the future of applied computer science has resulted in a tremendous burst of interest in the study of their behaviour. there are already many different lan architectures proposed and studied in the literature [tropper 81] [tannenbaum 81] [babic 78] [metcalfe 76] [clark 78] one lan architecture is significant for several reasons. this architecture is the token ring [carsten 77]. it has attracted interest because of its simplicity fairness and efficiency. the interest it has generated has resulted in the proposal of several different versions. this paper concentrates on one of these versions - the single token token ring protocol as described in [bux 81]. this particular version is attractive because of its overall simplicity and reliability. this paper presents an algorithm for predicting response times in a token ring with the single token protocol.  robert berry k. mani chandy
bimodal multicast  there are many methods for making a multicast protocol "reliable." at one end of the spectrum, a reliable multicast protocol might offer tomicity guarantees, such as all-or- nothing delivery, delivery ordering, and perhaps additional properties such as virtually synchronous addressing. at the other are protocols that use local repair to overcome transient packet loss in the network, offering "best effort" reliability. yet none of this prior work has treated stability of multicast delivery as a basic reliability property, such as might be needed in an internet radio, television, or conferencing application. this article looks at reliability with a new goal: development of a multicast protocol which is reliable in a sense that can be rigorously quantified and includes throughput stability guarantees. we characterize this new protocol as a "bimodal multicast" in reference to its reliability model, which corresponds to a family of bimodal probability distributions. here, we introduce the protocol, provide a theoretical analysis of its behavior, review experimental results, and discuss some candidate applications. these confirm that bimodal multicast is reliable, scalable, and that the protocol provides remarkably stable delivery throughput.  kenneth p. birman mark hayden oznur ozkasap zhen xiao mihai budiu yaron minsky