Minimizing the maximum delay for reaching consensus in quorum-basedmutual exclusion schemes

The use of quorums is a well-known approach to achieving mutual exclusion in distributed computing systems. This approach works based on a coterie, a special set of node groups where any pair of the node groups shares at least one common node. Each node group in a coterie is called a quorum. Mutual exclusion is ensured by imposing that a node gets consensus from all nodes in at least one of the quorums before it enters a critical section. In a quorum-based mutual exclusion scheme, the delay for reaching consensus depends critically on the coterie adopted and, thus, it is important to find a coterie with small delay. Fu (1997) introduced two related measures called max-delay and mean-delay. The former measure represents the largest delay among all nodes, while the latter is the arithmetic mean of the delays. She proposed polynomial-time algorithms for finding max-delay and mean-delay optimal coteries when the network topology is a tree or a ring. In this paper, we first propose a polynomial-time algorithm for finding max-delay optimal coteries and, then, modify the algorithm so as to reduce the mean-delay of generated coteries. Unlike the previous algorithms, the proposed algorithms can be applied to systems with arbitrary topology     

Isomorphism of degree four Cayley graph and wrapped butterfly andtheir optimal permutation routing algorithm

In this paper, we first show that the degree four Cayley graph proposed in a paper appearing in the January 1996 issue of IEEE Transactions on Parallel and Distributed Systems is indeed isomorphic to the wrapped butterfly. The isomorphism was first reported by Muga and Wei in the proceedings of PDPTA '96. The isomorphism is shown by using an edge-preserving bijective mapping. Due to the isomorphism, algorithms for the degree four Cayley graph can be easily developed in terms of wrapped butterfly and topological properties of one network can be easily derived in terms of the other. Next, we present the first optimal oblivious one-to-one permutation routing scheme for these networks in terms of the wrapped butterfly. Our algorithm runs in time O(√N), where N is the network size     

Routing direction determination in regular networks based on configurable circuits

We consider the problem of finding short paths in a regular network such as a k-ary n-cube. This problem is a basic aspect of routing and has to be implemented with a very high performance for cluster and parallel computer networks. To achieve this, a scalable reconfigurable circuit is proposed that covers many popular topologies at acceptable cost. As a demonstration, the application to a modestly complex topology is shown in detail (“Multi-Mesh” introduced by Das et al. [D. Das, M. De, B.P. Sinha, A network topology with multiple meshes, IEEE Transactions on Computers 48 (5) (1999) 536–551]).

The achieved flexibility is much higher than that of previously reported reconfigurable circuits for the same purpose such as interval routing [R.B. Tan, J. van Leeuwen, Compact routing methods: a survey, in: Proceedings of the Colloquium on Structural Information and Communication Complexity (SICC94), School of Computer Science, Carleton University, Ottawa, 1995, pp. 99–109] or bit-pattern-associative routing [D.H. Summerville, J.G. Delgado-Frias, S. Vassiliadis, A flexible bit-pattern-associative router for interconnection networks, IEEE Transactions on Parallel and Distributed Systems 7 (5) (1996) 477–485]. The proposed circuit extends the domain of application-specific reconfigurable circuits beyond the areas of signal processing and cryptography, where most work is currently done.     

A delay optimal coterie on the k-dimensional folded Petersen graph

Coteries are an effective tool for enforcing mutual exclusion in distributed systems. Communication delay is an important metric to measure the performance of a coterie. The topology of the interconnection network in a distributed system also has an impact on its performance. The k-dimensional folded Petersen graph, a graph with 10^k nodes and diameter 2k, qualifies as a good network topology for large distributed systems. In this paper, we present a delay optimal coterie on the k-dimensional folded Petersen graph, FP_k. For any positive integer k, the coterie has message complexity 4^k and delay k. Moreover, this coterie is not vote-assignable.     

A regular scalable fault tolerant interconnection network for distributed processing

Bounded degree networks like deBruijn graphs or wrapped butterfly networks are very important from VLSI implementation point of view as well as for applications where the computing nodes in the interconnection networks can have only a fixed number of I/O ports. One basic drawback of these networks is that they cannot provide a desired level of fault tolerance because of the bounded degree of the nodes. On the other hand, networks like hypercube (where degree of a node grows with the size of a network) can provide the desired fault tolerance but the design of a node becomes problematic for large networks. In their attempt to combine the best of the both worlds, authors in [IEEE Transactions on Parallel and Distributed Systems 4(9) (1993) 962] proposed hyper-deBruijn (HD) networks that have many additional features of logarithmic diameter, partitionability, embedding, etc. But, HD networks are not regular, are not optimally fault tolerant and the optimal routing is relatively complex. Our purpose in the present paper is to extend the concepts used in the above-mentioned reference to propose a new family of scalable network graphs that retain all the good features of HD networks and at the same time are regular and maximally fault tolerant; the optimal point to point routing algorithm is significantly simpler than that of the HD networks. We have developed some new interesting results on wrapped butterfly networks in the process.     

2006 Reviewers List

Lists, in alphabetical order, the reviewers who contributed to the IEEE Transactions on Parallel and Distributed Systems in 2006.     

2007 Reviewers List

Lists the reviewers who contributed to the IEEE Transactions on Parallel and Distributed Systems from 12 October 2006 through 23 October 2007.     

Recognizing nondominated coteries and wr-coteries by availability

Coterie is a widely accepted concept for solving the mutual exclusion problem. Nondominated coteries are an important class of coteries which have better performance than dominated coteries. The performance of a coterie is usually measured by availability. Higher availability of a coterie exhibits greater ability to tolerate node or communication link failures. In this paper, we demonstrate a way to recognize nondominated coteries using availability. By evaluating the availability of a coterie instead of using a formal proof, the coterie can be recognized as a nondominated coterie or not. Moreover, with regard to wr-coterie, a concept for solving the replica control problem, we also present a similar result for recognizing nondominated wr-coteries. Finally, we apply our results to some well-known coteries and wr-coteries     

Transversal merge operation: a nondominated coterie construction method for distributed mutual exclusion

A coterie is a set of subsets (called quorums) of the processes in a distributed system such that any two quorums intersect with each other and is mainly used to solve the mutual exclusion problem in a quorum-based algorithm. The choice of a coterie sensitively affects the performance of the algorithm and it is known that nondominated (ND) coteries achieve good performance in terms of criteria such as availability and load. On the other hand, grid coteries have some other attractive features: 1) a quorum size is small, which implies a low message complexity, and 2) a quorum is constructible on the fly, which benefits a low space complexity. However, they are not ND coteries unfortunately. To construct ND coteries having the favorite features of grid coteries, we introduce the transversal merge operation that transforms a dominated coterie into an ND coterie and apply it to grid coteries. We call the constructed ND coteries ND grid coteries. These ND grid coteries have availability higher than the original ones, inheriting the above desirable features from them. To demonstrate this fact, we then investigate their quorum size, load, and availability, and propose a dynamic quorum construction algorithm for an ND grid coterie.     

Coterie join algorithm

Given a set of nodes in a distributed system, a coterie is a collection of subsets of the set of nodes such that any two subsets have a nonempty intersection and are not properly contained in one another. A subset of nodes in a coterie is called a quorum. An algorithm, called the join algorithm, which takes nonempty coteries as input, and returns a new, larger coterie called a composite coterie is introduced. It is proved that a composite coterie is nondominated if and only if the input coteries are nondominated. Using the algorithm, dominated or nondominated coteries may be easily constructed for a large number of nodes. An efficient method for determining whether a given set of nodes contains a quorum of a composite coterie is presented. As an example, tree coteries are generalized using the join algorithm, and it is proved that tree coteries are nondominated. It is shown that the join algorithm may be used to generate read and write quorums which may be used by a replica control protocol     

Nondominated coteries on graphs

Let C and D be two distinct coteries under the vertex set V of a graph G=(V,E) that models a distributed system. Coterie C is said to G-dominate D (with respect to G) if the following condition holds: For any connected subgraph H of G that contains a quorum in D (as a subset of its vertex set), there exists a connected subgraph H' of H that contains a quorum in C. A coterie C on a graph G is said to be G-nondominated (G-ND) (with respect to G) if no coterie D(≠C) on G G-dominates C. Intuitively, a G-ND coterie consists of irreducible quorums. This paper characterizes G-ND coteries in graph theoretical terms, and presents a procedure for deciding whether or not a given coterie C is G-ND with respect to a given graph G, based on this characterization. We then improve the time complexity of the decision procedure, provided that the given coterie C is nondominated in the sense of Garcia-Molina and Barbara (1985). Finally, we characterize the class of graphs G on which the majority coterie is G-ND     

Providing QoS in OSPF based best effort network using load sensitive routing

In an open shortest path first (OSPF) based best effort network, when a packet experiences congestion, the routing subsystem cannot send it through an alternate path. Thus, it fails to provide desired quality of service (QoS) during congestion. In order to provide QoS we have reported three different load sensitive routing (LSR) protocols in [A. Sahoo, An OSPF based load-sensitive QoS routing algorithm using alternate paths, in: IEEE International Conference on Computer Communication Networks, October 2002; A. Tiwari, A. Sahoo, Providing QoS support in OSPF based best effort network, in: IEEE International Conference on Networks, November 2005; A. Tiwari, A. Sahoo, A local coefficient based load sensitive routing protocol for providing QoS, in: IEEE International Conference on Parallel and Distributed Systems, July 2006]. The LSR protocol forwards packets through alternate paths in case of congestion. The number of alternate paths at any node depends on the value of operating parameter or coefficient used for alternate path calculation. Though the basic protocol in these cases was the same, the methods of choosing operating parameter were different. We referred to these three methods as LSR [A. Sahoo, An OSPF based load-sensitive QoS routing algorithm using alternate paths, in: IEEE International Conference on Computer Communication Networks, October 2002], E-LSR [A. Tiwari, A. Sahoo, Providing QoS support in OSPF based best effort network, in: IEEE International Conference on Networks, November 2005] and L-LSR [A. Tiwari, A. Sahoo, A local coefficient based load sensitive routing protocol for providing QoS, in: IEEE International Conference on Parallel and Distributed Systems, July 2006] coefficient methods. In this paper, we present the LSR protocol along with the three coefficient calculation methods pointing out the reason for going from one method to the next. The main strength of our LSR protocol is that it provides loop free alternate paths in the event of congestion and can interwork with routers running vanilla OSPF protocol. We show through simulation that the LSR protocol based on any of the three different coefficient calculation methods performs much better than OSPF and that out of the three methods proposed by us, L-LSR performs the best.     

Composite k-arbiters

The k-arbiter is a useful concept to solve the distributed h-out-of-k mutual exclusion problem. The distributed h-out-of-k mutual exclusion algorithms, based on the k-arbiter, have the benefits of high fault tolerance and low message cost. However, according to the definition of the k-arbiter, it is required to have a nonempty intersection among any (κ + 1) quorums in a k-arbiter. Consequently, constructing k-arbiters is difficult. The coterie join operation proposed by Neilsen and Mizuno (1992) produces a new and larger coterie by joining known coteries. By extending the coterie join operation, we first propose a k-arbiter join operation to construct a new and larger k-arbiter from known k-arbiters for a large system. Then, we derive a necessary and sufficient condition for the k-arbiter join operation to construct a nondominated joined k-arbiter. Moreover, we discuss availability properties of the joined k-arbiters. We observe that, by selecting proper k-arbiters, the joined k-arbiter can provide a higher availability than that of the original input. Finally, we propose a k-arbiter compound, operation to construct k-arbiters by using coteries and/or k-coteries. By that way, the problem of constructing k-arbiters can be reduced to the problem of constructing coteries and/or k-coteries     

A Pipeline Technique for Dynamic Data Transfer on a Multiprocessor Grid

This paper describes a pipeline technique which is used to redistribute data on a multiprocessor grid during runtime. The main purposes of the algorithm are to minimize the data transfer time, prevent congestion on the ports of the receiving processors, and minimize the number of idle processors. One of the key ideas for this algorithm is the creation of processor classes, firstly introduced by Desprez et al. [IEEE Transactions on Parallel and Distributed Systems 9(2):102 (1998).] Based on the idea of classes, we create the pipeline tasks used to organize the redistribution of data. Our experimental results show that this pipeline technique can significantly reduce the amount of time required to complete a dynamic data transfer task.     

Performance comparison of routing algorithms in wormhole-switched networks

This paper presents, building on the analytical models developed in [A. Shahrabi, M. Ould-Khoua, L. Mackenzie, Performance modelling of broadcast communication in multicomputer networks, International Journal of Parallel, Emergent, and Distributed Systems 20 (1) (2005); A. Shahrabi, M. Ould-Khoua, On the communication latency of wormhole routed interconnection networks, International Journal of Simulation 4 (5–6) (2003) 32–43; A. Shahrabi, L. Mackenzie, M. Ould-Khoua, Modelling of Adaptive Wormhole-Routed Hypercubes in the Presence of Broadcast Traffic, in: N.J. Dimopoulos, K.F. Li (Eds.), Chapter 10 in High Performance Computing Systems And Applications, Kluwer Academic Publishers, Boston, 2002; A. Shahrabi, M. Ould-Khoua, L. Mackenzie, An Analytical Model of Wormhole-Routed Hypercubes under Broadcast Traffic, Performance Evaluation 53 (1) (2003) 23–42; A. Shahrabi, M. Ould-Khoua, L. Mackenzie, Latency of double-tree broadcast in wormhole-routed hypercubes, in: Proceedings of International Conference on Parallel Processing (ICPP’01), IEEE Computer Society, 2001, pp. 401–408] a comparative performance study of adaptive and deterministic routing algorithms in wormhole-switched interconnection networks carrying a broadcast traffic component and investigates the performance vicissitudes of them under a variety of network operating conditions. In contrast to previous works, which have reported superiority of adaptive over deterministic routing especially in high-dimensional networks such as hypercubes, our results show that adaptivity does not necessarily improve network performance even for high-dimensional networks and its superiority starts to deteriorate as the broadcast fraction of generated traffic increases.     

Distributed Computing Systems

The 2nd International Conference On Distributed Computing Systems was held in Paris, France, 8–10 April, 1981. This meeting was organized by the Institut National de Recherche en Informatique et Automatique (INRIA) and the Laboratoire de Recherche en Informatique (LRI), with strong support from the International Committee on Distributed Computing of the IEEE. Sponsored by the IEEE Computer Society, A.C.U., A.F.C.E.T., C.N.E.T., C.N.R.S., E.R.O., and the I.F.I.P. Technical Committees 7 and 10, this was the second of a series of conferences which are expected to be held every eighteen months on the subject of Distributed Computing.The conference, which attracted more than 500 participants, was divided into the following topical sessions: (1) Opening Session, (2) Distributed Systems Structure, (3) Architecture, (4) Semantics of Parallel Programming, (5) Software Engineering for Distributed Systems, (6) Distributed Databases, (7) Performance Analysis, (8) Security and Reliability, (9) Distributed Scheduling, (10) Local Area Networks Applications, (11) Distributed Systems in Specific Applications, (12) Languages Constructs & Semantics of Parallel Programming, (13) Local Area Networks and Applications, and (14) Distributed Systems Structure.A detailed report on the conference, with emphasis on topics of special relevance to this Journal, is featured below.     

Supercube: An optimally fault tolerant network architecture

Summary A new class of interconnection network topology is proposed for parallel and distributed processing. The attractive features of this class include (a) the network can be constructed for any number of computing nodes, (b) the network is incrementally expandable, i.e., a new node can easily be added to the existing network, (c) it has good fault-tolerant characteristics (measured by the connectivity of the network graph) and (d) it has small delay characteristics (measured by the diameter of the network graph). The node connectivity of the network is equal to the minimum node degree. In this sense the network is optimally fault-tolerant.     

新型互连网络NIN研究

以通信延迟和网络吞吐率这两个重要参数为出发点,以大规模并行处理系统的新型互连网络（ＮＩＮ）进行了理论分析和模拟测试,并与二维网格、环形网以及反图拓扑互连网络进行了比较,结果表明：与其它三种网络相比,ＮＩＮ不仅保持了反图拓扑互连网络可以连接更多处理机的优点,同时还具有较短的通信延迟和较高的网络吞吐率。     

Delay-optimal quorum consensus for distributed systems

Given a set of nodes S, a coterie is a set of pairwise intersecting subsets of S. Each element in a coterie is called a quorum. Mutual exclusion in a distributed system can be achieved if each request is required to gel consensus from a quorum of nodes. This technique of quorum consensus is also used for replicated distributed database systems, and bicoteries and wr-coteries have been defined to capture the requirements of read and write operations in user transactions. The author is interested in finding coteries, bicoteries, and wr-coteries with optimal communication delay. The protocols take into account the network topology. They design delay-optimal quorum consensus protocols for network topologies of trees, rings, and clustered networks     

On conditional diagnosability of the folded hypercubes

The n-dimensional folded hypercube FQ_n, a variation of the hypercube proposed by Ahmed et al. [A. El-Amawy, S. Latifi, Properties and performance of folded hypercubes, IEEE Transactions on Parallel and Distributed Systems 2(3) (1991) 31-42], is an (n + 1)-regular (n + 1)-connected graph. Conditional diagnosability, a new measure of diagnosability introduced by Lai et al. [Pao-Lien Lai, Jimmy J.M. Tan, Chien-Ping Chuang, Lih-Hsing Hsu, Conditional diagnosability measures for large multiprocessor systems, IEEE Transactions on Computers 54(2) (2005) 165-175] can better measure the diagnosability of regular interconnection networks. This paper determines that under PMC-model the conditional diagnosability of FQ_n (t_c(FQ_n)) is 4n − 3 when n = 5 or n ? 8; t_c(FQ₃) = 3, t_c(FQ₄) = 7.