Distributed Computing – IWDC 2005
7th International Workshop, Kharagpur, India, December 27-30, 2005. Proceedings
Page
%P
32 Result(s)
within
Ajay D. Kshemkalyani
-
Chapter and Conference Paper
Brief Announcement: Byzantine-Tolerant Detection of Causality in Synchronous Systems
It was recently proved that the causality or the happens before relation between events in an asynchronous distributed system cannot be detected in the presence of Byzantine processes [Misra and Kshemkalyani, ...
-
Chapter and Conference Paper
Byzantine Fault-Tolerant Causal Order Satisfying Strong Safety
Causal ordering is an important building block for distributed software systems. It was recently proved that it is impossible to provide causal ordering – liveness and strong safety – using a deterministic non...
-
Chapter and Conference Paper
Solvability of Byzantine Fault-Tolerant Causal Ordering Problems
Causal ordering in an asynchronous setting is a fundamental paradigm for collaborative software systems. Previous work in the area concentrates on ordering messages in a faultless setting and on ordering broad...
-
Chapter and Conference Paper
Weak Amnesiac Flooding of Multiple Messages
Flooding is a fundamental concept in distributed computing. In flooding, typically, a node forwards a message to its neighbors for the first time when it receives a message. Later if the node receives the same...
-
Chapter and Conference Paper
The Bloom Clock to Characterize Causality in Distributed Systems
Determining the causality between events in distributed executions is a fundamental problem. Vector clocks solve this problem but do not scale well. The probabilistic Bloom filter data structure can be used as...
-
Chapter and Conference Paper
The Bloom Clock for Causality Testing
Testing for causality between events in distributed executions is a fundamental problem. Vector clocks solve this problem but do not scale well. The probabilistic Bloom clock can determine causality between ev...
-
Chapter and Conference Paper
Dispersion of Mobile Robots on Grids
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
On the Growth of the Prime Numbers Based Encoded Vector Clock
The vector clock is a fundamental tool for tracking causality in parallel and distributed applications. Unfortunately, it does not scale well to large systems because each process needs to maintain a vector of...
-
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...
-
Chapter and Conference Paper
Evaluation of Models for Analyzing Unguided Search in Unstructured Networks
Evaluating the efficiency of unguided search based on random walk in unstructured peer-to-peer networks is important because it provides guidelines in correctly setting the parameters of the search. Most exist...
-
Book and Conference Proceedings
-
Chapter and Conference Paper
Analysis of Interval-Based Global State Detection
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
Nonintrusive Snapshots Using Thin Slices
This paper gives an efficient algorithm for recording consistent snapshots of an asynchronous distributed system execution. The nonintrusive algorithm requires 6(n–1) control messages, where n is the number of pr...
-
Chapter and Conference Paper
Performance of Fair Distributed Mutual Exclusion Algorithms
The classical Ricart-Agrawala algorithm (RA) has long been considered the most efficient fair mutual exclusion algorithm in distributed message-passing systems. The algorithm requires 2(N – 1) messages per critic...
-
Chapter and Conference Paper
Global State Detection Based on Peer-to-Peer Interactions
This paper presents an algorithm for global state detection based on peer-to-peer interactions. The interactions in distributed systems can be analyzed in terms of the peer-to-peer pairwise interactions of int...
-
Chapter and Conference Paper
Predicate Detection Using Event Streams in Ubiquitous Environments
Advances in clock synchronization techniques for sensor networks as well as wireless ad-hoc networks allow an approximated global time for an increasing number of configurations in ubiquitous and pervasive com...
-
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
A Note on Modalities for Nonconjunctive Global Predicates
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
Global Predicate Detection under Fine-Grained Modalities
Predicate detection is an important problem in distributed systems. Based on the temporal interactions of intervals, there exists a rich class of modalities under which global predicates can be specified. For ...
-
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...
