Detecting stable locality-aware predicates

In a large-scale locality-driven network such as in modular robotics and wireless sensor networks, knowing the state of a local area is sometimes necessary due to either interactions being local and driven by neighborhood proximity or the users being interested in the state of a certain region. We define locality-aware predicates (LAP) that aim at detecting a predicate within a specified area. We model the area of interest as the set of processes that are within a breadth-first search tree (BFST) of height k$k$ rooted at the initiator process. Although a locality-aware predicate specifies a predicate only within a local area, observing the area consistently requires considering the entire system in a consistent manner. This raises the challenge of making the complexities of the corresponding predicate detection algorithms scale-free, i.e., independent of the size of the system. Since all existing algorithms for getting a consistent view of the system require either a global snapshot of the entire system or vector clocks of the size of the system, a new solution is needed. We focus on stable LAP, which are those LAP that remain true once they become true. We propose a scale-free algorithm to detect stable LAP within a k$k$-height BFST. Our algorithm can detect both stable conjunctive LAP and stable relational LAP. In the process of designing our algorithm, we also propose the first distributed algorithm for building a BFST within an area of interest in a graph, and the first distributed algorithm for recording a consistent sub-cut within the area of interest. This paper demonstrates that LAPs are a natural fit for detecting distributed properties in large-scale distributed systems, and stable LAPs can be practically detected at low cost.     

Repeated detection of conjunctive predicates in distributed executions

Given a conjunctive predicate ? over a distributed execution, this paper gives an algorithm to detect all interval sets, each interval set containing one interval per process, in which the local values satisfy the Definitely(?) modality. The time complexity of the algorithm is O(n³p), where n is the number of processes and p is the bound on the number of times a local predicate becomes true at any process. The paper also proves that unlike the Possibly(?) modality which admits O(pn) solution interval sets, the Definitely(?) modality admits O(np) solution interval sets. The paper also gives an on-line test to determine whether all solution interval sets can be detected in polynomial time under arbitrary fine-grained causality-based modality specifications.     

Detecting Arbitrary Stable Properties Using Efficient Snapshots

A stable properly continues to hold in an execution once it becomes true. Detecting arbitrary stable properties efficiently in distributed executions is still an open problem. The known algorithms for detecting arbitrary stable properties and snapshot algorithms used to detect such stable properties suffer from drawbacks such as the following: They incur the overhead of a large number of messages per global snapshot, or alter application message headers, or use inhibition, or use the execution history, or assume a strong property such as causal delivery of messages in the system. We solve the problem of detecting an arbitrary stable property efficiently under the following assumptions: P1) the application messages should not be modified, not even by timestamps or message coloring. P2) no inhibition is allowed. P3) the algorithm should not use the message history. P4) any process can initiate the algorithm. This paper proposes a family of nonintrusive algorithms requiring 6(n - 1) control messages, where n is the number of processes. A three-phase strategy of uncoordinated observation of local states is used to give a consistent snapshot from which any stable property can be detected. A key feature of our algorithms is that they do not rely on the processes continually and pessimistically reporting their activity. Only the relevant activity that occurs in the thin slice during the algorithm execution needs to be examined.     

A fine-grained modality classification for global predicates

Specifying and detecting predicates in a distributed execution is an important problem. Distributed execution observation has classically used two modalities-Possibly(/spl Phi/) and Definitely(/spl Phi/)-for predicate /spl Phi/. Based on the temporal interactions of intervals, the author identified a complete, orthogonal set of relationships /spl Rfr/; between pairs of intervals in a distributed execution. We show how to map the rich, orthogonal classification of modalities of pairwise interval interactions, to the classical coarse-grained classification, Possibly(/spl Phi/) and Definitely(/spl Phi/), for specifying predicates defined on any number of processes. This increases the power of expressing the temporal modalities under which predicates can be specified, beyond the current Possibly/Definitely classification. We give some timestamp-based tests for the orthogonal modalities in the refined classification.     

ATM cell encryption and key update synchronization

This paper presents a data compaction/randomization based approach as a mode of block encryption for ATM (Asynchronous Transfer Mode) cells. The presented approach converts a plaintext into pseudo‐random plaintext before ciphering to conceal patterns in the plaintext. The underlying idea behind this scheme is the Shannon's principles of “confusion” and “diffusion” which involve breaking dependencies and introducing as much randomness as possible into the ciphertext. In this scheme, confusion and diffusion are introduced into the system by first compressing the ATM cell payload and then spreading a continuously changing random data over the entire content of the cell. As a mode of operation for block ciphering, this scheme offers the following attractive features:(i) plaintext patterns are pseudo‐randomized and chained with ciphertext (thereby, preventing against “dictionary”, “known plaintext”, and “statistical analysis” attacks), (ii) it is self‐synchronizing, (iii) cell loss has no additional negative effect, (iv) no IV (Initialization Vector) storage is required, (v) it is encryption‐algorithm independent, (vi) there is no cell‐to‐cell dependency (no feedback from previous cells), and (vii) it is highly scalable (i.e., cells from the same stream can be ciphered and deciphered in parallel). This paper also presents a secure mechanism for in‐band synchronization of encryption/decryption key updates using a “marker‐cell” that is carried within the data channel. An important aspect of both the above mechanisms is that they do not require any changes to the ATM cell header or ATM infrastructure. This revised version was published online in June 2006 with corrections to the Cover Date.     

A one-phase algorithm to detect distributed deadlocks in replicateddatabases

Replicated databases that use quorum-consensus algorithms to perform majority voting are prone to deadlocks. Due to the P-out-of-Q nature of quorum requests, deadlocks that arise are generalized deadlocks and are hard to detect. We present an efficient distributed algorithm to detect generalized deadlocks in replicated databases. The algorithm performs reduction of a distributed wait-for-graph (WFG) to determine the existence of a deadlock. If sufficient information to decide the reducibility of a node is not available at that node, the algorithm attempts reduction later in a lazy manner. We prove the correctness of the algorithm. The algorithm has a message complexity of 2e messages and a worst-case time complexity of 2d+2 hops, where e is the number of edges and d is the diameter of the WFG. The algorithm is shown to perform significantly better in both time and message complexity than the best known existing algorithms. We conjecture that this is an optimal algorithm, in time and message complexity, to detect generalized deadlocks if no transaction has complete knowledge of the topology of the WFG or the system and the deadlock detection is to be carried out in a distributed manner     

Efficient detection of a locally stable predicate in a distributed system

We present an efficient approach to detect a locally stable predicate in a distributed computation. Examples of properties that can be formulated as locally stable predicates include termination and deadlock of a subset of processes. Our algorithm does not require application messages to be modified to carry control information (e.g., vector timestamps), nor does it inhibit events (or actions) of the underlying computation. The worst-case message complexity of our algorithm is O(n(m+1))$O(n(m+1))$, where n$n$ is the number of processes in the system and m$m$ is the number of events executed by the underlying computation. We show that, in practice, its message complexity should be much lower than its worst-case message complexity. The detection latency of our algorithm is O(d)$O(d)$ time units, where d$d$ is the diameter of communication topology. Our approach also unifies several known algorithms for detecting termination and deadlock. We also show that our algorithm for detecting a locally stable predicate can be used to efficiently detect a stable predicate that is a monotonic function of other locally stable predicates.     

Efficient distributed snapshots in an anonymous asynchronous message-passing system

We present a global snapshot algorithm with concurrent initiators, with termination detection in an anonymous asynchronous distributed message-passing system having FIFO channels. In anonymous systems, process identifiers are not available and an algorithm cannot use process identifiers in its operation. Such systems arise in several domains due to a variety of reasons. In the proposed snapshot algorithm for anonymous systems, each instance of algorithm initiation is identified by a random number (nonce); however, this is not used as an address in any form of communication. In the algorithm, each process can determine an instant when the local snapshot recordings at all the processes have terminated. This is a challenging problem when an algorithm cannot use process identifiers and a process does not know the number of processes in the system or the diameter of the network and cannot use a predefined topology overlay on the network, because there is no easy way to identify the global termination condition. The message complexity of our algorithm is (cn²)$\left(c{n}^2\right)$, where c$c$ is the number of concurrent initiators and n$n$ is the number of processes in the system, which is much better than that of the algorithm by Chalopin et al. (2012) [6]. Further, the algorithm by Chalopin et al. also requires knowledge of the network diameter.     

Efficient detection and resolution of generalized distributeddeadlocks

We present an efficient one-phase algorithm that consists of two concurrent sweeps of messages to detect generalized distributed deadlocks. In the outward sweep, the algorithm records a snapshot of a distributed wait-for-graph (WFG). In the inward sweep, the algorithm performs reduction of the recorded distributed WFG to check for a deadlock. The two sweeps can overlap in time at a process. We prove the correctness of the algorithm. The algorithm has a worst-case message complexity of 4e-2n+2l and a time complexity of 2d hops, where e is the number of edges, n is the number of nodes, l is the number of leaf nodes, and d is the diameter of the WFG. This is a notable improvement over the existing algorithms to detect generalized deadlocks     

Orthogonal relations for reasoning about posets

In large distributed systems, event abstraction becomes an important issue in order to represent interactions and reason at the right level of abstraction. Abstract events are collections of more elementary events, which provide a view of the system execution at an appropriate level of granularity. Understanding how two abstract events relate to each other is a fundamental problem for knowledge representation and reasoning in a complex system. In this paper, we study how two abstract events in a distributed system are related to each other in terms of the more elementary causality relation. Specifically, we analyze the ways in which two abstract events can be related to each other orthogonally, that is, identify all the possible mutually independent relations by which two such events could be related to each other. © 2002 Wiley Periodicals, Inc.