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.     

偏最小二乘回归在气温预测中的研究与应用

气温的预测要考虑多重气象因子,然而各气象因子间的多重相关性导致普通的多元回归模型失真,预测精度降低。为了解决以上问题,本研究采用偏最小二乘回归(Partial Least Squares Regression,简称PLS)建模,根据实际建模需要对算法进行改进。为了验证该模型,本研究以成都市10月份气温场为预报场,并结合成都市13个自动站气温数据,提取预报所需主要因子,进行PLS回归建模。实验表明该模型有较好的预测能力。     

一种新的修正恒模算法

阐述了恒模算法(CMA)、修正恒模算法(MCMA)和判决引导(DD)算法的基本原理。针对CMA和MCMA收敛速度慢,固定步长条件下收敛速度和剩余误差之间存在矛盾的缺陷,在分析CMA误差特性的基础上,利用DD算法误差函数的模值和判决器输出构造新的误差函数,提出了一种新的变步长MCMA。新算法在加快收敛速度的同时保持小的剩余误差。仿真结果表明,新算法比CMA和MCMA收敛速度快,均衡输出剩余码间干扰(ISI)小而且能克服相位偏移,具有很好的实用性。     

栅栏覆盖最大化生存周期调度算法

栅栏覆盖是近年来无线传感器网络的研究热点之一,如何延长生存周期是无线传感器网络研究的一个重要问题。针对无线传感器网络的栅栏覆盖应用,设计了两种最大化网络生存周期的调度算法:集中式的Greedy调度算法和分布式的DBCS调度算法。仿真实验表明:两种算法显著地延长了网络的生存周期;在较稀疏的网络中,DBCS算法与Greedy算法性能接近,分布式的DBCS算法适合应用于大规模传感器网络。     

机器人三维路径规划问题的一种改进蚁群算法

本文研究移动机器人三维空间路径规划问题,针对三维空间的复杂地形特点,提出了一种基于改进蚁群算法的路径规划算法。文中首先描述了一种简单有效的环境建模方法,然后给出了算法在信息素呈现、路径点选取、信息素更新以及启发式函数设计等方面的改进方法。仿真结果证明了算法的可行性和可靠性。     

信息融合技术在变压器油气识别故障诊断中的研究

变压器故障分为放电性故障和过热性故障两大类别,它们均会在变压器油中有所反映。本文通过对变压器油中主要气体的分析,判断变压器的故障类型。具体方法是:利用改进算法的BP网络和信息融合技术,以变压器油中五种主要特征气体作为神经网络的输入,以六种变压器状态作为相应的输出,通过加入动量因子,可以提高学习率系数,充分发挥改进算法的BP网络具有自适应学习能力的优势。仿真测试结果表明,本方法能够在较大范围内准确有效地进行变压器的故障诊断。     

图像处理中模糊算法问题的分析

图像处理是计算机常用技术之一,模糊算法的运用有助于提高图像处理的效果。传统图像处理存在诸多弊端,影响了用户获取信息的便捷性。本文分析了图像处理的基本操作内容,并阐述了模糊算法在图像处理流程中的运用,以进一步提升原始图像处理的效果。     

未知环境下基于约束点的移动机器人路径规划

针对未知环境中障碍物种类多样性和位置不确定性的特点,提出了基于约束点的路径规划方法。首先对机器人在未知环境中检测到的局部障碍物信息进行分类和几何特征属性描述,得其约束点信息,然后引入改进后的A*算法,将其搜索范围局限于约束点上,计算约束点的评价函数值后得到子目标点,机器人到达子目标点后,若陷入死区,则采取回溯路径策略,重新选择子目标点,否则根据该点所属的障碍物种类采取跨越或绕行避障策略,最后移动机器人在未知环境中顺利到达目标点。仿真研究说明本文提出的路径规划方法具有可行性和有效性。     

Parallel depth first search. Part II. Analysis

This paper presents the analysis of a parallel formulation of depth-first search. At the heart of this parallel formulation is a dynamic work-distribution scheme that divides the work between different processors. The effectiveness of the parallel formulation is strongly influenced by the work-distribution scheme and the target architecture. We introduce the concept of isoefficiency function to characterize the effectiveness of different architectures and work-distribution schemes. Many researchers considered the ring architecture to be quite suitable for parallel depth-first search. Our analytical and experimental results show that hypercube and shared-memory architectures are significantly better. The analysis of previously known work-distribution schemes motivated the design of substantially improved schemes for ring and shared-memory architectures. In particular, we present a work-distribution algorithm that guarantees close to optimal performance on a shared-memory/-network-with-message-combining architecture (e.g. RP3). Much of the analysis presented in this paper is applicable to other parallel algorithms in which work is dynamically shared between different processors (e.g., parallel divide-and-conquer algorithms). The concept of isoefficiency is useful in characterizing the scalability of a variety of parallel algorithms.This work was supported by Army Research Office Grant No. DAAG29-84-K-0060 to the Artificial Intelligence Laboratory, and Office of Naval Research Grant N00014-86-K-0763 to the Computer Science Department at the University of Texas at Austin.