Publications Copyright Notice
Existing algorithms for global snapshots in distributed systems are not scalable when the underlying topology is complete. In a network with $N$ processors, these algorithms require $O(N)$ space and $O(N)$ messages per processor. In this paper, we propose three algorithms for global snapshot: a grid-based, a tree-based and a centralized algorithm. The grid-based algorithm uses $O(N)$ space but only $O(\sqrt N)$ messages per processor. The tree-based algorithm requires only $O(1)$ space and $O(\log N \log w)$ messages per processor where $w$ is the average number of messages in transit per processor. The centralized algorithm requires only $O(1)$ space and $O(\log w)$ messages per processor. We also have a matching lower bound for this problem.
A combinatorial problem usually requires enumerating, counting or ascertaining existence of structures that satisfy a given property $B$ in a set of structures $L$. This paper describes a technique based on a generalization of Birkhoff's Theorem of representation of finite distributive lattices that can be used for solving such problems mechanically and efficiently. Specifically, we give an efficient (polynomial time) algorithm to enumerate, count or detect structures that satisfy $B$ when the total set of structures is large but the set of structures satisfying $B$ is small. We illustrate our techniques by analyzing problems in integer partitions, set families, and set of permutations.
We propose a self-stabilizing algorithm for maintaining a spanning tree in a distributed fashion for a completely connected topology. Our algorithm requires a node to process $O(1)$ messages of size $O(\log n)$ on average in one cycle as compared to previous algorithms which need to process messages from every neighbor, resulting in $O(n)$ work in a completely connected topology. Our algorithm also stabilizes faster than the previous approaches.
Given a distributed computation and a global predicate, predicate detection involves determining whether there exists at least one consistent cut (or global state) of the computation that satisfies the predicate. On the other hand, computation slicing is concerned with computing the smallest sub-computation---with the least number of consistent cuts---that contains all consistent cuts of the computation satisfying the predicate. In this paper, we investigate the relationship between predicate detection and computation slicing and show that the two problems are equivalent. Specifically, given an algorithm to detect a predicate $b$ in a computation $C$, we derive an algorithm to compute the slice of $C$ with respect to $b$.
This paper gives the definition of computation slicing and an efficient algorithm to compute a slice for regular predicates.
This paper gives algorithms to compute slices with respect to EF, EG and AG operators of temporal logic.
This paper introduces the idea of controlled reexecution. It gives algorithms to control a computation for disjunctive and mutual exclusion predicates.
Shows that predicate detection is a hard problem in general. Defines the classes linear and semi-linear predicates that allow efficient detection.
Gives a class of predicates that can be detected efficiently in an asynchronous system in spite of faults.
Gives an algorithm to detect predicates of the form $x1+x2+..+xn \leq k$. The algorithm is also useful in computing width of a poset.
Gives an algorithm to detect predicates of the form $definitely:b1 \wedge b2 \wedge ... bn$ where $bi$ is a local predicate.
Gives an efficient algorithm for optimistic message logging. The crucial observation is that a process that rolls back due to failure of a process can recover to the point that it does not make any additional processes inconsistent. Therefore, there is no need for rollback announcement.
This paper shows that $possibly:b1 \wedge b2 \wedge nn$ where each bi is a local predicate can be detected efficiently. This allows efficient detection of any global predicate in disjunctive normal form.