A focus of the paper is on the performance of cloud computing servers in cyber-physical systems (CPS) applications that aggregate data over large spatial regions over long spans of time. Examples of such CPS applications include those that: sense and respond to change in the environment such as forest fires or mud slides, help utilities such as water management districts monitor water quality and flow, and traffic management systems. This paper evaluates the benefits of architectures based on Cloud computing systems for such CPS applications. We use earthquake detection as a concrete example for this application class. The focus of the paper is on the performance of Platform-as-a-Service systems. The paper described the relative advantages of different types of services in the next few sections.

Abstract This paper describes a methodology for developing and verifying a class of distributed systems in which the state space may be discrete or continuous. Our focus is on systems where changes are local in that a small number of components change state while the remainder of the system is unchanged. A proof methodology is developed that ensures global properties, such as invariants and convergence, by guaranteeing local properties within subsystems. This methodology is used to prove the correctness of concrete examples. We present a PVS library of theorems and proofs that can be used to reduce the work required to develop and verify programs in this class. A transformation of these libraries to Java is also outlined.

This paper proposes a methodology for designing a class of algorithms for computing functions in dynamic distributed systems in which communication channels and processes may cease functioning temporarily or permanently. Communication and computing may be interrupted by an adversary or by environmental factors such as noise and power loss. The set of processes may be partitioned into subsets that cannot communicate with each other; algorithms in which all such subsets behave in a similar fashion, regardless of size and identities of processes, are called self-similar algorithms. Algorithms adapt to changing conditions, speeding up or slowing down depending on the resources available. The paper presents necessary and sufficient conditions for the application of a self-similar strategy. Self-similar algorithms are developed for several problems by applying the methodology.

This tutorial deals with applications that help systems and individuals respond to critical conditions in their environments. The identification of critical conditions requires correlating vast amounts of data within and outside an enterprise. Conditions that signal opportunities or threats are defined by complex patterns of data over time, space and other attributes. Systems and individuals have models (expectations) of behaviors of their environments, and applications notify them when reality - as determined by measurements and estimates - deviate from their expectations. Components of event systems are also sent information to validate their current models and when specific responses are required. Valuable information is that which supports or contradicts current expectations or that which requires an action on the part of the receiver. A major problem today is information overload; this problem can be solved by identifying what information is critical, complementing existing pull technology with sophisticated push technology, and filtering out non-critical data.

The analysis, and eventual approval or rejection, of new enterprise information technology (IT) initiatives often proceeds on the basis of informal estimates of return on investment. Investment in new IT initiatives includes the costs of hardware, software licenses, application development tailored to the enterprise, and maintenance. Returns are typically estimated informally in terms of cost savings or revenue increases. This paper makes the case for evaluating certain IT investments in the same way as investments in factories and other resources have been evaluated for decades. Just as industrial factories create value by transforming raw materials into finished products, some IT investments, which we call “information factories”, create value by transforming raw information (events) into structured data (and possibly actions based on that data). The return on investment is estimated by the difference between the economic value of the structured data and concomitant actions (the “finished product”) and that of the data available within the enterprise, from its partners and customers, and from the Internet (the “raw materials”). This paper introduces the concept of the information factory, and explores design considerations for maximizing the economic efficiency of information factories.

Only a handful of fundamental mechanisms for synchronizing the access of concurrent threads to shared memory are widely implemented and used. These include locks, condition variables, semaphores, barriers, and monitors. In this paper, we introduce a new synchronization mechanism-monotonic counters-and make a case for its addition to this group. Unlike most other synchronization mechanisms, monotonic counters were designed primarily for multiprocessing, rather than for systems programming. Counters have a very simple definition: a counter object has a nonnegative value, an Increment operation, and a Check operation. Increment atomically increases the counter, and Check suspends until the counter reaches a specified level. We demonstrate that many practical thread synchronization patterns can be expressed more elegantly using counters than with other synchronization mechanisms. Of particular importance, the monotonicity of counters can be used to guarantee deterministic synchronization and the equivalence of multithreaded and sequential execution. In terms of implementation, counters are distinguished from traditional synchronization mechanisms, in that they have a dynamically varying number of thread suspension queues. We give several examples of multithreaded programs that use counter synchronization, and give an implementation of counters on top of locks and condition variables.

Article Micro-option: a method for optimal selection and atomic reservation of distributed resources in a free market environment Share on Authors: Roman Ginis 256-80 Caltech, Pasadena, CA 91125, California Institute of Technology 256-80 Caltech, Pasadena, CA 91125, California Institute of TechnologyView Profile , K. Mani Chandy 256-80 Caltech, Pasadena, CA 91125, California Institute of Technology 256-80 Caltech, Pasadena, CA 91125, California Institute of TechnologyView Profile Authors Info & Claims EC '00: Proceedings of the 2nd ACM conference on Electronic commerceOctober 2000 Pages 207–214https://doi.org/10.1145/352871.352894Online:17 October 2000Publication History 2citation319DownloadsMetricsTotal Citations2Total Downloads319Last 12 Months2Last 6 weeks0 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 SiteGet Access

This paper identifies some of the issues that need to be explored in systems that support content-based delivery. Distributed systems today are based on address-based delivery of messages. Each message carries the unique addresses of the intended recipients. The idea in content-based delivery is that information is delivered to those objects that have subscribed for that information. The ideas on content-based delivery reported are based partly on Roman Ginis' doctoral dissertation at Caltech. The ideas on directories reported are based partly on Eve Schooler's doctoral dissertation at Caltech.

We specify an abstract model for dynamic distributed control systems in which the component objects make local decisions based on system-wide constraints and approximate global state. We focus on the issue of distributed resource management, exploring a solution that is both compositional and scalable because it builds global events into the Java infrastructure by exploiting its multicast facilities. © 1998 John Wiley & Sons, Ltd.

We consider a system with the infrastructure for the creation and interconnection of large numbers of distributed persistent objects. This system is exemplified by the Internet: potentially, every appliance and document on the Internet has both persistent state and the ability to interact with large numbers of other appliances and documents on the Internet. This paper elucidates the characteristics of such a system, and proposes the compositional requirements of its corresponding infrastructure. We explore the problems of specifying, composing, reasoning about and implementing applications in such a system. A specific concern of our research is developing the infrastructure to support structuring distributed applications by using sequential, choice and parallel composition, in the anarchic environment where application compositions may be unforeseeable and interactions may be unknown prior to actually occurring. The structuring concepts discussed are relevant to a wide range of distributed applications; our implementation is illustrated with collaborative Java processes interacting over the Internet, but the methodology provided can be applied independent of specific platforms.

This paper describes the design of a distributed system built using Java that supports peer-to-peer communication among processes spread across a network. We identify the requirements of a software layer that supports distributed computing, and we propose a design that meets those requirements. Our primary concerns are (I) the identification, specification, and implementation of software components that can be composed in different ways to develop correct distributed applications; (2) reasoning about the components systematically; and (3) providing services to the components. This paper deals with the last of these concerns. Though our implementation uses Java, the fundamental ideas apply to any object-oriented language that supports messaging and threads. Alternative implementations use such languages coupled with object request brokers or remote procedure invocation mechanisms.

Proposes a framework for the systematic design of directory-based distributed applications. We evaluate a space of directory designs using our framework. We present a case study consisting of design, implementation and analysis of directories for a multicast application. Our framework is based on a model that extends the formal concept of process knowledge in distributed systems. This concept is used informally in phrases such as "process p knows when it is in state s that process q is active". We show that this definition of knowledge is too strong for many distributed applications, including directory design. We propose a weaker concept: estimation. We describe the meaning of phrases of the form: "process p in state s estimates with probability 0.9 that process q is active". We specify directory design as an optimization problem with the objective function of maximizing estimation probabilities, and with constraints on the amount of bandwidth, computation and storage used. We show how this specification helps in a systematic analysts of alternative directory designs.

This paper proposes extensions of sequential programming languages for parallel programming that have the following features: 1) Dynamic Structures: The process structure is dynamic. Processes and variables can be created and deleted. 2) Paradigm Integration: The programming notation supports shared memory and message passing models. 3) Determinism: Demonstrating that a program is deterministic-all executions with the same input produce the same output-is straightforward, Programs can be written so that compilers can verify that the programs are deterministic. Nondeterministic constructs can be introduced in a sequence of refinement steps to obtain greater efficiency if required. The ideas have been incorporated in an extension of Fortran, but the underlying sequential imperative language is not central to the ideas described here. A compiler for the Fortran extension, called Fortran M, is available by anonymous ftp From Argonne National Laboratory. Fortran M has been used for a variety of parallel applications.>

Abstract A program property is a predicate on programs. In this paper we explore program properties for safety, progress and parallel composition, of the form U ⇀ V where U and V are either predicates on states of a program or program properties, and ⇀ satisfies three rules that are also enjoyed by implication. We show how such properties can be used to reason about concurrent programs. Our motivation is to explore methods of reasoning based on a very small number of widely-known rules.

In designing parallel languages, the concern for defining a simple virtual machine must be balanced against the need to efficiently map a program on a specific architecture. UC addresses this problem by separating the programming task from efficiency considerations. UC programs are designed using a small set of constructs that include reduction, parallel assignment, and fixed-point computation. The language also provides a map section that may optionally be used by a programmer to specify data mappings for the program. The authors describe the UC constructs and their implementation on the Connection Machine. They also present measurements of the compiler for simple benchmarks.>

This paper describes a notation for concurrent programs \ncalled PCN for Program Composition Notation. The \nnotation is being implemented at Caltech on multicomputers \n(a network of computers that communicate by \nsending and receiving messages). A fragment of this \nnotation has been implemented on a data-parallel computer \n- the Connection Machine - by Rajive Bagrodia \nat UCLA. PCN is an outgrowth of research on UNITY \n(1) and Strand (2). The central ideas underlying PCN \naxe discussed next.

This paper develops a message-based approach to discrete-event simulation. Although message-based simulators have the same expressive power as traditional discrete-event simulation lanuages, they provide a more natural environment for simulating distributed systems. In message-based simulations, a physical system is modeled by a set of message-communicating processes. The events in the system are modeled by message-communications. The paper proposes the entity construct to represent a message-communicating process operating in simulated time. A general wait until construct is used for process scheduling and message-communication. Based on these two notions, the paper proposes a language fragment comprising a small set of primitives. The language fragment can be implemented in any general-purpose, sequential programming language to construct a message-based simulator. We give an example of a message-based simulation language, called MAY, developed by implementing the language fragment in Fortran. MAY is in the public domain and is available on request.

We propose a methodology for the development of concurrent programs and apply it to an important class of problems: quiescence detection. The methodology is based on a novel view of programs. A key feature of the methodology is the separation of concerns between the core problem to be solved and details of the forms of concurrency employed in the target architecture and programming language. We begin development of concurrent programs by ignoring issues dealing with concurrency and introduce such concerns in manageable doses. The class of problems solved includes termination and deadlock detection.

Article Concurrent programming for the masses (invited address) Share on Author: Mani Chandy Department of Computer Sciences, The University of Texas, Austin, Texas Department of Computer Sciences, The University of Texas, Austin, TexasView Profile Authors Info & Claims PODC '85: Proceedings of the fourth annual ACM symposium on Principles of distributed computingAugust 1985 Pages 1–12https://doi.org/10.1145/323596.323597Online:01 August 1985Publication History 11citation187DownloadsMetricsTotal Citations11Total Downloads187Last 12 Months5Last 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 SiteGet Access

This paper presents an algorithm by which a process in a distributed system determines a global state of the system during a computation. Many problems in distributed systems can be cast in terms of the problem of detecting global states. For instance, the global state detection algorithm helps to solve an important class of problems: stable property detection. A stable property is one that persists: once a stable property becomes true it remains true thereafter. Examples of stable properties are “computation has terminated,” “ the system is deadlocked” and “all tokens in a token ring have disappeared.” The stable property detection problem is that of devising algorithms to detect a given stable property. Global state detection can also be used for checkpointing.

A Mean Value Analysis (MVA) approximation is presented for computing the average performance measures of closed-, open-, and mixed-type multiclass queuing networks containing Preemptive Resume (PR) and nonpreemptive Head-Of-Line (HOL) priority service centers.The approximation has essentially the same storage and computational requirements as MVA, thus allowing computationally efficient solutions of large priority queuing networks.The accuracy of the MVA approximation is systematically investigated and presented.It is shown that the approximation can compute the average performance measures of priority networks to within an accuracy of 5 percent for a large range of network parameter values.Accuracy of the method is shown to be superior to that of Sevcik's shadow approximation.

The problem of resolving conflicts between processes in distributed systems is of practical importance.A conflict between a set of processes must be resolved in favor of some (usually one) process and against the others: a favored process must have some property that distinguishes it from others.To guarantee fairness, the distinguishing property must be such that the process selected for favorable treatment is not always the same.A distributed implementation of an acyclic precedence graph, in which the depth of a process (the longest chain of predecessors) is a distinguishing property, is presented.A simple conflict resolution rule coupled with the acyclic graph ensures fair resolution of all conflicts.To make the problem concrete, two paradigms are presented: the well-known distributed dining philosophers problem and a generalization of it, the distributed drinking philosophers problem.

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.

Sunple criterta are given for determining whether a queuing network model has a product-form solution and is thus computationally tractable Categories and SubJect Descriptors.D.4.

Distributed deadlock models are presented for resource and communication deadlocks.Simple distributed algorithms for detection of these deadlocks are given.We show that all true deadlocks are detected and that no false deadlocks are reported.In our algorithms, no process maintains global information; all messages have an identical short length.The algorithms can be applied in distributed database and other message communication systems.

This paper presents a distributed algorithm to detect deadlocks in distributed data bases. Features of this paper are (1) a formal model of the problem is presented, (2) the correctness of the algorithm is proved, i.e. we show that all true deadlocks will be detected and deadlocks will not be reported falsely, (3) no assumptions are made other than that messages are received correctly and in order and (4) the algorithm is simple.

A method is proposed for reasoning about safety and liveness properties of message passing networks. The method is hierarchical and is based upon combining the specifications of component processes to obtain the specification of a network. The inference rules for safety properties use induction on the number of messages transmitted; liveness proofs use techniques similar to termination proofs in sequential programs. We illustrate the method with two examples: concatenations of buffers to construct larger buffers and a special case of Stenning protocol for message communication over noisy channels.

In this paper it is shown how the Dijkstra-Scholten scheme for termination detection in a diffusing computation can be adapted to detect termination or deadlock in a network of communicating sequential processes as defined by Hoare.

A knot in a directed graph is a useful concept in deadlock detection.A distributed algorithm for identifying a knot in a graph by using a network of processes is presented.The algorithm is based on the work of Dijkstra and Scholten.

We present a proof method for networks of processes in which component processes communicate exclusively through messages. We show how to construct proofs of invariant properties which hold at all times during network computation, and terminal properties which hold upon termination of network computation, if network computation terminates. The proof method is based upon specifying a process by a pair of assertions, analogous to pre-and post-conditions in sequential program proving. The correctness of network specification is proven by applying inference rules to the specifications of component processes. Several examples are proved using this technique.

As CPUs have become larger and more complex, it has become increasingly more difficult during hardware design and implementation to predict how well a CPU will perform. Furthermore, buyers of such machines have a similar problem in evaluating CPU performance among a diverse selection of computers, since MIP rates quoted by manufacturers may be misleading.

The problem of system simulation is typically solved in a sequential manner due to the wide and intensive sharing of variables by all parts of the system. We propose a distributed solution where processes communicate only through messages with their neighbors; there are no shared variables and there is no central process for message routing or process scheduling. Deadlock is avoided in this system despite the absence of global control. Each process in the solution requires only a limited amount of memory. The correctness of a distributed system is proven by proving the correctness of each of its component processes and then using inductive arguments. The proposed solution has been empirically found to be efficient in preliminary studies. The paper presents formal, detailed proofs of correctness.

This paper is concerned with the pros and cons of writing distributed applications software. Most applications software is highly sequential due to the sharing of variables. Here we focus attention on one such application: discrete-event simulatiom. We show how to develop distributed software for this application by taking a radically different view of the application. We outline proofs that our distributed software is correct. Our goal is to develop guidelines for writing distributed applications software.

A new property of queueing discipline, station balance , seems to explain why some disciplines yield product form solutions for queues and networks using nonexponential service disciplines and other disciplines do not. A queueing discipline satisfies station balance if rates at which customers receive service at each position of the queue are proportional to the probability that a customer arrives at that position. Station and local balance in queues and networks of queues are investigated. In addition to characterizing local balance and product form, the results of the paper generalize previous results on local balance to arbitrary differentiable service distribution functions.

This paper considers the selection of capacities, in two classes of open queueing network models of computer communication systems: 1) local-balanced queueing networks with multiple classes of customers and 2) the Reiser-Kobayashi diffusion approximation model. The problem of selecting optimal bandwidths for communication lines and switches and computing machinery is difficult due to 1) the economy of scale exhibited by components (i.e., the bandwidth per dollar increases with the total cost of the component) and 2) the discrete nature of computer/communication components (for instance it is possible to lease communication lines with 2400-Bd or 4800-Bd band-widths but not one with a 2401.3-Bd bandwidth). This paper develops aun algorithm to select servers taking both of these characteristics of server costs into account. The contribution of this paper is to discuss 1) the optimization of more general network models with 2) the consideration of more realistic tariffs and 3) more constraints on network behavior than were previously analyzed.

The problem of allocating files in a computer network is a complex combinatorial problem due to the number of integer design parameters involved. These parameters include system cost, number of copies of each file to be stored, and sites at which the copies should be stored. The tradeoffs between these parameters are discussed. The design problem is formulated as an integer programming problem. A branch and bound algorithm is proposed to solve the problem. A linear programming formulation which ignores integer restrictions (and allows a fraction of a file to reside at a site) is shown to yield integer solutions in most cases. In other words integer restrictions are satisfied automatically. A near-optimal heuristic is presented, along with computational results. An efficient method to solve the file allocation problem for medium-scale networks is proposed.

The objective of this paper is to relate models of multi-tasking in which task times are known or known to be equal to models in which task times are unknown. We study bounds on completion times and the applicability of optimal deterministic schedules to probabilistic models. Level algorithms are shown to be optimal for forest precedence graphs in which task times are independent and identically distributed exponential or Erlang random variables. A time sharing system simulation shows that multi-tasking could reduce response times and that response time is insensitive to multi-tasking scheduling disciplines.

The joint equihbrmm distribution of queue sizes in a network of queues containing N service centers and R classes of customers m derived The equilibrium state probabillUes have the general form P(S) = Cd(S) fl(xl)f2(x2) .fN(x~), where S is the state of the system, x, is the configuration of customers at the ~th service center, d(S) is a function of the state of the model, f, is a function that depends on the type of the zth service center, and C is a normalizing constant It is assumed that the eqmhbrlum probabfl~tles exmt and are unique Four types of service centers to model central processors, data channels, terminals, and routing delays are considered The queuemg dlSclphnes associated with these service centers include first-come-first-served, processor sharing, no queueing, and last-come-first-served Each customer belongs to a single class of customers while awaiting or receiving serwce at a service center, but may change classes and service centers according to fixed probabditms at the completion of a service request For open networks, state dependent arrival processes are considered Closed networks are those with no exogenous arrivals A network may be closed with respect to some classes of customers and open with respect to other classes of customers At three of the four types of serwce centers, the service times of customers are governed by probablhty dmtrlbutions hawng ratmnM Laplace transforms, different classes of customers hawng different distributions At first-come-first-served-type service centers, the service time distribution must be identical and exponentml for all classes of customers.Examples show how different classes of customers can affect models of computer systems.

Rollback and recovery (RR) is a method of enchancing the reliability of file or data base systems. At certain points in time, called checkpoints, a copy of the data or files is made on tape (or other storage devices). A chronological record is kept of all transactions which modify the data stored by the system; this record is called the audit trail. When an error is detected, the copy of the files or data made at the most recent checkpoint is loaded, and all transactions on the audit trail since this check point are reprocessed in chronological sequence, thus recovering from the error. This paper presents models and techniques which aid in determining optimal times for checkpoints.

Abstract The capacitated minimum spanning tree is an offspring of the minimum spanning tree and network flow problems. It has application in the design of multipoint linkages in elementary teleprocessing tree networks. Some theorems are used in conjunction with Little's branch and bound algorithm to obtain optimal solutions. Computational results are provided to show that the problem is tractable.

This paper investigates some of the effects of varying the number of central processing units (CPU's) available to a multiprogramming system both when parallel processing of a single task (multitasking) is allowed and is not allowed. The variables investigated are those that would be expected to control the CPU queue length distribution and include the degree of multiprogramming, CPU service discipline, CPU service distribution, the degree of cooperation between processors engaged in multitasking, and the ratio of CPU to I/O service capacity. The computer systems are modeled by queueing networks. Analytic results are displayed in many cases with supplementation by numeric and simulation solutions when convenient or necessary. It is demonstrated that under properly defined conditions doubling the number of CPU's in a system can more than double throughput. The effectiveness of multitasking in improving throughput is found to be fairly small if the degree of multiprogramming ranges from modest to high.

Reliability is an important aspect of any system. On-line diagnosis, parity check coding, triple modular redundancy, and other methods have been used to improve the reliability of computing systems. In this paper another aspect of reliable computing systems is explored. The problem is that of recovering error-free information when an error is detected at some stage in the processing of a program. If an error or fault is detected while a program is being processed and if it cannot be corrected immediately, it may be necessary to run the entire program again. The time spent in rerunning the program may be substantial and in some real time applications critical. Recovery time can be reduced by saving states of the program (all the information stored in registers, primary and secondary storage, etc.) at intervals, as the processing continues. If an error is detected the program is restarted from its most recently saved state. However, a price is paid in saving a state in the form of time spent storing all the relevant information in secondary storage. Hence it is expensive to save the state of the program too often. Not saving any state of the program may cause an unacceptably large recovery time. The problem that we solve is the following. Determine the optimum points at which the state of the program should be stored to recover after any malfunction.

The problem of designing a minimum cost network with multipoint linkages which connects several remote terminals to a data processing center is studied. The important aspects of a teleprocessing network are queue behavior at the terminals and the cost and reliability of the entire system. In this paper it is assumed that the rate and manner in which information is requested at the terminals is known and that acceptable line loadings are given. An algorithm that determines (in principle) the optimum minimum cost network subject to reliability constraints is developed. A heuristic based on Vogel's approximation method (VAM) and two other heuristics presented by Martin and Esau-Williams were compared with each other and with the optimal algorithm. The Esau-Williams heuristic seems to be the one that gives the best solution and Martin's requires the least processing time. It is shown experimentally that Martin's and Esau-Williams heuristics are, in fact, near-optimal heurstics in the sense that the solutions provided by these heuristics are generally very near the optimal solution. In this paper we make the assumption that all lines of the network have the same capacity.

This paper describes a set of techniques that can be used to optimally schedule a sequence of interrelated computational tasks on a multiprocessor computer system. Using a directed graph model to represent a computational process, two basic problems are solved here. First, given a set of computational tasks and the relationships between them, the tasks are scheduled such that the total execution time is minimized, and the minimum number of processors required to realize this schedule is obtained. The second problem is of a more general nature. Given k processors, the tasks are scheduled such that execution time is again minimized. Consideration is given to tasks of equal and unequal duration, and task preemption is not allowed.

The optimization of memory hierarchy involves the selection of types and sizes of memory devices such that the average access time to an information block is a minimum for a particular cost constraint. It is assumed that the frequency of usage of the information is known a priori. In this paper the optimization theory for a single task or program is reviewed and it is extended to a general case in multiprogramming when a number of tasks are executed concurrently. Another important extension treats the case when memories are available only in indivisible modules. Comparisons with conventional methods of solution as well as computational experience on the multiprogrammed and modular cases are given.