Distributed Computing – IWDC 2005
7th International Workshop, Kharagpur, India, December 27-30, 2005. Proceedings
Chapter and Conference Paper
The dispersion problem on graphs asks \(k\le n\) robots initially placed arbitrarily on the nodes of an n-node anonymous graph to reposition autonomously to reach a configuration in which each robot is on a dist...
Chapter and Conference Paper
The dispersion problem on graphs asks \(k\le n\) robots placed initially arbitrarily on the nodes of an n-node anonymous graph to reposition autonomously to reach a configuration in which each robot is on a dist...
Book and Conference Proceedings
7th International Workshop, Kharagpur, India, December 27-30, 2005. Proceedings
Chapter and Conference Paper
The problem of global state observation is fundamental to distributed systems. All interactions in distributed systems can be analyzed in terms of the building block formed by the pairwise interactions of inte...
Chapter and Conference Paper
Global predicate detection is an important problem in distributed executions. A conjunctive predicate is one in which each conjunct is defined over variables local to a single process. Polynomial space and tim...
Chapter and Conference Paper
The complete set ℜ of orthogonal temporal interactions between pairs of intervals, formulated by Kshemkalyani, allows the detailed specification of the manner in which intervals can be related to one another i...
Chapter and Conference Paper
Several constructions have been proposed for implementing a Bounded Concurrent Timestamp System (BCTS). Some constructions are based on a recursively defined Precedence Graph. Such constructions have been viewed ...
Chapter and Conference Paper
This paper presents a compact routing algorithm with stretch less than 3for directed networks. Although for stretch less than 3, the lower bound for the total routing information in the network is Ω(n ...
Chapter and Conference Paper
A significant shortcoming of causal message ordering systems is their inefficiency because of false causality. False causality is the result of the inability of the “happens before” relation to model true caus...
Chapter and Conference Paper
An optimal causal message ordering algorithm was recently proposed by Kshemkalyani and Singhal, and its optimality was proved theoretically. For a system of n processes, although the space complexity of this algo...
Chapter and Conference Paper
Vector and matrix clocks are exte sively used i asy chroous distributed systems.This paper asks,“how does the clock abstractio generalize?” and casts the problem in terms of concurrent knowledge. To this end, ...