共查询到20条相似文献,搜索用时 484 毫秒
1.
分布式互斥是网格分布式系统的重要问题.根据网格系统的特点,提出了新型的分布式互斥算法.该算法基于网格网络的行列生成分布式互斥十字仲裁集;采用Lamport逻辑时戳保证消息的时序性;算法采用"探测"消息进行系统的容错处理.分析与仿真证明,该算法具有较低的消息复杂度、较短的响应延迟以及较好的容错性能. 相似文献
2.
分布式互斥是网格分布式系统的重要问题。根据网格系统的特点,提出了新型的分布式互斥算法。该算法基于网格网络的直径生成分布式互斥仲裁集;采用Lamport逻辑时戳保证消息的时序性;算法采用“探测”消息进行系统的容错处理。分析与仿真证明,该算法具有较低的消息复杂度、较短的响应延迟以及较好的容错性能。 相似文献
3.
分布式互斥是分布式系统的重要问题.根据树拓扑网络的特点,提出了新型的分布式互斥算法TNDME.算法的运行范围限制在根节点到请求节点之间,采用循径方法生成分布式互斥仲裁集;采用Lamport逻辑时戳保证消息的时序性;算法采用"最大残存树"探测方法进行系统的容错处理.描述了算法的模型、主要思想、数据结构、消息结构以及伪代码,并证明了算法的正确性.理论性能分析与仿真对比证明,算法具有较低的消息复杂度、较短的响应延迟以及较好的容错性能. 相似文献
4.
目前人们已经提出了很多分布式互斥算法.为简化问题,这些算法多数要求假设系统的节点与通信均可靠,因此不存在容错处理问题.部分在先假定节点与通信可靠的基础上讨论的算法,为达到其结论的逻辑严密性,补充了节点与通信不可靠时的容错处理,但这些容错处理方式都是作为其分布式互斥算法的补充提出来的,有较大程度的理想化成分,基本上没用进行充分的性能分析.本文根据分布式互斥算法节点容错处理方式的不同,将其分为两类并对其时消息复杂度的影响进行详细讨论.在此基础上,提出一种混合的分布式互斥节点容错处理方法,以降低非稳定环境下分布式互斥算法的平均消息复杂度. 相似文献
5.
非稳定环境下基于竞争消息复杂度的分布式互斥节点容错算法 总被引:1,自引:0,他引:1
目前人们已经提出了很多分布式互斥算法。为简化问题,这些算法多数要求假设系统的节点与通信均可靠,因此不存在容错处理问题。部分在先假定节点与通信可靠的基础上讨论的算法,为达到其结论的逻辑严密性,补充了节点与通信不可靠时的容错处理,但这些容错处理方式都是作为其分布式互斥算法的补充提出来的,有较大程度的理想化成分,基本上没用进行充分的性能分析。本文根据分布式互斥算法节点容错处理方式的不同,将其分为两类并对其对消息复杂度的影响进行详细讨论。在此基础上,提出一种混合的分布式互斥节点容错处理方法,以降低非稳定环境下分布式互斥算法的平均消息复杂度。 相似文献
6.
7.
8.
9.
一种基于消息槽的K资源互斥算法 总被引:1,自引:0,他引:1
在分布式操作系统等一些有多个进程同时活跃的应用中,必须妥善解决不同进程对资源的需求,即同步与互斥问题.文章提出了一种基于消息槽的K资源互斥算法,介绍了该算法的原理,详细描述了该算法的运作过程,并进行了深入的分析.分析结果表明,该算法能够有效地满足K资源分布式环境下同步与互斥的要求. 相似文献
10.
在银行系统等有多个实体同时活跃的分布式应用中,必须妥善解决不同实体对资源的需求,即同步与互斥。本文基于令牌的K资源互斥算法,提出了基于消息槽的K资源互斥算法,该算法能有效满足K资源分布式环境下同步与互斥的要求。 相似文献
11.
分布式工业测控网DMCN中多主站组成的逻辑环维护算法 总被引:2,自引:0,他引:2
分布式工业控制网中采用多主站组成的令牌总线逻辑环,当逻辑环被破坏时,就执行逻辑维护算法。算法效率直接影响整个网络的效率,也是影响网络实量性的主要因素。本文针对这种类型的网络,提出了一种新的算法,采用“下站地址捎带”,从而降低整个网络逻辑环维护复杂性,使维护逻辑环时间得以减少,使网络的实时性得以保证。 相似文献
12.
王立宏 《计算机工程与科学》2000,22(6):46-47
分布式系统临界区互斥访问方法大体上有集中式算法、分布式算法和令版环算法三种。本文在简单讨论了这三种方法后,结合在分布式光纤数据接口FDDI中应用的时控令牌协议,对令版环算法进行了改造,使得令版特环一周的时间可以控制在有限范围内,从而为丢失令牌的判断提供了理论依据。模拟实验对改进引起的综合影响进行评价,认为该该改进是可取的。 相似文献
13.
Topological design of intereonnection network is a key factor of developingparallel/distributed processing systems composed of a large number of microcomputermodules. For this purpose a double-chordal ring intereonnection network was proposed. Themost attractive of its advantages is that for an optimally designed network with N modules itsdiameter can he reduced to O(N~(1/3)) compared with O(N~(1/2)) for a simple chordal ring. Theessential properties of double-chordal ring network arc presented, and formulae for calculatingits diameter are derived. These formulae lead to a distributed computational routing algorithmand a way of optimization of the network parameters (maximal number of nedes and optimalchordal lengths) for a given diameter. 相似文献
14.
15.
汤毅坚 《计算机研究与发展》1993,30(1):27-31,26
环形局域网HUSTRING采用令牌传递和寄存器插入相结合的媒介访问控制协议,从而获得了优于令牌环的实时传输性能。本文介绍了HUSTRING 的双环结构,研究了它的拓扑容错性能,并给出其信息包路由选择算法。 相似文献
16.
《Journal of Parallel and Distributed Computing》1999,58(1):1-25
Algorithms for arbitrating and scheduling transmissions from different transmitters sharing a common access medium arise often in the design of many shared and distributed systems. In this paper we present a distributed algorithm for arbitrating time-constrained transmissions on slotted shared access media. The two most important distinguishing features of our algorithm are: (1) unlike most of the other schemes that guarantee on-time transmission over shared media by centralized preallocation of slots, our algorithm is fully distributed and completely on-line; (2) it eliminates one of the common pitfalls of all slotted systems, that is, allocation in integral multiples of full slots. We derive sufficient conditions for schedulability and show that the proposed scheme achieves high levels of schedulable utilization. We also show that the schedulable utilization increases as the length of the allocation cycle increases and asymptotically approaches the maximum achievable utilization. We present a distributed slot access protocol to realize the proposed algorithm for ring architecture. The protocol can be easily modified for other topologies, such as bus and dual-bus networks. Using illustrative examples we demonstrate the effectiveness of the algorithm. 相似文献
17.
本文在理解群、环、域构成的基础上 ,提出了分级认证的电子政务认证体系 ,很好地把群、环、域的结构体系和电子政务三级认证体系与群、环、域中的运算法则和认证方法对应起来 ,并依照群、环、域中的运算法则 ,提出了三级认证体系的基本认证原则。同时 ,利用群同态和环同态的思想 ,得到了适合政务实情的三级认证体系分布式网络 ,为进一步研究电子政务做好了基础平台。 相似文献
18.
Joseph Y-T. Leung Tommy W. Tam Gilbert H. Young 《Journal of Parallel and Distributed Computing》1996,34(2):211
The problem of routing unit-length, real-time messages in a distributed system is considered. An on-line routing algorithm is one that routes messages without any knowledge of future arrivals of messages. An on-line algorithm is said to be optimal if it produces a feasible route whenever one exists. In this article, we study the issue whether it is possible to have an optimal on-line algorithm for the following networks—unidirectional ring, out-tree, in-tree, bidirectional tree, and bidirectional ring. The problem is considered under various restrictions of the four parameters—origin node, destination node, release time, and deadline. We show that: (1) for a unidirectional ring, no such algorithm can exist unless one of the four parameters is fixed (i.e., all messages have identical values for that parameter); (2) for an out-tree, no such algorithm can exist unless one of the three parameters—origin node, destination node, and release time—is fixed; (3) For an in-tree, no such algorithm can exist unless one of the three parameters—origin node, destination node, and deadline —is fixed; (4) for a bidirectional tree, no such algorithm can exist unless the origin node or the destination node is fixed; (5) for a bidirectional ring, no such algorithm can exist unless the origin node and either the destination node or the release time are fixed. Our results give a sharp boundary delineating those instances for which an optimal algorithm exists and those for which no such algorithm can exist. 相似文献
19.
Makki Kia Dell John Pissinou Niki Moh W. Melody Jia Xiaohua 《The Journal of supercomputing》2000,16(1-2):117-132
In this paper, we investigate distributed mutual exclusion algorithms and delineate the features of a new distributed mutual exclusion algorithm. The basis of the algorithm is the logical ring structure employed in token-based mutual exclusion algorithms. Specifically, there exists dynamic properties of the logical ring that, given certain restrictions regarding message traffic flow, passively give useful information about the location of the token. Effectively, the algorithm demonstrates a type of intelligent routing that identifies useful shortcuts in the routing of the token. The result is a reduction in the total number of messages exchanged prior to the execution of the critical section as compared to the algorithm proposed by Fu and Tzeng [3]. Furthermore, the algorithm allows for an increased degree of fairness in a lightly loaded system than that allowed by Fu and Tzeng's algorithm. The paper also addresses failure recovery issues. 相似文献
20.
A new and more detailed analysis of the unidirectional algorithm of Chang and Roberts for distributed extrema finding on a ring is presented. This analysis shows that this simple algorithm, which is known to be average case optimal, compares very favorably with all the other known algorithms as it requires O(n log n) messages with probability tending to one. A bidirectional version of this algorithm is presented and is shown to dominate the unidirectional one in its average message complexity. Finally, both the unidirectional and the bidirectional algorithms are generalized to perform k selection in the ring, i.e., find the k largest labeled processors. 相似文献