Search

Given a checkpoint and communication pattern of a distributed execution, the No Z-Cycle property (NZC) states that a dependency between a checkpoint and itself does not exist. In other words, a noncausal sequence of messages that starts after a checkpoint and terminates before that checkpoint does not exist. From an operational point of view, this property corresponds to the fact that each checkpoint belongs to at least one consistent global checkpoint. So it could be used, for example, for restarting a distributed application after the occurrence of a failure. In this paper we derive a characterization of the NZCproperty (previously an open problem). It identifies a subset of Z-cycles, namely core Z-cycles(CZCs), that has to be empty in order that the checkpoint and communication pattern of the execution satisfies the NZCproperty. Then, we present a communication-induced checkpointing protocol that prevents CZCs on-the-fly. This protocol actually removes the common causal partto any CZC. Finally we propose a taxonomy of communication-induced checkpointing protocols that ensure the NZCproperty.

Distributed Mutual Exclusion algorithms have been mainly compared using the number of messages exchanged per critical section execution. In such algorithms, no attention has been paid to the serialization order of the requests. Indeed, they adopt FCFS discipline. Conversely, the insertion of priority serialization disciplines, such as Short-Job-First, Head-Of-Line, Shortest-Remaining-Job-First etc., can be useful in many applications to optimize some performance indices. However, such priority disciplines are prone to starvation. The goal of this paper is to investigate and evaluate the impact of the insertion of a priority discipline in Maekawa-type algorithms. Priority serialization disciplines will be inserted by means of agated batch mechanism which avoids starvation. In a distributed algorithm, such a mechanism needs synchronizations among the processes. In order to highlight the usefulness of the priority based serialization discipline, we show how it can be used to improve theaverage response time compared to the FCFS discipline. The gated batch approach exhibits other advantages: algorithms are inherently deadlock-free and messages do not need to piggyback timestamps. We also show that, under heavy demand, algorithms using gated batch exchange less messages than Maekawa-type algorithms per critical section excution.