Search NASA⌕ Search

SEARCH · Search NASA

Results for “protocols”

Search indexed NASA NTRS and DOE OSTI research on propulsion, heat transfer, battery materials and energy systems. Follow report and document links to the original sources.

Quote a phrase for an exact phrase match. Source license links do not imply unrestricted reuse.

At least 55 records · Page 3
All sourcesNASA NTRSDOE OSTI
NASA NTRS1995

SeaWiFS technical report series. Volume 25: Ocean optics protocols for SeaWiFS validation, revision 1

This report presents protocols for measuring optical properties, and other environmental variables, to validate the radiometric performance of the Sea-viewing Wide Field-of-view Sensor (SeaWiFS), and to develop and validate bio-optical algorithms for use with SeaWiFS data. The protocols are intended to establish foundations for a measurement strategy to verify the challenging SeaWiFS uncertainty goals of 5 percent in water-leaving radiances and 35 percent in chlorophyll alpha concentration. The protocols first specify the variables which must be measured, and briefly review the rationale for measuring each variable. Subsequent chapters cover detailed protocols for instrument performance specifications, characterizing and calibrating instruments, methods of making measurements in the field, and methods of data analysis. These protocols were developed at a workshop sponsored by the SeaWiFS Project Office (SPO) and held at the Naval Postgraduate School in Monterey, California (9-12 April 1991). This report began as the proceedings of the workshop, as interpreted and expanded by the authors and reviewed by workshop participants and other members of the bio-optical research community. The protocols are an evolving prescription to allow the research community to approach the unprecedented measurement uncertainties implied by the SeaWiFS goals; research and development are needed to improve the state-of-the-art in specific areas. These protocols should be periodically revised to reflect technical advances during the SeaWiFS Project cycle. The present edition (Revision 1) incorporates new protocols in several areas, including expanded protocol descriptions for Case-2 waters and other improvements, as contributed by several members of the SeaWiFS Science Team.

Hooker, Stanford B.↗
NASA NTRS2007

Model Checking a Byzantine-Fault-Tolerant Self-Stabilizing Protocol for Distributed Clock Synchronization Systems

This report presents the mechanical verification of a simplified model of a rapid Byzantine-fault-tolerant self-stabilizing protocol for distributed clock synchronization systems. This protocol does not rely on any assumptions about the initial state of the system. This protocol tolerates bursts of transient failures, and deterministically converges within a time bound that is a linear function of the self-stabilization period. A simplified model of the protocol is verified using the Symbolic Model Verifier (SMV) [SMV]. The system under study consists of 4 nodes, where at most one of the nodes is assumed to be Byzantine faulty. The model checking effort is focused on verifying correctness of the simplified model of the protocol in the presence of a permanent Byzantine fault as well as confirmation of claims of determinism and linear convergence with respect to the self-stabilization period. Although model checking results of the simplified model of the protocol confirm the theoretical predictions, these results do not necessarily confirm that the protocol solves the general case of this problem. Modeling challenges of the protocol and the system are addressed. A number of abstractions are utilized in order to reduce the state space. Also, additional innovative state space reduction techniques are introduced that can be used in future verification efforts applied to this and other protocols.

Malekpour, Mahyar R.↗
NASA NTRS2011

A Self-Stabilizing Distributed Clock Synchronization Protocol for Arbitrary Digraphs

This report presents a self-stabilizing distributed clock synchronization protocol in the absence of faults in the system. It is focused on the distributed clock synchronization of an arbitrary, non-partitioned digraph ranging from fully connected to 1-connected networks of nodes while allowing for differences in the network elements. This protocol does not rely on assumptions about the initial state of the system, other than the presence of at least one node, and no central clock or a centrally generated signal, pulse, or message is used. Nodes are anonymous, i.e., they do not have unique identities. There is no theoretical limit on the maximum number of participating nodes. The only constraint on the behavior of the node is that the interactions with other nodes are restricted to defined links and interfaces. We present an outline of a deductive proof of the correctness of the protocol. A model of the protocol was mechanically verified using the Symbolic Model Verifier (SMV) for a variety of topologies. Results of the mechanical proof of the correctness of the protocol are provided. The model checking results have verified the correctness of the protocol as they apply to the networks with unidirectional and bidirectional links. In addition, the results confirm the claims of determinism and linear convergence. As a result, we conjecture that the protocol solves the general case of this problem. We also present several variations of the protocol and discuss that this synchronization protocol is indeed an emergent system.

Malekpour, Mahyar R.↗
NASA NTRS2004

Protocol for a Delay-Tolerant Data-Communication Network

As its name partly indicates, the Delay-Tolerant Networking (DTN) Bundle Protocol is a protocol for delay-tolerant transmission of data via communication networks. This protocol was conceived as a result of studies of how to adapt Internet protocols so that Internet-like services could be provided across interplanetary distances in support of deep-space exploration. The protocol, and software to implement the protocol, is being developed in collaboration among experts at NASA's Jet Propulsion Laboratory and other institutions. No current Internet protocols can accommodate long transmission delay times or intermittent link connectivity. The DTN Bundle Protocol represents a departure from the standard Internet assumption that a continuous path is available from a host computer to a client computer: It provides for routing of data through networks that may be disjointed and may be characterized by long transmission delays. In addition to networks that include deepspace communication links, examples of such networks include terrestrial ones within which branches are temporarily disconnected. The protocol is based partly on the definition of a message-based overlay above the transport layers of the networks on which it is hosted.

Torgerson, Jordan↗
NASA NTRS2014

The CCSDS Next Generation Space Data Link Protocol (NGSLP)

The CCSDS space link protocols i.e., Telemetry (TM), Telecommand (TC), Advanced Orbiting Systems (AOS) were developed in the early growth period of the space program. They were designed to meet the needs of the early missions, be compatible with the available technology and focused on the specific link environments. Digital technology was in its infancy and spacecraft power and mass issues enforced severe constraints on flight implementations. Therefore the Telecommand protocol was designed around a simple Bose, Hocquenghem, Chaudhuri (BCH) code that provided little coding gain and limited error detection but was relatively simple to decode on board. The infusion of the concatenated Convolutional and Reed-Solomon codes5 for telemetry was a major milestone and transformed telemetry applications by providing them the ability to more efficiently utilize the telemetry link and its ability to deliver user data. The ability to significantly lower the error rates on the telemetry links enabled the use of packet telemetry and data compression. The infusion of the high performance codes for telemetry was enabled by the advent of digital processing, but it was limited to earth based systems supporting telemetry. The latest CCSDS space link protocol, Proximity-1 was developed in early 2000 to meet the needs of short-range, bi-directional, fixed or mobile radio links characterized by short time delays, moderate but not weak signals, and short independent sessions. Proximity-1 has been successfully deployed on both NASA and ESA missions at Mars and is planned to be utilized by all Mars missions in development. A new age has arisen, one that now provides the means to perform advanced digital processing in spacecraft systems enabling the use of improved transponders, digital correlators, and high performance forward error correcting codes for all communications links. Flight transponders utilizing digital technology have emerged and can efficiently provide the means to make the next leap in performance for space link communications. Field Programmable Gate Arrays (FPGAs) provide the capability to incorporate high performance forward error correcting codes implemented within software transponders providing improved performance in data transfer, ranging, link security, and time correlation. Given these synergistic technological breakthroughs, the time has come to take advantage of them in applying them to both on going (e.g., command, telemetry) and emerging (e.g., space link security, optical communication) space link applications. However one of the constraining factors within the Data Link Layer in realizing these performance gains is the lack of a generic transfer frame format and common supporting services amongst the existing CCSDS link layer protocols. Currently each of the four CCSDS link layer protocols (TM, TC, AOS, and Proximity-1) have unique formats and services which prohibits their reuse across the totality of all space link applications of CCSDS member space agencies. For example, Mars missions. These missions implement their proximity data link layer using the Proximity-1 frame format and the services it supports but is still required to support the direct from Earth (TC) protocols and the Direct To Earth (AOS/TM) protocols. The prime purpose of this paper, is to describe a new general purpose CCSDS Data Link layer protocol, the NGSLP that will provide the required services along with a common transfer frame format for all the CCSDS space links (ground to/from space and space to space links) targeted for emerging missions after a CCSDS agency-wide coordinated date. This paper will also describe related options that can be included for the Coding and Synchronization sub-layer of the Data Link layer to extend the capacities of the link and additionally provide an independence of the transfer frame sub-layer from the coding sublayer. This feature will provide missions the option of running either the currently performed synchronous coding and transfer frame data link or an asynchronous coding/frame data link, in which the transfer frame length is independent of the block size of the code. The benefits from the elimination of this constraint (frame synchronized to the code block) will simplify the interface between the transponder and the data handling equipment and reduce implementation costs and complexities. The benefits include: inclusion of encoders/decoders into transmitters and receivers without regard to data link protocols, providing the ability to insert latency sensitive messages into the link to support launch, landing/docking, telerobotics. and Variable Coded Modulation (VCM). In addition the ability to transfer different sized frames can provide a backup for delivering stored anomaly engineering data simultaneously with real time data, or relaying of frames from various sources onto a trunk line for delivery to Earth.

Kazz, Greg J.↗
DOE OSTI2024

Learning protocols for the fast and efficient control of active matter

Exact analytic calculation shows that optimal control protocols for passive molecular systems often involve rapid variations and discontinuities. However, similar analytic baselines are not generally available for active-matter systems, because it is more difficult to treat active systems exactly. Here we use machine learning to derive efficient control protocols for active-matter systems, and find that they are characterized by sharp features similar to those seen in passive systems. We show that it is possible to learn protocols that effect fast and efficient state-to-state transformations in simulation models of active particles by encoding the protocol in the form of a neural network. We use evolutionary methods to identify protocols that take active particles from one steady state to another, as quickly as possible or with as little energy expended as possible. Our results show that protocols identified by a flexible neural-network ansatz, which allows the optimization of multiple control parameters and the emergence of sharp features, are more efficient than protocols derived recently by constrained analytical methods. Our learning scheme is straightforward to use in experiment, suggesting a way of designing protocols for the efficient manipulation of active matter in the laboratory.

74 ATOMIC AND MOLECULAR PHYSICS↗
NASA NTRS1992

Tradeoffs in implementing primary-backup protocols

One way to implement a fault-tolerant service is by using multiple servers that fail independently. The state of the service is replicated and distributed among these servers, and updates are coordinated so that even when a subset of the servers fail, the service remains available. A common approach to structuring such replicated services is to designate one server as the primary and all the others as backups. Clients make requests by sending messages only to the primary. If the primary fails, then a failover occurs and one of the backups takes over. This service architecture is commonly called the primary-backup or the primary-copy approach. In most such primary-backup protocols, when the primary receives a client request, it informs the backups about the request, and then responds to the client. Informally, this primary-backup protocol is non-blocking if the primary does not wait for an acknowledgement from the backups before it sends the response; otherwise, it is blocking. Most of the existing protocols are blocking as non-blocking protocols cannot be constructed for some kinds of failures. However, it is shown that non-blocking protocols can be constructed for most of the process and communication failures that are expected to occur in the primary-backup systems of the future. Since non-blocking protocols can theoretically achieve the smallest possible response time, this paper analyzes these protocols under various system parameters. Two kinds of non-blocking protocols are analyzed: one in which the processes use point-to-point communication to exchange messages, and the other in which processes use hardware broadcasts.

Budhiraja, Navin↗
NASA NTRS1997

Study and Simulation of Enhancements for TCP (Transmission Control Protocol) Performance Over Noisy, High-Latency Links

The designers of the TCP/IP protocol suite explicitly included support of satellites in their design goals. The goal of the Internet Project was to design a protocol which could be layered over different networking technologies to allow them to be concatenated into an internet. The results of this project included two protocols, IP and TCP. IP is the protocol used by all elements in the network and it defines the standard packet format for IP datagrams. TCP is the end-to-end transport protocol commonly used between end systems on the Internet to derive a reliable bi-directional byte-pipe service from the underlying unreliable IP datagram service. Satellite links are explicitly mentioned in Vint Cerf's 2-page article which appeared in 1980 in CCR [2] to introduce the specifications for IP and TCP. In the past fifteen years, TCP has been demonstrated to work over many differing networking technologies, including over paths including satellites links. So if satellite links were in the minds of the designers from the beginning, what is the problem? The problem is that the performance of TCP has in some cases been disappointing. A goal of the authors of the original specification of TCP was to specify only enough behavior to ensure interoperability. The specification left a number of important decisions, in particular how much data is to be sent when, to the implementor. This was deliberately' done. By leaving performance-related decisions to the implementor, this would allow the protocol TCP to be tuned and adapted to different networks and situations in the future without the need to revise the specification of the protocol, or break interoperability. Interoperability would continue while future implementations would be allowed flexibility to adapt to needs which could not be anticipated at the time of the original protocol design.

Shepard, Timothy J.↗
NASA NTRS2000

Satellite Communications Using Commercial Protocols

NASA Glenn Research Center has been working with industry, academia, and other government agencies in assessing commercial communications protocols for satellite and space-based applications. In addition, NASA Glenn has been developing and advocating new satellite-friendly modifications to existing communications protocol standards. This paper summarizes recent research into the applicability of various commercial standard protocols for use over satellite and space- based communications networks as well as expectations for future protocol development. It serves as a reference point from which the detailed work can be readily accessed. Areas that will be addressed include asynchronous-transfer-mode quality of service; completed and ongoing work of the Internet Engineering Task Force; data-link-layer protocol development for unidirectional link routing; and protocols for aeronautical applications, including mobile Internet protocol routing for wireless/mobile hosts and the aeronautical telecommunications network protocol.

Ivancic, William D.↗
NASA NTRS2000

Operational Implementation of a 2-Hour Prebreathe Protocol for International Space Station

Procedures, equipment, and analytical techniques were developed to implement the ground tested 2-hour protocol in-flight operations. The methods are: 1) The flight protocol incorporates additional safety margin over the ground tested protocol. This includes up to 20 min of additional time on enriched O2 during suit purge and pressure check, increased duration of extravehicular activity (EVA) preparation exercise during O2 prebreathing (up to 90 min vs; the tested 24 min), and reduced rates of depressurization. The ground test observations were combined with model projections of the conservative measures (using statistical models from Duke University and NASA JSQ to bound the risk of Type I and Type II decompression sickness (DCS). 2) An inflight exercise device using the in-flight ergometer and elastic tubes for upper body exercise was developed to replicate the dual cycle exercise in the ground trials. 3) A new in-flight breathing system was developed and man-tested. 4) A process to monitor inflight experience with the protocol, including the use of an in-suit Doppler bubble monitor when available, was developed. The results are: 1) The model projections of the conservative factors of the operational protocol were shown to reduce the risk of DCS to levels consistent with the observations of no DCS to date in the shuttle program. 2) Cross over trials of the dual cycle ergometer used in ground tests and the in-flight exercise system verified that02consumption and the % division of work between upper and lower body was not significantly different at the p= 0.05 level. 3) The in-flight breathing system was demonstrated to support work rates generating 75% O2(max) in 95 percentile subjects. 4) An in-flight monitoring plan with acceptance criteria was put in place for the 2-hour prebreathe protocol. And the conclusions are: The 2-hour protocol has been approved for flight, and all implementation efforts are in place to allow use of the protocol as early as flight ISS 7A, now scheduled in November of 2000.

Waligora, James M.↗
NASA NTRS2008

Verification of a Byzantine-Fault-Tolerant Self-stabilizing Protocol for Clock Synchronization

This paper presents the mechanical verification of a simplified model of a rapid Byzantine-fault-tolerant self-stabilizing protocol for distributed clock synchronization systems. This protocol does not rely on any assumptions about the initial state of the system except for the presence of sufficient good nodes, thus making the weakest possible assumptions and producing the strongest results. This protocol tolerates bursts of transient failures, and deterministically converges within a time bound that is a linear function of the self-stabilization period. A simplified model of the protocol is verified using the Symbolic Model Verifier (SMV). The system under study consists of 4 nodes, where at most one of the nodes is assumed to be Byzantine faulty. The model checking effort is focused on verifying correctness of the simplified model of the protocol in the presence of a permanent Byzantine fault as well as confirmation of claims of determinism and linear convergence with respect to the self-stabilization period. Although model checking results of the simplified model of the protocol confirm the theoretical predictions, these results do not necessarily confirm that the protocol solves the general case of this problem. Modeling challenges of the protocol and the system are addressed. A number of abstractions are utilized in order to reduce the state space.

Malekpour, Mahyar R.↗
NASA NTRSDate not supplied

Nasa Exploration Atmosphere Tests 3 & 4: Development and Validation of Planetary Extravehicular Activity Prebreathe Protocols for Alternate Atmospheres and Suit Pressures

INTRODUCTION: Space suits operate at low pressures to optimize astronauts’ performance. The drop in pressure from the habitat environment to the suit carries a risk of decompression sickness (DCS), which is mitigated by a 95% O2 prebreathe protocol. Prebreathe protocols for the lunar surface have a significantly higher risk compared to International Space Station microgravity Extravehicular Activities (EVA). In previous studies, we validated a prebreathe protocol from a 56.5 kPa 34% O2 cabin to a 29.6 kPa EVA pressure; however, the enriched oxygen cabin environment poses a flammability risk that requires significant changes to material design and selections. Here, we report outcomes for prebreathe protocols from a sub-30% O2 cabin and associated changes necessary to control DCS risk critical to upcoming lunar missions. METHODS: Fourteen volunteers completed 11-day hypobaric chamber studies with an “alternate exploration atmosphere” of 66.2kPa, 28.5% O2. Subjects acclimated for 48 hrs and then participated in five 6-hour simulated EVAs at 29.6 or 35.6kPa, 95% O2. Prior to EVA, subjects underwent a 20, 90, or 150-minute prebreathe. The EVA simulation was designed to be representative of future planetary EVAs, proportionate to the subject’s VO2max. Decompression stress was monitored by real-time doppler and echocardiograph alternating every 15 min, as well as clinical monitoring for DCS signs/symptoms. Venous gas emboli (VGE) and DCS outcomes were verified against NASA-STD-3001 acceptance criteria. RESULTS AND DISCUSSION: Venous gas emboli (VGE) were identified during all EVAs. A neurological DCS case was identified in the 90-min/29.6kPa prebreathe, terminating further testing of this protocol. No DCS cases were identified in the 150 min/29.6kPa protocol. The 20 min/36.5kPa protocol was rejected due to a Type II DCS case. All DCS symptoms resolved with treatment, with no sequelae post initial treatment of DCS. These various test points highlighted to the significant benefit of elevated suit pressure to shorten prebreathe protocols, but also the difficulty in assessing and managing DCS during sustained EVA operations in remote planetary surfaces.

decompression sickness↗
DOE OSTI2023

Elucidating the Effect of Ion Exchange Protocol on the Copper Exchange Efficacy, Copper Siting, and SCR activity in Cu-SSZ-13

The influence of the copper ion exchange protocol on SCR activity of SSZ-13 is quantified. Using the same parent SSZ-13 zeolite, four exchange protocols are used to assess how exchange protocol impacts metal uptake and SCR activity. Large differences in the SCR activity, nearly 30 percentage points at 160 °C at constant copper content, are observed for different exchange protocols implying that different exchange protocols lead to different copper species. Hydrogen temperature programmed reduction on selected samples and infrared spectroscopy of CO binding corroborates this conclusion as the reactivity at 160 °C correlates with the intensity of the IR band at 2162 cm -1 . DFT-based calculations show that such an IR assignment is consistent with CO adsorbed on a Cu(I) cation within an eight-membered ring. This work shows that SCR activity can be influenced by the ion exchange process even when different protocols lead to the same metal loading. Perhaps most interesting, a protocol used to generate Cu-MOR for methane to methanol studies led to the most active catalyst both on a unit mass or unit mole copper basis. This points to a yet not recognized means to tailor catalyst activity as the open literature is silent on this issue.

37 INORGANIC, ORGANIC, PHYSICAL, AND ANALYTICAL CH↗
DOE OSTI2022

Asymptotic optimality of twist-untwist protocols for Heisenberg scaling in atom-based sensing

Twist-untwist protocols for quantum metrology consist of a serial application of (1) unitary nonlinear dynamics (e.g., spin squeezing or Kerr nonlinearity), (2) parameterized dynamics U ( φ ) (e.g., a collective rotation or phase space displacement), and (3) time reversed application of step 1. Such protocols are known to produce states that allow Heisenberg scaling for experimentally accessible estimators of φ even when the nonlinearities are applied for times much shorter than required to produce Schrödinger cat states. In this work, we prove that, asymptotically in the number of particles, twist-untwist protocols provide the lowest estimation error among quantum metrology protocols that utilize two calls to a weakly nonlinear evolution and a readout involving only first and second moments of a total spin operator n → · J → . We consider the following physical settings: all-to-all interactions generated by one-axis twisting J z 2 (e.g., interacting Bose gases), constant finite range spin-spin interactions of distinguishable or bosonic atoms (e.g., trapped ions or Rydberg atoms, or lattice bosons). In these settings, we further show that the optimal twist-untwist protocols asymptotically achieve 85% and 92% of the respective quantum Cramér-Rao bounds. We show that the error of a twist-untwist protocol can be decreased by a factor of L without an increase in the noise of the spin measurement if the twist-untwist protocol can be noiselessly iterated as an L layer quantum alternating operator ansatz.

74 ATOMIC AND MOLECULAR PHYSICS↗
DOE OSTI2019

Determining the Safety and Efficacy of Enhanced Recovery Protocols in Major Oncologic Surgery: An Institutional NSQIP Analysis

Background: Enhanced-recovery (ER) protocols are increasingly being utilized in surgical practice. Outside of colorectal surgery, however, their feasibility, safety, and efficacy in major oncologic surgery have not been proven. This study compared patient outcomes before and after multispecialty implementation of ER protocols at a large, comprehensive cancer center. Methods: Surgical cases performed from 2011 to 2016 and captured by an institutional NSQIP database were reviewed. Following exclusion of outpatient and emergent surgeries, 2747 cases were included in the analyses. Cases were stratified by presence or absence of ER compliance, defined by preoperative patient education and electronic medical record order set-driven opioid-sparing analgesia, goal-directed fluid therapy, and early postoperative diet advancement and ambulation. Results: Approximately half of patients were treated on ER protocols (46%) and the remaining on traditional postoperative (TP) protocols (54%). Treatment on an ER protocol was associated with decreased overall complication rates (20% vs. 33%, p < 0.0001), severe complication rates (7.4% vs. 10%, p = 0.010), and median hospital length of stay (4 vs. 5 days, p < 0.0001). There was no change in readmission rates (ER vs. TP, 8.6% vs. 9.0%, p = 0.701). Subanalyses of high magnitude cases and specialty-specific outcomes consistently demonstrated improved outcomes with ER protocol adherence, including decreased opioid use. Conclusions: This assessment of a large-scale ER implementation in multispecialty major oncologic surgery indicates its feasibility, safety, and efficacy. Future efforts should be directed toward defining the long-term oncologic benefits of these protocols.

62 RADIOLOGY AND NUCLEAR MEDICINE↗
NASA NTRS1983

SPP: A data base processor data communications protocol

The design and implementation of a data communications protocol for the Intel Data Base Processor (DBP) is defined. The protocol is termed SPP (Service Port Protocol) since it enables data transfer between the host computer and the DBP service port. The protocol implementation is extensible in that it is explicitly layered and the protocol functionality is hierarchically organized. Extensive trace and performance capabilities have been supplied with the protocol software to permit optional efficient monitoring of the data transfer between the host and the Intel data base processor. Machine independence was considered to be an important attribute during the design and implementation of SPP. The protocol source is fully commented and is included in Appendix A of this report.

Fishwick, P. A.↗
NASA NTRS1988

Integrated voice/data protocols for satellite channels

Several integrated voice/data protocols for satellite channels are studied. The system consists of two types of traffic: voice calls which are blocked-calls-cleared and the data packets which may be stored when no channel is available. The voice calls are operated under a demand assignment protocol. Three different data protocols for data packets are introduced. Under Random Access Data (RAD), the Aloha random access scheme is used. Due to the nature of random access, the channel utilization is low. Under Demand Assignment Data (DAD), a demand assignment protocol is used to improve channel utilization. Since a satellite channel has long propagation delay, DAD may perform worse than RAD. The two protocols are combined to obtain a new protocol called Hybrid Data (HD). The proposed protocols are fully distributed and no central controller is required. Numerical results show that HD enjoys a lower delay than DAD and provides a much higher channel capacity than RAD. The effects of fixed and movable boundaries are compared in partitioning the total frequency band to voice and data users.

Wu, Cheng-Shong↗
NASA NTRS1988

The Use of Efficient Broadcast Protocols in Asynchronous Distributed Systems

Reliable broadcast protocols are important tools in distributed and fault-tolerant programming. They are useful for sharing information and for maintaining replicated data in a distributed system. However, a wide range of such protocols has been proposed. These protocols differ in their fault tolerance and delivery ordering characteristics. There is a tradeoff between the cost of a broadcast protocol and how much ordering it provides. It is, therefore, desirable to employ protocols that support only a low degree of ordering whenever possible. This dissertation presents techniques for deciding how strongly ordered a protocol is necessary to solve a given application problem. It is shown that there are two distinct classes of application problems: problems that can be solved with efficient, asynchronous protocols, and problems that require global ordering. The concept of a linearization function that maps partially ordered sets of events to totally ordered histories is introduced. How to construct an asynchronous implementation that solves a given problem if a linearization function for it can be found is shown. It is proved that in general the question of whether a problem has an asynchronous solution is undecidable. Hence there exists no general algorithm that would automatically construct a suitable linearization function for a given problem. Therefore, an important subclass of problems that have certain commutativity properties are considered. Techniques for constructing asynchronous implementations for this class are presented. These techniques are useful for constructing efficient asynchronous implementations for a broad range of practical problems.

Schmuck, Frank Bernhard↗