This paper presents a new hash chain traversal strategy which improves performance of hash chain based one-time authentication schemes. This work is motivated by the need for efficient message authentication in low-latency multicast systems. Proposed solutions such as TV-OTS rely on hash chain generated values for keys, achieving reliable security by using only a small subset of generated values from each chain. However, protocols using hash chains are limited by the rate at which a hash chain traversal is able to supply keys. The new algorithm uses the same structure as Fractal Hash Traversal, but eliminates redundant operations incurred when used with applications such as TV-OTS. Performance is measured in terms of savings and is proportional to the chain-distance between consecutively retrieved values. For a distance of delta, we achieve Theta(delta_2(delta)) savings, which is shown analytically and supported by empirical tests.

In recent years, much of the discussion involving “smart grids” has implicitly involved only the distribution side, notably advanced metering. However, today's electric systems have many challenges that also involve the rest of the system. An enabling technology for improving the power system, which has emerged in recent years, is the ability to measure coherent, real-time data. In this paper, we describe major challenges facing electrical generation and transmission today that availability of these measurements can help address. We overview applications using coherent, real-time measurements that are in use today or proposed by researchers. Specifically, we describe, normalize, and then quantitatively compare key factors for these power applications that influence how the delivery system should be planned, implemented, and managed. These factors include whether a person or computer is in the loop and (for both inputs and outputs) latency, rate, criticality, quantity, and geographic scope. From this, we abstract the baseline communications requirements of a data delivery system supporting these applications and suggest implementation guidelines to achieve them. Finally, we overview the state of the art in the supporting computer science areas of overlay networking and distributed computing (including middleware) and analyze gaps in commercial middleware products, utility standards, and issues that limit low-level network protocols from meeting these requirements when used in isolation.

GridStat is a QoS-managed middleware framework designed to replace the power grid's aging, inflexible, and slow data communications system. GridStat is a specialization of the publish-subscribe paradigm that takes advantage of the semantics of periodic updates of cached sensor data to provide data delivery with a per-subscriber rate, latency, and redundant paths. While GridStat is well-suited for delivery of sensor data over a wide-area network, its baseline one-way mechanisms are not suitable for round-trip invocations such as setting an actuator or calling between control centers. In this paper we present the design, implementation and experimental evaluation of Ratatoskr, a tunable remote procedure call mechanism that builds on the QoS semantics of GridStat and supports three kinds of redundancy. Additionally, user-defined pre- and post-condition predicates over GridStat status variables are built into the call semantics.

Given the major advantages of productivity and safety, the use of garbage collection (GC) in real-time systems has gained increasing attention. Guaranteeing garbage collection activities' worst-case execution time (WCET) is necessary for a real-time system to perform scheduling and schedulability analysis. This paper describes a detailed GC cost model for incremental mark-and-sweep GC exemplified by a modified Boehm-Demers-Weiser (BDW) collector. The GC cost model computes the WCET for garbage collection in terms of (1) the performance of collector operations and (2) the garbage collection load offered by a real-time task. Separating these aspects is a step along the road to an engineering approach to garbage collection in real-time systems, allowing prediction of system behavior from knowledge of component behavior and environmental specifications. The model incorporates the cost of write barriers that are needed to support incremental GC. To be useful for real-time systems, a model's predicted WCET must be no less than the actual WCET. However, unreasonably large overestimates are also problematic as they may lead to the incorrect conclusion that the application cannot be feasibly scheduled. A pessimism metric assesses the degree to which the model's predictions exceed the measured worst-case cost in particular instances.

The problem of finding survivable low-cost multicast trees having node-disjoint paths to destinations and satisfying delay requirements is an open area of research. Having two node-disjoint paths from the source to each destination makes a multicast tree resilient to node or edge failures. Satisfying delay requirements of the application ensures that the data delivered to the destination is fresh. Reducing the total cost of the multicast tree helps in lowering resource usage. We propose a new heuristic called dynamic weight optimal path pair (DW-OPP) for this problem. The heuristic constructs a node-disjoint low-cost multicast tree having low end-to-end delays. A user-specified parameter controls the performance of the heuristic. The parameter presents the user with a choice between lowering tree cost and achieving better delay performance. The performance of the new heuristic is evaluated empirically.

Garbage collection is increasingly prevalent as part of the programming landscape, but its use in real-time embedded systems remains problematic. One approach is to separate the specification of the timing requirements of real-time tasks, the memory use behavior of the code that implements them, and the configuration of the memory management system to ensure that the tasks' real-time requirements are met. The Real Time Garbage Collector (RTGC) framework provides common language for describing a broad class of real-time collectors. The notion of an RTGC configuration, based on the framework, provides a target for automating the task of configuring automatic memory management for a real-time system and its workload.

article Free Access Share on Managing update conflicts in Bayou, a weakly connected replicated storage system Authors: D. B. Terry Computer Science Laboratory, Xerox Palo Alto Research Center, Palo Alto, California Computer Science Laboratory, Xerox Palo Alto Research Center, Palo Alto, CaliforniaView Profile , M. M. Theimer Computer Science Laboratory, Xerox Palo Alto Research Center, Palo Alto, California Computer Science Laboratory, Xerox Palo Alto Research Center, Palo Alto, CaliforniaView Profile , Karin Petersen Computer Science Laboratory, Xerox Palo Alto Research Center, Palo Alto, California Computer Science Laboratory, Xerox Palo Alto Research Center, Palo Alto, CaliforniaView Profile , A. J. Demers Computer Science Laboratory, Xerox Palo Alto Research Center, Palo Alto, California Computer Science Laboratory, Xerox Palo Alto Research Center, Palo Alto, CaliforniaView Profile , M. J. Spreitzer Computer Science Laboratory, Xerox Palo Alto Research Center, Palo Alto, California Computer Science Laboratory, Xerox Palo Alto Research Center, Palo Alto, CaliforniaView Profile , C. H. Hauser Computer Science Laboratory, Xerox Palo Alto Research Center, Palo Alto, California Computer Science Laboratory, Xerox Palo Alto Research Center, Palo Alto, CaliforniaView Profile Authors Info & Claims ACM SIGOPS Operating Systems ReviewVolume 29Issue 5Dec. 3, 1995 pp 172–182https://doi.org/10.1145/224057.224070Online:03 December 1995Publication History 630citation5,089DownloadsMetricsTotal Citations630Total Downloads5,089Last 12 Months311Last 6 weeks48 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

We describe the results of examining two large research and commercial systems for the ways that they use threads. We used three methods: analysis of macroscopic thread statistics, analysis the microsecond spacing between thread events, and reading the implementation code. We identify ten different paradigms of thread usage: defer work, general pumps, slack processes, sleepers, one-shots, deadlock avoidance, rejuvenation, serializers, encapsulated fork and exploiting parallelism. While some, like defer work, are well known, others have not been previously described. Most of the paradigms cause few problems for programmers and help keep the resulting system implementation understandable. The slack process paradigm is both particularly effective in improving system performance and particularly difficult to make work well. We observe that thread priorities are difficult to use and may interfere in unanticipated ways with other thread primitives and paradigms. Finally, we glean from the practices in this code several possible future research topics in the area of thread abstractions.

Cedar is the name for both a language and an environment in use in the Computer Science Laboratory at Xerox PARC since 1980. The Cedar language is a superset of Mesa, the major additions being garbage collection and runtime types. Neither the language nor the environment was originally intended to be portable, and for many years ran only on D-machines at PARC and a few other locations in Xerox. We recently re-implemented the language to make it portable across many different architectures. Our strategy was, first, to use machine-dependent C code as an intermediate language, second, to create a language-independent layer known as the Portable Common Runtime, and third, to write a relatively large amount of Cedar-specific runtime code in a subset of Cedar itself. By treating C as an intermediate code we are able to achieve reasonably fast compilation, very good eventual machine code, and all with relatively small programmer effort. Because Cedar is a much richer language than C, there were numerous issues to resolve in performing an efficient translation and in providing reasonable debugging. These strategies will be of use to many other porters of high-level languages who may wish to use C as an assembler language without giving up either ease of debugging or high performance. We present a brief description of the Cedar language, our portability strategy for the compiler and runtime, our manner of making connections to other languages and the Unix* operating system, and some measures of the performance of our “Portable Cedar”.

Operating system abstractions do not always reach high enough for direct use by a language or applications designer. The gap is filled by language-specific runtime environments, which become more complex for richer languages (CommonLisp needs more than C+ +, which needs more than C). But language-specific environments inhibit integrated multi-lingual programming, and also make porting hard (for instance, because of operating system dependencies). To help solve these problems, we have built the Portable Common Runtime (PCR), a language-independent and operating-system-independent base for modern languages. PCR offers four interrelated facilities: storage management (including universal garbage collection), symbol binding (including static and dynamic linking and loading), threads (lightweight processes), and low-level I/O (including network sockets). PCR is “common” because these facilities simultaneously support programs in several languages. PCR supports C. Cedar, Scheme, and CommonLisp intercalling and runs pre-existing C and CommonLisp (Kyoto) binaries. PCR is “portable” because it uses only a small set of operating system features. The PCR source code is available for use by other researchers and developers.

Whru a dilt~lhSC is replicated at, many sites2 maintaining mutual consistrnry among t,he sites iu the fac:e of updat,es is a signitirant problem.This paper descrikrs several randomized algorit,hms for dist,rihut.ingupdates and driving t,he replicas toward consist,c>nc,y.The algorit Inns are very simple and require few guarant,ees from the underlying conllllunicat.iollsystem, yc+ they rnsutc t.hat.the off(~c~t, of ('very update is evcnt,uwlly rf+irt-ted in a11 rq1ica.s.The cost, and parformancc of t,hr algorithms arc tuned I>? c%oosing appropriat,c dist,rilMions in t,hc randoinizat,ioii step.TIN> idgoritlmls ilr(' c*los~*ly analogoIls t,o epidemics, and t,he epi-dcWliolog)-litc\ratiirc, ilitlh iii Illld~~rsti4lldill~ tlicir bc*liavior.One of tlW i$,oritlims 11&S brc>n implrmcWrd in the Clraringhousr sprv(brs of thr Xerox C'orporat~c~ Iiitcrnc4, solviiig long-standing prol>lf~lns of high traffic and tlatirl>ilsr inconsistcllcp.