Termination detection protocols for mobile distributed systems

This paper studies a fundamental problem, the termination detection problem, in distributed systems. Under a wireless network environment, we show how to handle the host mobility and disconnection problems. In particular, when some distributed processes are temporarily disconnected, we show how to capture a weakly terminated state where silence has been reached only by those currently connected processes. A user may desire to know such a state to tell whether the mobile distributed system is still running or is silent because some processes are disconnected. Our protocol tries to exploit the network hierarchy by combining two existing protocols together. It employs the weight-throwing scheme on the wired network side, and the diffusion-based scheme on each wireless cell. Such a hybrid protocol can better pave the gaps of computation and communication capability between static and mobile hosts, thus more scalable to larger distributed systems. Analysis and simulation results are also presented     

Speculative locking protocols to improve performance for distributed database systems

We have proposed speculative locking (SL) protocols to improve the performance of distributed database systems (DDBSs) by trading extra processing resources. In SL, a transaction releases the lock on the data object whenever it produces corresponding after-image during its execution. By accessing both before and after-images, the waiting transaction carries out speculative executions and retains one execution based on the termination (commit or abort) mode of the preceding transactions. By carrying out multiple executions for a transaction, SL increases parallelism without violating serializability criteria. Under the naive version of SL, the number of speculative executions of the transaction explodes with data contention. By exploiting the fact that a submitted transaction is more likely to commit than abort, we propose the SL variants that process transactions efficiently by significantly reducing the number of speculative executions. The simulation results indicate that even with manageable extra resources, these variants significantly improve the performance over two-phase locking in the DDBS environments where transactions spend longer time for processing and transaction-aborts occur frequently.     

Message and time efficient consensus protocols for synchronous distributed systems

For a synchronous distributed system of n processes with up to t potential and f   actual crash failures, where (t<n-1,f≤t)$(t<n-1,f\le t)$, the time lower bound for a protocol to achieve consensus is min(t+1,f+2)$\min (t+1,f+2)$ rounds. Currently, most researches in this field focus on the time efficiency of consensus protocols. This paper proposes consensus protocols for synchronous distributed systems that achieve both message and time   efficiency. Based on an early stopping consensus protocol for synchronous distributed system with crash failures, we propose a rotating coordinator scheme that significantly reduces message complexity. However, this protocol is not time efficient because it requires min(t+1,f+3)$\min (t+1,f+3)$ rounds to reach consensus. Thus, to achieve both time and message efficiency, we propose another protocol in which (t+1)$(t+1)$ coordinators are used to send messages in each round. Furthermore, we show that the proposed consensus protocol with crash failures can be revised to be more message-efficient with orderly crash failures. When a process is able to send more than one message to another in a round, we propose an optimal message efficient early stopping consensus protocol for synchronous distributed systems with orderly crash failures.     

The imposition of protocols over open distributed systems

In order to facilitate enforcement of protocols, an architecture for distributed systems is introduced under which all interactions between objects are governed by an explicit and strictly enforced set of rules, called the law of the system. This law is global in the sense that all the objects of the system are made to obey it, but the maintenance of the law and its enforcement are performed locally, at each object (or node). The term law is used to emphasized that it not only provides the specification of protocols, but actually governs the system by enforcing them. In other words, under this architecture a protocol can be established simply by writing it into the law of a system, without having to worry about the programs that drive the various objects that might populate that system. The law, then, is the enforced specification of protocols. It is shown that various familiar protocols can be established under this architecture. A technique for online distributed updating of the global law of a system is presented     

Scalable consistency protocols for distributed services

A common way to address scalability requirements of distributed services is to employ server replication and client caching of objects that encapsulate the service state. The performance of such a system could depend very much on the protocol implemented by the system to maintain consistency among object copies. We explore scalable consistency protocols that never require synchronization and communication between all nodes that have copies of related objects. We achieve this by developing a novel approach called local consistency (LC). LC based protocols can provide increased flexibility and efficiency by allowing nodes control over how and when they become aware of updates to cached objects. We develop two protocols for implementing strong consistency using this approach and demonstrate that they scale better than a traditional invalidation based consistency protocol along the system load and geographic distribution dimensions of scale     

Analytic evaluation of contention protocols used in distributed real-time systems

The probability of a station failing to deliver packets before their deadlines, called theprobability of dynamic failure, P _dyn, is an important measure for the communication subsystem of a distributed real-time system. Another closely-related performance measure is the -bounded delivery time,T , which is defined as the least time needed to deliver a packet with probability greater than 1–. UsingP _dyn andT , we comparatively evaluate four contention protocols often used in distributed real-time systems: (i) the token passing protocol and its priority-based variation (called thetoken scheduling protocol), and (ii) theP _i-persistent protocol and a priority-based variation thereof. The communication subsystem equipped with different contention protocols is modeled first as embedded Markov chains. Then, we derive the probability distributions of access delay, from whichP _dyn andT can be calculated. The blocking probability,Q _i, can also be derived from the access delay distribution. These measures are derived first under the assumption of a single buffer at each station. The single-buffer model is then extended to the multiple-buffer case. The effects of buffer size onP _dyn,T , andQ _i, and the performance improvement with multiple buffers are analyzed over a wide range of network traffic.The work reported in this paper was supported in part by the ONR under Grant N00014-92-J—1080. Any opinions, findings, and conclusions or recommendations expressed in this paper are those of the authors and do not necessarily reflect the views of the ONR.     

Fault-containing self-stabilizing distributed protocols

Self-stabilization is an elegant approach for designing a class of fault-tolerant distributed protocols. A self-stabilizing protocol is guaranteed to eventually converge to a legitimate state after a transient fault. However, even a minor transient fault can cause vast disruption in the system before legitimacy is reached. This paper introduces the notion of fault-containment to address this particular weakness of self-stabilizing systems. Informally, a fault-containing self-stabilizing protocol, in addition to providing self- stabilization, contains the effects of faults. This ensures that disruption during recovery from faults, is proportional to the extent of the faults. The paper begins with a formal framework for specifying and evaluating fault-containing self-stabilizing protocols. The main result of the paper is a transformer that converts any non-reactive self-stabilizing protocol into an equivalent fault-containing self-stabilizing protocol that can repair any single fault in the system in O(1) time. For a large class of input protocols, the corresponding output protocols produced by the transformer have O(1) space overhead. The small time and space overhead make the fault-containing self-stabilizing protocol a practical alternative to the original self-stabilizing protocol. The transformer is based on a novel stabilizing timer paradigm that significantly simplifies the task of fault-containment.     

Single-site and distributed optimistic protocols for concurrencycontrol

The authors consider that, in spite of their advantage in removing the overhead of lock maintenance and deadlock handling, optimistic concurrency control methods have been applied less in practice than locking schemes. Two complementary approaches are introduced that may help render the optimistic approach practically viable. For the high-level approach, integration schemes can be utilized so that the database management system is provided with a variety of synchronization methods each of which can be applied to the appropriate class of transactions. The low-level approach seeks to increase the concurrency of the original optimistic method and improve its performance. The author examines the low-level approach in depth, and presents algorithms that aim at reducing back-ups and improve throughput. Both the single-site and distributed networks are considered. Optimistic schemes using time-stamps for fully duplicated and partially duplicated database networks are presented, with emphasis on performance enhancement and on reducing the overall cost of implementation     

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     

Complexity of distributed commit protocols

Summary Implementation of atomic actions in a distributed system in the presence of fail-stop failures is investigated. Worst case time and message complexities of the protocols realizing this are studied on complete graphs, rings, trees, and arbitrary graphs. Two modes of communication are considered — point-to-point and broadcast. Individual lower and upper bounds on time and messages are presented and the simultaneous achievability of the optimum message and time bounds is shown impossible in all the interesting cases.     

Quantum protocols for zero-knowledge systems

Zero-knowledge proof system is an important protocol that can be used as a basic block for construction of other more complex cryptographic protocols. An intrinsic characteristic of a zero-knowledge systems is the assumption that is impossible for the verifier to show to a third party that he has interacted with the prover. However, it has been shown that using quantum correlations the impossibility of transferring proofs can be successfully attacked. In this work we show two new protocols for proof transference, being the first one based on teleportation and the second one without using entangled states. In this last case, we assume that the third party can communicate in advance with both verifier and prover. Following, we present a quantum zero-knowledge protocol based on quantum bit commitment that can be implemented with today technology.     

Novel distributed robust adaptive consensus protocols for linear multi-agent systems with directed graphs and external disturbances

This paper addresses the distributed consensus protocol design problem for linear multi-agent systems with directed graphs and external unmatched disturbances. Novel distributed adaptive consensus protocols are proposed to achieve leader–follower consensus for any directed graph containing a directed spanning tree with the leader as the root node and leaderless consensus for strongly connected directed graphs. It is pointed out that the adaptive protocols involve undesirable parameter drift phenomenon when bounded external disturbances exist. By using the σ modification technique, distributed robust adaptive consensus protocols are designed to guarantee the ultimate boundedness of both the consensus error and the adaptive coupling weights in the presence of external disturbances. All the adaptive protocols in this paper are fully distributed, relying on only the agent dynamics and the relative states of neighbouring agents.     

Broadcast psi-calculi with an application to wireless protocols

Psi-calculi is a parametric framework for the extensions of pi-calculus, with arbitrary data structures and logical assertions for facts about data. In this paper we add primitives for broadcast communication in order to model wireless protocols. The additions preserve the purity of the psi-calculi semantics, and we formally prove the standard congruence and structural properties of bisimilarity. We demonstrate the expressive power of broadcast psi-calculi by modelling the wireless ad hoc routing protocol LUNAR and verifying a basic reachability property.     

Authentication for distributed systems

A number of protocols used to authenticate users, hosts and processes are described. The three main types of authentication in a distributed computing system-message content authentication, message origin authentication, and general identity authentication-are explained. Authentication exchanges are identified, and paradigms of authentication protocols are presented. Authentication protocol failures are addressed, and an authentication framework is provided. As case studies, two authentication services, Kerberos and SPX, are examined     

Design recovery for distributed systems

Two factors limit the utility of reverse engineering technology for many distributed software systems. First, with the exception of tools that support Ada and its explicit tasking constructs, reverse engineering tools fail to capture information concerning the flow of information between tasks. Second, relatively few reverse engineering tools are available for programming languages in which many older legacy applications were written (e.g., Jovial, CMS-2, and various assembly languages). We describe approaches that were developed for overcoming these limitations. In particular, we have implemented an approach for automatically extracting task flow information from a command and control system written in CMS-2. Our approach takes advantage of a small amount of externally provided design knowledge in order to recover design information relevant to the distributed nature of the target system     

Delay-independent design for distributed systems

Methods of limiting the impact of communication delays on the logical behavior of distributed systems are considered. It is assumed that a distributed system is described in terms of a number of interconnected modules, and each module is described in terms of its possible states and the possible state transitions. Transitions may be initiated spontaneously by a module and may give rise to output messages, which will be received, after some possible delay, by another module as an input. Otherwise, transitions may be initiated by received input. If the system has the property called regularity, its behavior is logically independent of the communication delays. A simple condition for regularity is given. This condition is the basis for the implementation of counter-based synchronization conditions in a distributed environment. Weaker forms of regularity, which make abstraction of internal operations invisible from the point of view of an outside observer, are also considered. The application of these concepts to the design of module interfaces involving `collisions' and to communication including timeouts is discussed in some detail with examples     

Finite-time distributed consensus via binary control protocols

This paper investigates the finite-time distributed consensus problem for multi-agent systems using a binary consensus protocol and the pinning control scheme. Compared with other consensus algorithms which need the complete state or output information of neighbors, the proposed algorithm only requires sign information of the relative state measurements, that is, the differences between a node’s state and that of its neighbors. This corresponds to only requiring a single-bit quantization error relative to each neighbor. This signum protocol is realistic in terms of observed behavior in animal groups, where relative motion is determined not by full time-signal measurements, but by coarse estimates of relative heading differences between neighbors. The signum protocol does not require explicit measurement of time signals from neighbors, and hence has the potential to significantly reduce the requirements for both computation and sensing. Analysis of discontinuous dynamical systems is used, including the Filippov solutions and set-valued Lie derivative. Based on the second-order information on the evolution of Lyapunov functions, the conditions that guarantee the finite-time consensus for the systems are identified. Numerical examples are given to illustrate the theoretical results.     

Boosting system performance with optimistic distributed protocols

Optimistic distributed protocols can dramatically improve system performance if the underlying system assumptions are sound and carry a high degree of probability. Optimistic protocols aggressively execute actions based on best-case system assumptions. Using optimistic protocols unquestionably involves tradeoffs, but if a protocol is well designed and the optimistic assumptions hold frequently enough, the gain in performance outweighs the overhead of repairing actions that execute incorrectly. Optimistic distributed protocols can dramatically improve system performance if the underlying system assumptions are sound and carry a high degree of probability     

Commit protocols for externalized-commit heterogeneous database systems

In designing a heterogeneous database systems, one of the main technical challenges is developing techniques for ensuring global commit. That is, guaranteeing that a transaction spanning multiple individual database management systems (DBMSs) either commits at all the participating DBMSs or at none of them. Previous work in this area typically assumes that the participating DBMSs do not provide a mechanism for interacting with their commit facilities. While this is true in many cases, in practice there are systems which support a programmatic interface to their commit protocols. We refer to database systems offering such facilities asexternalized commit DBMSs.The focus of this paper is on commit protocols for these systems. We propose two new commit protocols for externalized commit DBMSs. The first may be used to obtain global commit in heterogeneous database systems composed of DBMSs with different 2-phase commit protocols (e.g., centralized and linear). The second protocol is more general, and ensures global commit even if the participating DBMSs employ 3-phase commit protocols. The more general protocol also preserves database autonomy, since it does not block a DBMS upon failure of another system. We describe both protocols in detail and prove their correctness. Recommended by: M. RusinkiewiczThis work was partially supported by an IBM Research Initiation Grant.     

Towards an integrated formal method for verification of liveness properties in distributed systems: with application to population protocols

State-based formal methods [e.g. Event-B/RODIN (Abrial in Modeling in Event-B—system and software engineering. Cambridge University Press, Cambridge, 2010; Abrial et al. in Int J Softw Tools Technol Transf (STTT) 12(6):447–466, 2010)] for critical system development and verification are now well established, with track records including tool support and industrial applications. The focus of proof-based verification, in particular, is on safety properties. Liveness properties, which guarantee eventual, or converging computations of some requirements, are less well dealt with. Inductive reasoning about liveness is not explicitly supported. Liveness proofs are often complex and expensive, requiring high-skill levels on the part of the verification engineer. Fairness-based temporal logic approaches have been proposed to address this, e.g. TLA Lamport (ACM Trans Program Lang Syst 16(3):872–923, 1994) and that of Manna and Pnueli (Temporal verification of reactive systems—safety. Springer, New York, 1995). We contribute to this technology need by proposing a fairness-based method integrating temporal and first-order logic, proof and tools for modelling and verification of safety and liveness properties. The method is based on an integration of Event-B and TLA. Building on our previous work (Méry and Poppleton in Integrated formal methods, 10th international conference, IFM 2013, Turku, Finland, pp 208–222, 2013. doi: 10.1007/978-3-642-38613-8_15), we present the method via three example population protocols Angluin et al. (Distrib Comput 18(4):235–253, 2006). These were proposed as a theoretical framework for computability reasoning about Wireless Sensor Network and Mobile Ad-Hoc Network algorithms. Our examples present typical liveness and convergence requirements. We prove convergence results for the examples by integrated modelling and proof with Event-B/RODIN and TLA. We exploit existing proof rules, define and apply three new proof rules; soundness proofs are also provided. During the process we observe certain repeating patterns in the proofs. These are easily identified and reused because of the explicit nature of the reasoning.