Processor membership in asynchronous distributed systems

Presents protocols for determining processor membership in asynchronous distributed systems that are subject to processor and communication faults. These protocols depend on the placement of a total order on broadcast messages. The types of systems for which each of these protocols is applicable are characterized by the properties of the communication mechanisms and by the availability of stable storage. In the absence of stable storage or of a mechanism for distinguishing promptly delivered messages, the authors show that no membership protocol can exist. They also discuss their experience in implementing these membership protocols     

A Reservation-Based Extended Transaction Protocol

With the advent of the new generation of Internet-based technology, in particular, web services, the automation of business activities that are distributed across multiple enterprises becomes possible. Business activities are different from traditional transactions in that they are typically asynchronous, loosely coupled, and long running. Therefore, extended transaction protocols are needed to coordinate business activities that span multiple enterprises. Existing extended transaction protocols typically rely on compensating transactions to handle exceptional conditions. In this paper, we identify a number of issues with compensation-based extended transaction protocols and describe a reservation-based extended transaction protocol that addresses those issues. Moreover, we define a set of properties, analogous to the ACID properties of traditional transactions that are more appropriate for business activities that span multiple enterprises. In addition, we compare our reservation protocol with other extended transaction protocols for coordinating business activities and present performance analyses and results.     

From State Machines to Temporal Logic: Specification Methods for Protocol Standards

This paper attempts to lend perspective to several different methods that have been employed for specifying computer communication protocols by comparing a spectrum of specification techniques. The paper characterizes specification languages such as state transition diagrams, variants of temporal logic approaches, and sequence expressions by the extent to Which information is encoded as properties of a single state versus properties of a history of the entire computation state sequence. Taking the prototypical alternating bit protocol as an example, each method is used to specify the requirements for the send process of the distributed system.     

Large-core high n.a. fibres for data-link applications

High-n.a. fibres are required for optical-fibre data links. A germania-silica-core/silica-clad fibre has been produced by an alteration to the m.c.v.d. process, by the use of helium as a lining agent and the addition of P2 O5 to the core, with a measured n.a. of 0.38 and an attenuation of less than 5 dB/km at 0.89 ?m wavelength.     

A parallel sorting algorithm for a novel model of computation

The computational complexity of a parallel algorithm depends critically on the model of computation. We describe a simple and elegant rule-based model of computation in which processors apply rules asynchronously to pairs of objects from a global object space. Application of a rule to a pair of objects results in the creation of a new object if the objects satisfy the guard of the rule. The model can be efficiently implemented as a novel MIMD array processor architecture, the Intersecting Broadcast Machine. For this model of computation, we describe an efficient parallel sorting algorithm based on mergesort. The computational complexity of the sorting algorithm isO(nlog² n), comparable to that for specialized sorting networks and an improvement on theO(n ^1.5) complexity of conventional mesh-connected array processors.     

Maintaining censorship resistance in the iTrust network for publication,search and retrieval

This paper presents the architecture of the iTrust system together with algorithms for maintaining censorship resistance. In iTrust, metadata describing documents, and requests containing keywords, are distributed to randomly chosen nodes in the iTrust network. If a node receives a request containing keywords that match metadata it holds, it sends the URL of the matching document to the requesting node, which then retrieves the document from the source node. A novel detection algorithm estimates the proportion of operational nodes in the iTrust network, by comparing the empirical probabilities of the number of responses received for a node’s request with the analytical probabilities for a match, for various proportions of operational nodes. A novel defensive adaptation algorithm increases the number of nodes to which the requests are distributed, in order to maintain the same high probability of a match when some of the nodes are non-operational or malicious as when all of the nodes are operational. Extensive experimental evaluations demonstrate the effectiveness of the architecture and the algorithms for maintaining censorship resistance in the iTrust network.     

Necessary and sufficient conditions for broadcast consensus protocols

Summary We consider consensus protocols in asynchronous distributed systems that are based on broadcast communication. We show that a necessary and sufficient condition for the existence of a deterministic consensus protocol is delivery of each broadcast message to at least (n+k+1)/2 processes in ann-process system subject tok crash failures with either eventual fair broadcasting or eventual full broadcasting. The broadcast model captures the idea of a broadcast communication medium, such as the Ethernet, in which messages, if delivered, are delivered immediately and in order but not necessarily to all processes. Louise E. Moser received the Ph.D. degree in mathematics from the University of Wisconsin, Madison, in 1970. From 1970 to 1987 she was a professor of mathematics and computer science at California State University, Hayward. In 1987 she moved to the University of California, Santa Barbara, where is currently on the faculty of the Department of Electrical and Computer Engineering. Her current research interests include parallel and distributed systems, network architectures and communication protocols, and formal methods in software engineering. P.M. Melliar-Smith received the Ph.D. degree in computer science from the University of Cambridge, Cambridge, England, in 1987. He was a senior research scientist and program director at SRI International in Menlo Park (1976–1987), senior research associate at the University of Newcastle Upon Tyne (1973–1976), and principal designer for GEC Computers Ltd. in England (1964–1973). He is currently a professor in the Department of Electrical and Computer Engineering at the University of California, Santa Barbara. His research interests include fault-tolerant distributed systems, high-speed communication networks and protocols, and formal specification and verification. Vivek Agrawala received the B.Tech. degree in chemical engineering in 1984 and the M. Tech. degree in computer technology in 1986, both from the Indian Institute of Technology, Delhi, and a Ph.D. in computer science in 1991 from the University of California, Santa Barbara. Since then he has been a Research Scientist at Siemens Corporate Research, Princeton, New Jersey. His major research interests are distributed algorithms, software design methods, and distributed systems.This research was supported by the National Science Foundation, Grant Numbers CCR-8908515 and NCR-9016361. V. Agrawala's current address is Siemens Corporate Research, 755 College Road East, Princeton, NJ 08540, USA     

Index matching fluids for long wavelength (1.2?1.6 ?m) fibre-optic applications

Halocarbon fluids (FXCCF2)n, where X = Cl or Br have been used to index-match silica in the 800?2000 nm region. These fluids, unlike silicones or hydrocarbon fluids, are free of CH and OH absorption, and are resistant to hydrolysis and moisture absorption.     

The use of novel PtSi thin film structures in preferential sputtering measurements

The yields of silicon and platinum from the argon sputtering of PtSi films were measured by Rutherford backscattering techniques. Novel thin film structures of Al₂O₃ (substrate)/W/PtSi were employed to facilitate the measurements. Before steady state was reached, more silicon than platinum was sputtered off, in good agreement with platinum enrichment measurements in the sputtered samples. At steady state the silicon and platinum sputtering yields were equal.