Browsing by Author "YUAN, SM"

Now showing 1 - 15 of 15

A LIUB(LOG(2)(N))-2 RESILIENT DECENTRALIZED COMMIT PROTOCOL
(1994-12-01)
YUAN, SM
;
交大名義發表
;
資訊工程學系
;
National Chiao Tung University
;
Department of Computer Science
In distributed database systems, commit protocols are used to ensure the transaction atomicity. In the presence of failures, nonblocking commit protocols can guarantee the transaction atomicity without blocking the transaction execution. A (resilient) decentralized nonblocking commit protocol (RDCP) is proper-ed for distributed database systems. This protocol is based on the hypercube network topology and is 'liub(log(2)(N)) - 2' resilient to node failures (N = number of system-nodes). The number of messages sent among the N nodes is 0(N.log(2)(2)(N)) which is only a factor of log(2)(N) over the message complexity lower bound 0(N.log(2)(N)) of decentralized commit protocols. Furthermore, RDCP is an optimistic nonblocking protocol. It aborts the transaction only when some nodes want to abort or some nodes fail before they make local decisions.
AN EFFICIENT FAULT-TOLERANT DECENTRALIZED COMMIT PROTOCOL
(1994-01-01)
YUAN, SM
;
交大名義發表
;
資訊工程學系
;
National Chiao Tung University
;
Department of Computer Science
A new efficient decentralized commit protocol is proposed for distributed database systems. This protocol can be applied to systems of all sizes and is [log(2) N] - 2 resilient to site failures, where N is the number of sites in the system. In addition, the number of messages sent among the N sites is (N log(2)(2)N) which is only a factor of log(2) over the message complexity lower bound O(N In N) of decentralized commit protocols.
AVAILABILITY OF K-COTERIE - COMMENTS
(1994-12-01)
YUAN, SM
;
CHANG, HK
;
交大名義發表
;
資訊工程學系
;
National Chiao Tung University
Kakugawa ef al, proposed the k-majority coterie for the distributed k-mutual exclusion problem (k-mutex). It was claimed that the K-majority coterie is a k-coterie, which is a general solution for k-mutex. In this comment, we show that the k-majority coterie is not necessary a k-coterie.
BANDWIDTH OF CROSSBARS FOR GENERAL REFERENCE MODEL
(1993-10-14)
CHANG, HK
;
YUAN, SM
;
交大名義發表
;
資訊工程學系
;
National Chiao Tung University
The bandwidth of crossbar multiprocessor systems is analysed for the general memory reference model. Previous solutions are restricted to several specified models: uniform memory reference, favorite memory reference and hot-spot; the presented analysis includes these as special cases.
DESIGN AND IMPLEMENTATION OF MOONY - A FAULT-TOLERANT DISTRIBUTED SHARED-MEMORY SYSTEM
(1995-04-01)
LIN, YW
;
YUAN, SM
;
LIANG, DR
;
資訊工程學系
;
Department of Computer Science
Shared memory is a natural high level programming paradigm in particular in distributed computing environments. In this paper, we describe the design and implementation of a fault-tolerant distributed shared memory system (FTDSM) called Moony,which provides shaved memory abstraction and guarantees continuous services even in the presence of site crashes. Moony is implemented at application level with a set of daemon sewers and provides services to users via Moony library function calls. The first prototype is portable to all Unix machines that support BSD socket and System V IPC. The preliminary results demonstrate that FTDSM is viable and, that Moony is portable over a wide variety of distributed environments.
EFFICIENT ALGORITHM FOR EVALUATING THE AVAILABILITY OF MULTIDIMENSIONAL VOTING
(1994-01-01)
CHANG, HK
;
YUAN, SM
;
資訊工程學系
;
Department of Computer Science
Voting is a fault-tolerant technique to synchronize conflict operations on shared resources in a faulty distributed system. Multidimensional voting is a generalization of traditional weighted voting. The availability of a voting system is determined by the vote and quorum assignments. In this paper, we present an O(n(k)+1) efficient algorithm for evaluating the availability of any given k-multidimensional vote and quorum assignments, where n is the number of sites in the system and k is the number of dimensions.
FAULT-TOLERANT DECENTRALIZED COMMIT PROTOCOLS
(1991-11-01)
YUAN, SM
;
AGRAWALA, AK
;
資訊工程學系
;
Department of Computer Science
FAULT-TOLERANT DECENTRALIZED COMMIT PROTOCOLS
(1991-11-01)
YUAN, SM
;
AGRAWALA, AK
;
資訊工程學系
;
Department of Computer Science
MESSAGE COMPLEXITY OF HIERARCHICAL QUORUM CONSENSUS ALGORITHM
(1994-04-22)
CHANG, HK
;
YUAN, SM
;
資訊工程學系
;
Department of Computer Science
The hierarchical quorum consensus (HQC) algorithm, which is a generalization of the standard quorum consensus algorithm for managing replicated data, can reduce the quorum size to N0.63. This paper analyzes the message complexity of HQC. Moreover, an asymptotic analysis on the ratio of the message complexity to the quorum size is presented. It is shown that the ratio converges to a constant.
MESSAGE COMPLEXITY OF THE TREE QUORUM ALGORITHM
(1995-08-01)
YUAN, SM
;
CHANG, HK
;
交大名義發表
;
資訊工程學系
;
National Chiao Tung University
The tree quorum algorithm (TQA) uses a tree structure to generate intersecting (tree) quorums for distributed mutual exclusion, This paper analyzes the number of messages required to acquire a quorum in TQA. Let i be the depth of the complete binary tree used in TQA, and let M(i) be the number of messages required to acquire a quorum or to determine that no quorum is accessible. We discuss M(i) as a function of i and p, where p (1/2 < p < 1) is the probability that each site is operational. Let C-i denote the average number of sites in the quorum that TQA finds. The analysis shows that, although both M(i) and C-i increase without bound as i increases, M(i)/C-i approaches to 1+p/p as i increases. According to the result, an approximate close form for M(i) is derived.
MESSAGE COMPLEXITY OF THE TREE QUORUM ALGORITHM FOR DISTRIBUTED MUTUAL EXCLUSION
(1994)
CHANG, HK
;
YUAN, SM
;
資訊工程學系
;
Department of Computer Science
PERFORMANCE CHARACTERIZATION OF THE TREE QUORUM ALGORITHM
(1995-06-01)
CHANG, HK
;
YUAN, SM
;
交大名義發表
;
資訊工程學系
;
National Chiao Tung University
The tree quorum algorithm, which logically organizes the sites in a system to a tree structure, is an efficient and fault-tolerant solution for distributed mutual exclusion. In this paper, the performance characteristics of the tree quorum algorithm is analyzed. A refinement algorithm is proposed to refine a logical tree structure by eliminating nodes or subtrees which do not improve the peformance. Thus the refined tree performs better than the original.
SGHC - A NEW CLASS OF OPTIMALLY FAULT-TOLERANT NETWORKS
(1995-01-01)
LIEN, HM
;
YUAN, SM
;
交大名義發表
;
資訊工程學系
;
National Chiao Tung University
A new class of interconnection network topology is proposed for parallel and distributed processing. The interconnection is based on the Generalized Hypercube and the Supercube systems. Given the number of nodes N and the desired diameter k, a topology can be constructed. The node degree of each node is between k(left perpendicula-k square-root N right perpendicular) - 1) and ((2k - 1)(inverted left perpendicular k square-root N inverted right perpendicular - 1) - 1). The connectivity of the network is at least k(left perpendicular k square-root N right perpendicular - 1). It has been shown that the connectivity of the network is equal to the minimum node degree. In this sense it is an optimally fault-tolerant network. In addition, there exist at least k(left perpendicular k square-root N right perpendicular - 1) paths of length less-than-or-equal-to k + 1 between any two nodes in an N-node super generalized hypercube with specified diameter k.
TOPOLOGICAL PROPERTIES OF SUPERCUBE
(1991-03-14)
YUAN, SM
;
交大名義發表
;
資訊工程學系
;
National Chiao Tung University
;
Department of Computer Science
The N-node Supercube is a new generalized of Hypercube topology. Unlike the Binary Hypercube, the Supercube can be constructed for any number of nodes N. In addition, it maintains the connectivity and diameter properties of the corresponding hypercube. In this paper, we examine some topological properties of the Supercube from the graph-theory point of view.
X-WINDOW BASED GROUP COLLABORATIVE EDITING SYSTEM
(1993-11-01)
LEU, WY
;
YUAN, SM
;
交大名義發表
;
資訊工程學系
;
National Chiao Tung University
Group collaborative editing is an activity by which people geographically dispersed can edit the same document simultaneously. It makes use of computers and network communication to provide an interactive and convenient environment, so people can save much of their time and cost. We have developed a group collaborative editing system which not only allows participants to jointly view and process multimedia documents but also provides real-time interactive conversation facilities to let users feel realistic and friendly. This paper describes the concepts of group collaboration and the mechanisms of our system. It also presents the interface design strategy and the synchronization control method.