Distributed match-making

In many distributed computing environments, processes are concurrently executed by nodes in a store- and-forward communication network. Distributed control issues as diverse as name server, mutual exclusion, and replicated data management involve making matches between such processes. We propose a formal problem called distributed match-making as the generic paradigm. Algorithms for distributed match-making are developed and the complexity is investigated in terms of messages and in terms of storage needed. Lower bounds on the complexity of distributed match-making are established. Optimal algorithms, or nearly optimal algorithms, are given for particular network topologies.The work of the second author was supported in part by the Office of Naval Research under Contract N00014-85-K-0168, by the Office of Army Research under Contract DAAG29-84-K-0058, by the National Science Foundation under Grant DCR-83-02391, and by the Defence Advanced Research Projects Agency (DARPA) under Contract N00014-83-K-0125. Current address of both authors: CWI, Kruislaan 413, 1098 SJ Amsterdam, The Netherlands.     

A self-adjusting algorithm for byzantine agreement

Summary Byzantine Agreement is important both in the theory and practice of distributed computing. However, protocols to reach Byzantine Agreement are usually expensive both in the time required as well as in the number of messages exchanged. In this paper, we present a self-adjusting approach to the problem. The Mostly Byzantine Agreement is proposed as a more restrictive agreement problem that requires that in the consecutive attempts to reach agreement, the number of disagreements (i.e., failures to reach Byzantine Agreement) is finite. Fort faulty processes, we give an algorithm that has at mostt disagreements for 4t or more processes. Another algorithm is given forn3t+1 processes with the number of disagreements belowt ²/2. Both algorithms useO(n ³) message bits for binary value agreement. Yi Zhao is currently working on his Ph.D. degree in Computer Science at University of Houston. His research interests include fault tolerance, distributed computing, parallel computation and neural networks. He obtained his M.S. from University of Houston in 1988 and B.S. from Beijing University of Aeronautics and Astronautics in 1984, both in computer science. Farokh B. Bastani received the B. Tech. degree in electrical engineering from the Indian Institute of Technology, Bombay, India, and the M.S. and Ph.D. degrees in electrical engineering and computer science from the University of California, Berkeley. He joined the University of Houston in 1980, where he is currently an Associate Professor of Computer Science. His research interests include software design and validation techniques, distributed systems, and fault-tolerant systems. He is a member of the ACM and the IEEE and is on the editorial board of theIEEE Transactions on Software Engineering.     

An improved algorithm for finding the median distributively

Given two processes, each having a total-ordered set ofn elements, we present a distributed algorithm for finding median of these 2n elements using no more than logn +O(logn) messages, but if the elements are distinct, only logn +O(1) messages will be required. The communication complexity of our algorithm is better than the previously known result which takes 2 logn messages.     

Analysing interactive devices based on information resource constraints

Analysis of the usability of an interactive system requires both an understanding of how the system is to be used and a means of assessing the system against that understanding. Such analytic assessments are particularly important in safety-critical systems as latent vulnerabilities may exist which have negative consequences only in certain circumstances. Many existing approaches to assessment use tasks or scenarios to provide explicit representation of their understanding of use. These normative user behaviours have the advantage that they clarify assumptions about how the system will be used but have the disadvantage that they may exclude many plausible deviations from these norms. Assessments of how a design fails to support these user behaviours can be a matter of judgement based on individual experience rather than evidence. We present a systematic formal method for analysing interactive systems that is based on constraints rather than prescribed behaviour. These constraints capture precise assumptions about what information resources are used to perform action. These resources may either reside in the system itself or be external to the system. The approach is applied to two different medical device designs, comparing two infusion pumps currently in common use in hospitals. Comparison of the two devices is based on these resource assumptions to assess consistency of interaction within the design of each device.     

Comparative analysis of two different middleware approaches for reconfiguration of distributed real-time systems

Software-based reconfiguration of distributed real-time systems is a complex problem with many sides to it ranging from system-wide concerns down to the intrinsic non-robust nature of the specific middleware layer and the used programming techniques. In a completely open distributed system, mixing reconfiguration and real-time is not possible; the set of possible target states can be very large threatening the temporal predictability of the reconfiguration process. Over the last years, middle ware solutions have appeared mainly for general purpose systems where efficient state transitions are sought for, but real-time properties are not considered. One of the few contributions to run-time software reconfiguration in distributed real-time environments has been the iLAND middleware, where the germ of a solution with high potential has been conceived and delivered in practice.¹ The key idea has been the fact that a set of bounds and limitations to the structure of systems and to their open nature needs to be imposed in order to come up with practical solutions. In this paper, the authors present the different sides of the problem of software reconfiguration from two complementary middleware perspectives comparing two strategies built inside distribution middleware. We highlight the lessons learned in the iLAND project aimed at service-based reconfiguration and compare it to our experience in the development of distributed real-time Java reconfiguration based on distributed tasks rescheduling. Authors also provide a language view of both solutions. Lastly, empirical results are shown that validate these solutions and compare them on the basis of different programming language realizations.     

车载自组织网络分布式入侵检测算法研究

随着汽车产业的发展,汽车给我们带来便利的同时也给我们带来一系列的问题,例如交通拥堵、交通安全等。为了解决这些问题车载自组织网络应运而生。但是车载自组织网络中信息安全问题一直存在,采用分布式入侵检测模型和基于此模型下的改进随机森林分类算法可以很好地解决这个问题。     

基于控制微元的统计自适应增量控制方法

依据系统对模拟量实时控制的要求,提出了基于控制微元的统计自适应增量控制方法,给出了量化控制状态统计图的获取方法,分别找出了扩展控制微元的统计稳定系数、平均统计状态偏差、统计趋势、统计超调、尾偏差等参数与调节增量之问的关系,确定了统计控制策略及其最优化条件,给出了统计预测自适应记忆增量控制器的设计方案.该方法易于微处理器编程,运算速度快,可高效率实现对模拟量的精确控制.     

动态划分序列模式挖掘算法

在对海量数据进行序列模式挖掘时,由于产生的候选序列数量大并且需要反复遍历数据库,会带来存储受限及时效性问题.为此,基于无共享分布式环境,提出一种动态划分序列模式挖掘算法DPSPM.通过分布数据降低数据库扫描的规模,降低I、O开销,使用分派函数指定选举节点,降低通信开销,设计动态列表存储候选序列,降低内存开销,多个子过程异步运行,提高算法的执行效能.实验结果表明,DPSPM算法在较小支持度情况下对中大型数据库有较好的搜索效率.     

C4KISR测试与评估应用框架的研究与实现

基于HLA/RTI和分布式数据库初步构建了一个开放的测试和评估应用框架,为战术C4KISR系统中的指挥、控制、通信(C3)以及典型飞行器武器系统的作战效能(K)提供一种有效的可扩展的测试评估环境.系统采用了基于HLA/RTI的分布式体系结构,与被测系统相连.建立了典型的层次化战术CAKISR系统效能指标体系,并实现相应的评估算法模型.基于Oracle数据库建立了通用的战术C4KISR系统试验数据库/用例库/算法库和相应的管理工具,并开发了通用的分析评估工具,支持评估指标的在线/离线计算和显示.     

改进NS2对局域网分布式系统在线仿真的实现

目前大多数仿真系统采用流量发生器等模拟l离散事件的发生,为了充分模拟网络环境中分布式系统各子系统的并发运行和彼此之间依据算法的实时交互,设有虚拟局域网VLAN的IEEE802.1Q协议。提出一种改进NS2模拟局域网分布式系统实际运行的在线仿真的集成方法,将各分布式应用对象移植为NS2的C++扩展对象,执行实际算法,构造一个模拟中心调度对象,管理各分布式对象的并发运行、转发各分布式对象之间的消息交给NS2以模拟其网络延迟,与领域仿真软件交换数据等。对NS2中共享式以太网协议模块改造,添加VLAN802.1Q协议模块,分别实现对交换式局域网和多播报文的模拟。变电站自动化系统的通信网络仿真实验结果,验证了在线仿真方法是有效的、所扩展的NS2模块是正确的。