-
Chapter and Conference Paper
Fast Dispersion of Mobile Robots on Arbitrary Graphs
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...
-
Article
The power of logical clock abstractions
Vector and matrix clocks are extensively used in asynchronous distributed systems. This paper asks, “how does the clock abstraction generalize?” To address this problem, the paper motivates and proposes logica...
-
Chapter and Conference Paper
Detection of Orthogonal Interval Relations
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
Compact Routing in Directed Networks with Stretch Factor of Two
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
Reducing False Causality in Causal Message Ordering
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
Evaluation of the Optimal Causal Message Ordering Algorithm
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...
-
Article
Causality and atomicity in distributed computations
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 r...
-
Article
Necessary and sufficient conditions on information for causal message ordering and their optimal implementation
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 algorith...
-
Chapter and Conference Paper
Testing of synchronization conditions for distributed real-time applications
A set of synchronization relations between distributed nonatomic events was recently proposed to provide real-time applications with a fine level of discrimination in the specification of causality relations a...
-
Chapter and Conference Paper
A framework for viewing atomic events in distributed computations
We present a unifying framework for expressing and analyzing events at various levels of atomicity in distributed computations. In the framework, events at any level of atomicity are defined and composed in te...