Journal of High Speed Networks - Volume 14, issue 2

Authors: Gouda, Mohamed G.

Article Type: Other

Citation: Journal of High Speed Networks, vol. 14, no. 2, pp. 107-107, 2005

Authors: Arora, Anish | Theimer, Marvin

Article Type: Research Article

Abstract: Distributed systems have to deal with the following scenarios in practice: bugs in components; incorrect specifications of components and, therefore, incorrect use of components; unanticipated faults due to complex interactions or to not containing the effects of faults in lower-level components; and evolution of components. Extant fault tolerance models deal with such scenarios in only a limited manner. In particular, we point out that state corruption is inevitable in practice and that therefore one must accept it and seek to correct it. The well-known concepts of detectors and correctors can be used to find and repair state corruption. However, …these concepts have traditionally been employed to immediately detect and correct errors caused by misbehaving system components. Immediate detection and correction is often too expensive to perform and hence we consider the implications of running detectors and correctors only intermittently. More specifically, we address issues that must be dealt with when state corruption may persist within a system for a period of time. We show how to both detect and correct state corruption caused by infrequently occurring “transient” errors despite the ability for it to actively spread to other parts of the system. We also show how to eventually detect all state corruption, even in cases where continually recurring errors are constantly introducing new state corruption. Finally, we discuss the minimum set of capabilities needed from a trusted base of software in order to guarantee the correctness of our algorithms. Show more

Citation: Journal of High Speed Networks, vol. 14, no. 2, pp. 109-134, 2005

Authors: Dolev, Shlomi | Kat, Ronen I.

Article Type: Research Article

Abstract: A self-stabilizing distributed file systems is presented. The system constructs and maintains a spanning tree for each file volume. The spanning tree consists of the servers that have volume replicas and caches for the specific file volume. The spanning trees are constructed and maintained by self-stabilizing distributed algorithms. A self-stabilizing synchronizer enforces file system semantics and consistent replications. File system updates use the tree to implement file read and write operations. A prototype of the system based on the Linux operating system has been implemented.

Citation: Journal of High Speed Networks, vol. 14, no. 2, pp. 135-153, 2005

Authors: Kulkarni, Sandeep S. | Ravikant,

Article Type: Research Article

Abstract: In this paper, we focus on causal deterministic merge – that combines causal delivery and uniform total order – in semi-synchronous publish-subscribe systems that provide simple guarantees related to clock values and message delays. We consider two properties of the timestamps used to obtain causal deterministic merge: (1) they should be bounded, i.e., for a given system, the maximum size of the timestamp should be independent of the length of the computation, and (2) they should be scalar, i.e., the time required to compare/update timestamps should be independent of the size of the system. By making certain assumptions about how …the timestamps are compared, we show that it is impossible to obtain a solution that uses scalar and bounded timestamps. Hence, we focus on solutions that achieve one of these properties. We present two solutions where the size of the timestamps is bounded; the size of the timestamps in the first solution is logarithmic in the number of processes whereas in the second solution, it is linear in the number of processes. We also present a solution where the timestamp consists of O(1) integers that can grow unbounded; we further show that the timestamps in this solution can be bounded if the application provides a simple guarantee about event creation. Each of these solutions is stabilizing fault-tolerant in that even if the system is perturbed by faults that improperly initialize processes, lose/corrupt messages and temporarily violate system guarantees, the system recovers to states from where subsequent computation satisfies the requirements of causal deterministic merge. Our solutions improve previously known solutions in several ways: In previous solutions, the timestamps consist of O(n2 ) unbounded integers where n is the number of processes. By contrast, one of our solutions uses O(1) unbounded integers and the remaining three solutions use bounded integers. Show more

Keywords: Logical timestamps, causal delivery, deterministic merge clock synchronization, publish-subscribe systems

Citation: Journal of High Speed Networks, vol. 14, no. 2, pp. 155-183, 2005

Authors: Cournier, Alain | Datta, Ajoy K. | Petit, Franck | Villain, Vincent

Article Type: Research Article

Abstract: A snap-stabilizing protocol, starting from any arbitrary initial system configuration, always behaves according to its specification. In other words, a snap-stabilizing protocol is a self-stabilizing protocol which stabilizes in zero steps. In this paper, we first prove the number of states required on processors to design a snap-stabilizing Propagation of Information with Feedback (PIF) algorithm in arbitrary un-oriented trees running under any distributed daemon (four states per processor for the middle processors and two states for each of the two extreme end processors). Then, we propose two snap-stabilizing PIF algorithms for un-oriented trees. The former works under any (fair …or unfair, central or distributed) daemon. It matches the lower bound in terms of number of states we established in this paper. The latter works under any (fair or unfair) central daemon. It uses only three states for the internal processors (two states for the root and the leaves). It is optimal in terms of number of states assuming a central daemon. Thus, both algorithms are optimal both in terms of the stabilization time (zero steps) and state requirement per processor. Show more

Keywords: Distributed systems, fault-tolerance, PIF, self-stabilization, snap-stabilization, wave algorithms

Citation: Journal of High Speed Networks, vol. 14, no. 2, pp. 185-200, 2005