Dependency mining-based causal message logging

In fault-tolerant computing, the approach of causal message logging provides on-demand stable logging and enables the independent recovery of nodes. It imposes the requirement that the dependency between non-deterministic events needs to be known for nodes. The dependency information is disseminated through messages. A central problem in traditional causal message logging is that if the message logging progress of nodes cannot be effectively tracked, some redundant dependency information will be piggybacked on the messages. In this paper, a dependency mining based approach is proposed. It tries to detect the message logging progress of nodes only from the dependency between non-deterministic events, without needing to piggyback an additional dependency vector or dependency matrix on each message.     

Message fragment based causal message logging

In a distributed computing system, message logging is widely used for providing nodes with recoverability. To reduce the piggyback overhead of traditional causal message logging, we present a zoning causal message logging approach in this paper. The crux of the approach is to control the propagation of dependency information: the nodes in the system are divided into zones, and by a message fragment mechanism, the dependency information of a node is only visible in the zone scope. Simulation results show that the piggyback overhead of the proposed approach is lower than that of traditional causal message logging.     

Vector time and causality among abstract events in distributed computations

An important problem in analyzing distributed computations is the amount of information. In event-based models, even for simple applications, the number of events is large and the causal structure is complex. Event abstraction can be used to reduce the apparent complexity of a distributed computation. This paper discusses one important aspect of event abstraction: causality among abstract events. Following Lamport [24], two causality relations are defined on abstract events, called weak and strong precedence. A general theoretical framework based on logical vector time is developed in which several meaningful timestamps for abstract events are derived. These timestamps can be used to efficiently determine causal relationships between arbitrary abstract events. The class of convex abstract events is identified as a subclass of abstract events that is general enough to be widely applicable and restricted enough to simplify timestamping schemes used for characterizing weak precedence. We explain why such a simplification seems not possible for strong precedence. Received: February 1994 / Accepted: July 1997     

Efficient causality-tracking timestamping

Vector clocks are the appropriate mechanism used to track causality among the events produced by a distributed computation. Traditional implementations of vector clocks require application messages to piggyback a vector of n integers (where n is the number of processes). This paper investigates the tracking of the causality relation on a subset of events (namely, the events that are defined as "relevant" from the application point of view) in a context where communication channels are not required to be FIFO, and where there is no a priori information on the connectivity of the communication graph or the communication pattern. More specifically, the paper proposes a suite of simple and efficient implementations of vector clocks that address the reduction of the size of message timestamps, i.e., they do their best to have message timestamps whose size is less than n. The relevance of such a suite of protocols is twofold. From a practical side, it constitutes the core of an adaptive timestamping software layer that can used by underlying applications. From a theoretical side, it provides a comprehensive view that helps better understand distributed causality-tracking mechanisms.     

Necessary and sufficient conditions on information for causal message ordering and their optimal implementation

Summary. This paper formulates necessary and sufficient conditions on the information required for enforcing causal ordering in a distributed system with asynchronous communication. The paper then presents an algorithm for enforcing causal message ordering. The algorithm allows a process to multicast to arbitrary and dynamically changing process groups. We show that the algorithm is optimal in the space complexity of the overhead of control information in both messages and message logs. The algorithm achieves optimality by transmitting the bare minimum causal dependency information specified by the necessity conditions, and using an encoding scheme to represent and transmit this information. We show that, in general, the space complexity of causal 0message ordering in an asynchronous system is , where is the number of nodes in the system. Although the upper bound on space complexity of the overhead of control information in the algorithm is , the overhead is likely to be much smaller on the average, and is always the least possible. Received: January 1996 / Accepted: February 1998     

Building Distributed Context-Aware Applications

Context-aware applications gather information from sensors about their users and operating environment. Sensor handling is a complicated issue that makes it hard and time-consuming to develop context-aware applications. This paper shows how dynamic discovery protocols can be employed to deal with the physical distribution of sensors and the need to share sensors between many applications. We report on our experiences from building a position-aware application using the dynamic discovery protocol that is part of the Jini software infrastructure for distributed systems.     

The cost of recovery in message logging protocols

Past research in message logging has focused on studying the relative overhead imposed by pessimistic, optimistic and causal protocols during failure-free executions. In this paper, we give the first experimental evaluation of the performance of these protocols during recovery. Our results suggest that applications face a complex tradeoff when choosing a message logging protocol for fault tolerance. On the one hand, optimistic protocols can provide fast failure-free execution and good performance during recovery, but are complex to implement and can create orphan processes. On the other hand, orphan-free protocols either risk being slow during recovery (e.g. sender-based pessimistic and causal protocols) or incur a substantial overhead during failure-free execution (e.g. receiver-based pessimistic protocols). To address this tradeoff, we propose hybrid logging protocols, which are a new class of orphan-free protocols. We show that hybrid protocols perform within 2% of causal logging during failure-free execution and within 2% of receiver-based logging during recovery     

Handling message semantics with Generic Broadcast protocols

Summary. Message ordering is a fundamental abstraction in distributed systems. However, ordering guarantees are usually purely “syntactic,” that is, message “semantics” is not taken into consideration despite the fact that in several cases semantic information about messages could be exploited to avoid ordering messages unnecessarily. In this paper we define the Generic Broadcast problem, which orders messages only if needed, based on the semantics of the messages. The semantic information about messages is introduced by conflict relations. We show that Reliable Broadcast and Atomic Broadcast are special instances of Generic Broadcast. The paper also presents two algorithms that solve Generic Broadcast. Received: August 2000 / Accepted: August 2001     

Dynamic end-to-end QoS management middleware for distributed multimedia systems

In this paper, we present a separable, reusable middleware solution that provides coordinated, end-to-end QoS management over any type of service component, and can use existing (legacy) QoS management solutions (by using wrappers) in a distributed multimedia system. Our middleware solution incorporates strategic and tactical QoS managers, and supports protocols and messages between tactical managers and managed application components, and between QoS managers in the management hierarchy. Strategic QoS managers take a global view of QoS provided by a set of application components within the manager's policy domain. Tactical QoS managers provide local control over application components. We introduce the concept of QoS policy domains to scope the authority of a strategic QoS manager. We describe how the management hierarchy is dynamically configured and reconfigured based on runtime needs of the application.     

Message logging: pessimistic, optimistic, causal, and optimal

Message-logging protocols are an integral part of a popular technique for implementing processes that can recover from crash failures. All message-logging protocols require that, when recovery is complete, there be no orphan processes, which are surviving processes whose states are inconsistent with the recovered state of a crashed process. We give a precise specification of the consistency property “no orphan processes”. From this specification, we describe how different existing classes of message-logging protocols (namely optimistic, pessimistic, and a class that we call causal) implement this property. We then propose a set of metrics to evaluate the performance of message-logging protocols, and characterize the protocols that are optimal with respect to these metrics. Finally, starting from a protocol that relies on causal delivery order, we show how to derive optimal causal protocols that tolerate f overlapping failures and recoveries for a parameter f (1⩽f⩽n)     

Understanding and Using Context

Context is a poorly used source of information in our computing environments. As a result, we have an impoverished understanding of what context is and how it can be used. In this paper, we provide an operational definition of context and discuss the different ways in which context can be used by context-aware applications. We also present the Context Toolkit, an architecture that supports the building of these context-aware applications. We discuss the features and abstractions in the toolkit that make the task of building applications easier. Finally, we introduce a new abstraction, a situation which we believe will provide additional support to application designers.     

Efficient verification of security protocols using partial-order reductions

In this paper we explore how partial-order reduction can make the task of verifying security protocols more efficient. These reduction techniques have been implemented in our tool Brutus. Partial-order reductions have proved very useful in the domain of model checking reactive systems. These reductions are not directly applicable in our context because of additional complications caused by tracking knowledge of various agents. We present partial-order reductions in the context of verifying security protocols and prove their correctness. Experimental results demonstrating the effectiveness of this reduction technique are also presented. Published online: 24 January 2003     

Active optimistic and distributed message logging for message‐passing applications

Message logging is an attractive solution to provide fault tolerance for message‐passing applications because it is more scalable than coordinated checkpointing. Sender‐based message logging is a well‐known optimization that allows the saving of message payload in the sender memory. Thus, only message reception events have to be logged reliably by using an event logger. This paper proposes solutions to further improve message logging protocol scalability. In existing works on message logging, the event logger has always been considered as a centralized process. We propose a distributed event logger that takes advantage of multi‐core processors that are to be executed in parallel with application processes, leveraging the volatile memory of the nodes to save events reliably. We also propose the combination of our distributed event logger and O2P, an active optimistic message logging protocol using a gossip‐based protocol to disseminate information on new stable events. Our distributed event logger and O2P are implemented in the Open MPI library. Our results show the following: (i) distributed event logging improves message logging protocol scalability and (ii) using O2P with a distributed event logger provides an efficient and scalable fault‐tolerant solution for message‐passing applications. Copyright © 2011 John Wiley & Sons, Ltd.     

Synchronous,asynchronous, and causally ordered communication

Summary.  This article studies characteristic properties of synchronous and asynchronous message communications in distributed systems. Based on the causality relation between events in computations with asynchronous communications, we characterize computations which are realizable with synchronous communications, which respect causal order, or where messages between two processes are always received in the order sent. It is shown that the corresponding computation classes form a strict hierarchy. Furthermore, an axiomatic definition of distributed computations with synchronous communications is given, and it is shown that several informal characterizations of such computations are equivalent when they are formalized appropriately. As an application, we use our results to show that the distributed termination detection algorithm by Dijkstra et al. is correct under a weaker synchrony assumption than originally stated. Received: November 1992/Accepted: July 1995     

Efficient distributed detection of conjunctions of local predicates

Global predicate detection is a fundamental problem in distributed systems and finds applications in many domains such as testing and debugging distributed programs. This paper presents an efficient distributed algorithm to detect conjunctive-form global predicates in distributed systems. The algorithm detects the first consistent global state that satisfies the predicate even if the predicate is unstable. Unlike previously proposed run-time predicate detection algorithms, our algorithm does not require the exchange of control messages during the normal computation. All the necessary information to detect predicates is piggybacked on computation messages of application programs. The algorithm is distributed because the predicate detection efforts as well as the necessary information are equally distributed among the processes. We prove the correctness of the algorithm and compare its performance with respect to message, storage and computational complexities with that of the previously proposed run-time predicate detection algorithms     

Efficient Garbage Collection Schemes for Causal Message Logging with Independent Checkpointing

This paper presents three garbage collection schemes for causal message logging with independent checkpointing. The first scheme allows each process to autonomously remove useless log information in its volatile storage by piggybacking only some additional information without requiring any extra message and forced checkpoint. Additionally, it supports faster output commit than traditional schemes. The second scheme enables each process to remove a part of log information in the storage if more empty space is required. It reduces the number of processes participating in the garbage collection by using the size of the log information of each process. The third scheme is a hybrid scheme having the advantages of the two proposed schemes. Simulation results show that the third scheme significantly reduces the garbage collection overhead compared with the traditional schemes regardless of specific communication patterns of distributed applications.     

Self-stabilization with r-operators

This paper describes a parameterized distributed algorithm applicable to any directed graph topology. The function parameter of our algorithm is instantiated to produce distributed algorithms for both fundamental and high level applications, such as shortest path calculus and depth-first-search tree construction. Due to fault resilience properties of our algorithm, the resulting protocols are self-stabilizing at no additional cost. Self-stabilizing protocols can resist transient failures and guarantee system recovery in a finite time. Since the condition on the function parameter (being a strictly idempotent r-operator) permits a broad range of applications to be implemented, the solution presented in our paper can be useful for a large class of distributed systems. Received: August 1999 / Accepted: January 2001     

Efficient detection of discrepancies in multiple file copies

Summary. For data consistency in distributed information systems, it is often necessary to compare remotely located copies of a file. We develop several protocols for the efficient detection of differing pages in a replicated file in different communication and failure models. The first set of protocols assumes a restricted but practical communication model. In this case, the minimum amount of communication necessary to identify any given number of differing pages is determined and a technique to attain this minimum is presented. For the more general communication model and for more refined failure models, we show that more efficient protocols can be derived. Our approach is based on the theory of Galois fields. Received: February 1996 / Accepted: September 1997     

Causality and atomicity in distributed computations

Summary. In a distributed system, high-level actions can be modeled by nonatomic events. This paper proposes causality relations between distributed nonatomic events and provides efficient testing conditions for the relations. The relations provide a fine-grained granularity to specify causality relations between distributed nonatomic events. The set of relations between nonatomic events is complete in first-order predicate logic, using only the causality relation between atomic events. For a pair of distributed nonatomic events X and Y, the evaluation of any of the causality relations requires integer comparisons, where and , respectively, are the number of nodes on which the two nonatomic events X and Y occur. In this paper, we show that this polynomial complexity of evaluation can by simplified to a linear complexity using properties of partial orders. Specifically, we show that most relations can be evaluated in integer comparisons, some in integer comparisons, and the others in integer comparisons. During the derivation of the efficient testing conditions, we also define special system execution prefixes associated with distributed nonatomic events and examine their knowledge-theoretic significance. Received: July 1997 / Accepted: May 1998     

基于FPGA消息识别和过滤的1553B总线监视器的设计

在1553B总线应用中,总线消息的识别和过滤是总线监视器（BM）的扩展功能,在很多工程应用中具有非常重要的意义,尤其在高负荷实时通信中,总线上数据量庞大,给系统设计带来很大困难。在研究1553B总线协议的基础上,提取了消息分类的特征信息,设计了基于FPGA的具有信息识别和过滤功能的BM。该BM根据1553B总线消息特征进行消息识别,从而将总线上传输的信息处理成有意义的数据块;在此基础上,按照一定的策略进行消息过滤,仅保留过滤后的信息,从而降低总线负荷。采用VHDL语言、有限状态机技术和模块化设计,进行BM的开发,并通过仿真验证和硬件综合,测试结果表明本文设计的BM达到了设计目的。