The Doomsday distributed termination detection protocol

Distributed termination detection (DTD) algorithms are important since they detect globally stable states in distributed computations. Here we introduce a new DTD mechanism, the Doomsday protocol together with its proof of correctness. Doomsday is generic since it forms the basis for a number of new and existing DTD algorithms for which the correctness proof may be reused. The paper describes the Doomsday protocol, provides its formal proof, derives one new DTD algorithm and shows how other hitherto unrelated algorithms, Dijkstra–Scholten, Task Balancing and Credit Recovery, can be derived from the protocol. The paper concludes by examining various properties of the protocol in the context of existing DTD algorithms. This work was supported in part by Visiting Fellowship grant EPSRC GR/R84481/01 “The Doomsday Protocol” and by Australian Research Council ARC Linkage International Grant LX0349049 “Extending a Family of Garbage Collectors”.     

Algorithms for distributed termination detection

The termination problem for distributed computations is analyzed in the general context of asynchronous communication. In the underlying computational model it is assumed that messages take an arbitrary but finite time and do not necessarily obey the FIFO rule. Time diagrams are used as a graphic means of representing the overall communication scheme, giving a clear insight into the difficulties involved (e.g., lack of global state or time, inconsistent time cuts) and suggesting possible solutions.Several efficient algorithms for the solution of the termination problem are presented. They are all based on the idea of message counting but have a number of different characteristics. The methods are discussed and compared with other known solutions.Friedemann Matternreceived the Diploma in computer science from the University of Bonn, West Germany, in 1983.He is now a research scientist in the Department of Computer Science at the University of Kaiserslautern and is currently completing his Ph.D. His primary research interests include distributed algorithms, programming language design, and compiler construction. The author can be reached by electronic mail via mattern @ incas.uucp or mattern % uklirb.uucp @ Germany.csne.This work has been supported by the Deutsche Forschungsgemeinschaft (DFG) as part of the SFB124 research project VLSI-Design and Parallelism     

Termination detection for distributed computations

A simple derivation of a general solution to the problem of detecting the termination of a distributed computation is presented.     

An efficient parallel termination detection algorithm

In this paper, we present a new, easy to implement algorithm for detecting the termination of a parallel asynchronous computation on distributed-memory MIMD computers. We demonstrate that it operates concurrently with the main computation, adding minimal overhead, and we prove that it correctly detects termination when it occurs. Experimental results confirm that the termination detection routine imposes an overhead smaller than the experimental uncertainty.     

LSFR算法在多传感器分布式检测中的优化研究

在多传感器分布式检测系统中,常规融合规则算法要求传感器误差概率已知,且系统中传感器和融合中心同时优化存在一定困难.提出最小二乘融合规则(LSFR)算法,算法不依赖噪声环境稳定性以及传感器的虚警概率与检测概率,融合中心根据各个传感器的硬决策,得到全局的硬决策,并在传感器和融合中心处理达到最优时,获得最佳全局性能.仿真结果表明:对比似然比融合决策算法与Neyman Pearson融合规则(NPFR)算法,LSFR算法全局检测概率显著提高,且在不同数量规模传感器和更多类型的分布式检测系统中具有较好兼容性.     

A partially distributed deadlock detection algorithm

In this paper, a partially distributed deadlock detection algorithm [PDDDA] with multiple outstanding requests is presented for use in distributed database systems. This algorithm allows a process to request many resources simultaneously and uses a central controller for detecting multisite deadlocks. The detection of local deadlocks and the maintenance of local deadlock information are performed at each of the local sites. This partially distributed algorithm alleviates the problem of congestion at the central controller in a centralized algorithm and needs fewer messages and smaller storage space than a fully decentralized algorithm. A set of criteria for comparing deadlock detection algorithms are also given and then used to compare PDDDA with a fully decentralized algorithm proposed by Isloor and Marsland.Research reported herein was supported by US Army CECOM, Ft. Monmouth, New Jersey, under Contract No. DAAB07-83-K-K542. The views, opinions, and/or findings contained in this paper are those of the authors and should not be construed as an official Deportment of the Army position, policy or decision.     

利用绑定技术实现分布式继承

面向对象编程语言的继承机制实现了子类和父类间is-a的关系,子类对象成为一个有效的父类对象,具有了父类对象的功能,实现了继承和扩展父类的目的。但是继承难以在分布式环境中跨网络实现,难以实现异构的分布式对象间的继承,所以在借鉴已有绑定技术的基础上,文章将绑定应用到分布式对象之间,提出了一种新的分布式继承模型:利用分布式对象间的绑定来增强和扩展分布式对象的功能,从而达到一种分布式继承的效果。     

Towards the construction of distributed detection programs,with an application to distributed termination

Summary Methodological design of distributed programs is necessary if one is to master the complexity of parallelism. The class of control programs, whose purpose is to observe or detect properties of an underlying program, plays an important role in distributed computing. The detection of a property generally rests upon consistent evaluations of a predicate; such a predicate can be global, i.e. involve states of several processes and channels of the observed program. Unfortunately, in a distributed system, the consistency of an evaluation cannot be trivially obtained. This is a central problem in distributed evaluations. This paper addresses the problem of distributed evaluation, used as a basic tool for solution of general distributed detection problems. A new evaluation paradigm is put forward, and a general distributed detection program is designed, introducing the iterative scheme ofguarded waves sequence. The case of distributed termination detection is then taken to illustrate the proposed methodological design. Jean-Michel Hélary is currently professor of Computer Science at the University of Rennes, France. He received a first Ph.D. degree in Numerical Analysis in 1968, then another Ph.D. Degree in Computer Science in 1988. His research interests include distributed algorithms and protocols, specially the methodological aspects. He is a member of an INRIA research group working at IRISA (Rennes) on distributed algorithms and applications. Professor Jean-Michel Hélary has published several papers on these subjects, and is co-author of a book with Michel Raynal. He serves as a PC member in an international conference. Michel Raynal is currently professor of Computer Science at the University of Rennes, France. He received the Ph.D. degree in 1981. His research interests include distributed algorithms, operating systems, protocols and parallelism. He is the head of an INRIA research group working at IRISA (Rennes) on distributed algorithms and applications. Professor Michel Raynal has organized several international conferences and has served as a PC member in many international workshops, conferences and symposia. Over the past 9 years, he has written 7 books that constitute an introduction to distributed algorithms and distributed systems (among them: Algorithms for Mutual Exclusion, the MIT Press, 1986, and Synchronization and Control of Distributed Programs, Wiley, 1990, co-authored with J.M. Hélary). He is currently involved in two european Esprit projects devoted to large scale distributed systems.This work was supported by French Research Program C³ on Parallelism and Distributed ComputingAn extended abstract has been presented to ISTCS '92 [12]     

基于分布式Agent的入侵检测系统研究

随着网络入侵行为变得越来越普遍和复杂,传统的单一入侵检测系统已不能满足网络安全的发展需求,针对当前形势,为了提高计算机及网络系统的防御能力,提出了一种基于分布式Agent技术的入侵检测模型,并给出了一种可疑度算法和多IP地址连续报告策略,经测试和论证,系统可有效地阻止已知和未知的攻击行为,最后对系统的整体性能进行了详细描述。     

An efficient delay-optimal distributed termination detection algorithm

Distributed termination detection is a fundamental problem in parallel and distributed computing and numerous schemes with different performance characteristics have been proposed. These schemes, while being efficient with regard to one performance metric, prove to be inefficient in terms of other metrics. A significant drawback shared by all previous methods is that, on most popular topologies, they take Ω(P)$\mathrm{\Omega }(P)$ time to detect and signal termination after its actual occurrence, where P   is the total number of processing elements. Detection delay is arguably the most important metric to optimize, since it is directly related to the amount of idling of computing resources and to the delay in the utilization of results of the underlying computation. In this paper, we present a novel termination detection algorithm that is simultaneously optimal or near-optimal with respect to all relevant performance measures on any topology. In particular, our algorithm has a best-case detection delay of Θ(1)$\mathrm{\Theta }(1)$ and a finite optimal worst-case detection delay on any topology equal in order terms to the time for an optimal one-to-all broadcast on that topology (which we accurately characterize for an arbitrary topology). On k-ary n  -cube tori and meshes, the worst-case delay is Θ(D)$\mathrm{\Theta }(D)$, where D   is the diameter of the target topology. Further, our algorithm has message and computational complexities of Θ(MD+P)$\mathrm{\Theta }(\mathit{MD}+P)$ in the worst case and, for most applications, Θ(M+P)$\mathrm{\Theta }(M+P)$ in the average case—the same as other message-efficient algorithms, and an optimal space complexity of Θ(P)$\mathrm{\Theta }(P)$, where M is the total number of messages used by the underlying computation. We also give a scheme using counters that greatly reduces the constant associated with the average message and computational complexities, but does not suffer from the counter-overflow problems of other schemes. Finally, unlike some previous schemes, our algorithm does not rely on first-in first-out (FIFO) ordering for message communication to work correctly.     

基于Chi-square检验的分布式网络入侵检测系统

针对网络攻击的新特点,本文提出了一种基于Chi-square检验的分布式网络入侵检测系统模型CTDIDS。设计并实现了一个基于异常检测的入侵分析引擎。通过对网络数据包的分析,运用Chi-square值比较对系统的行为进行检测。与现有的入侵检测方法相比,本文提出的方法具有更好的环境适应性和数据协同分析能力。实验证明,分布式入侵检测系统CTDIDS具有更高的准确性和扩展性。     

分布式发电系统的复合型孤岛检测方法研究

为了解决分布式发电系统中存在的孤岛检测问题,提出了一种新型复合式孤岛检测方法。该方法通过改变扰动电流波形对传统的AFD检测方法进行改进,并结合传统被动式孤岛检测方法判定孤岛现象的发生。结合IEEE.Std.2000-929/UL1741标准中的技术规范,利用Matlab/Simulink对新方法进行了仿真验证。仿真结果显示,该方法既能快速、准确地检测出孤岛现象,又把对电网电能质量的影响降到最小。     

分布式网络入侵检测代理系统的改进设计方案研究

提出了一个分布式网络入侵检测代理系统的改进设计方案,以层次式的体系结构为蓝本,结合对等式模型提出了双控中心策略,当"主控制中心"失效时,由"从控制中心"代替行使控制权,按对等式方式工作.该方案提高了系统的容错性,最大可能的避免了单点失效而引起连锁反应问题.同时给出了在移动代理整合入侵检测系统(MACIDS)框架下,基于测量服务层次协议的Agent详细设计,通信平台的3个层次、4个功能组件的划分和如何在分布式、对等式两种工作方式共享数据和资源进行通信的过程.     

一种基于环形协作算法的分布式入侵检测模型

文章分析了当前流行的分布式入侵检测系统的特征以及协作方式，提出了一种基于逻辑环形协作算法的分布式入侵检测系统，以解决目前分布式入侵检测系统中各系统间协作效率低、检测响应慢的缺陷。     

基于移动代理的分布式入侵检测系统的研究

分析了现有入侵检测系统的不足,提出了一个基于移动代理的分布式入侵检测系统的模型,对系统中各个组件的功能进行了描述,同时对移动代理的安全问题进行了讨论.该模型采用无控制中心的协作式组件体系结构,完全避免了单点失效问题.移动代理之间各自独立,同时相互通信,协作完成入侵检测任务,真正实现了分布式的检测,增强了系统的灵活性和可扩展性.     

基于CORBA的分布式入侵检测模型的设计与实现

针对目前入侵检测系统中面临的平台异构、无统一通信机制和安全策略等问题,将分布式中间件的CORBA技术与入侵检测技术结合在一起,提出了一种新型的基于CORBA的分布式入侵检测系统模型(CDIDS)。从入侵检测系统的发展、分布式入侵检测系统和CORBA技术谈起,详细讲述了基于CORBA的分布式入侵检测系统模型的体系结构、实现方法和安全问题,并解决了基于CORBA的入侵检测系统的异步调用死锁问题。     

论中国传统造型观念在图形设计中的传承

传统造型观念是中国传统艺术的一个重要组成部分,它作为一种民族文化和视觉美感的研究形式,是不容被忽视的。本文通过对传统造型观念在造型手法与特点等方面的分析,找出它在艺术形式和表现手法上对现代图形设计的影响。并进一步论述中国传统造型观念对于图形设计的现实意义.从而说明传承与发扬我们的传统文化,把其精神元素融入图形设计中,必定会使图形设计与国际化视觉语言进行有机结合,这是中国现代设计的必由之路。     

用继承扩展XML-RL

XML正在成为Internet上数据描述和交换的标准，用一些重要的面向对象的特征扩展基于高级数据模型上的以规则为基础的XML查询语言XML-RL．首先用元素层次，多重继承和多态扩展了XML-RL数据模型．然后扩展XML-RL以支持多态元素，多态引用，独占元素和独占引用．     

分布式系统的移动代理保障检测机制

移动代理技术为解决复杂、动态、分布式的应用提供了新的计算手段,结合Agent技术的特点以及Agent技术与分布式系统的相互适应性,进行一种基于Agent技术的用来对分布计算机网络或服务个体行为关键点进行监测和信息收集的研究,提出一种可行的移动代理保障检测机制,为分布式系统提供主动的分布式系统可靠性保障情况报告和建议性措施。