Semi-distributed load balancing for massively parallelmulticomputer systems

A semidistributed approach is given for load balancing in large parallel and distributed systems which is different from the conventional centralized and fully distributed approaches. The proposed strategy uses a two-level hierarchical control by partitioning the interconnection structure of a distributed or multiprocessor system into independent symmetric regions (spheres) centered at some control points. The central points, called schedulers, optimally schedule tasks within their spheres and maintain state information with low overhead. The authors consider interconnection structures belonging to a number of families of distance transitive graphs for evaluation, and, using their algebraic characteristics, show that identification of spheres and their scheduling points is in general an NP-complete problem. An efficient solution for this problem is presented by making exclusive use of a combinatorial structure known as the Hadamard matrix. The performance of the proposed strategy has been evaluated and compared with an efficient fully distributed strategy through an extensive simulation study. The proposed strategy yielded much better results     

Accurate distributed and semidistributed models of field effect transistors for millimeter wave applications

An accurate distributed model of field effect transistors, including the parasitic impedances of the electrodes and the mutual coupling between them for analyzing the propagation effects along the electrodes working at millimeter wave frequencies, is presented. A numerical method is used to calculate the S‐parameters of the distributed model. Then, a corresponding simpler semidistributed model, which avoids solving coupled differential equations, is then presented. A GaAs pHEMT example is given to show the well agreement of the S‐parameters of the measurement and the distributed model ranging from 1 to 60 GHz. The S‐parameters of the semidistributed model agree well with that of the distributed model up to 100 GHz, and both of the models can be applied for S‐parameters prediction out of the measurement equipment range. © 2011 Wiley Periodicals, Inc. Int J RF and Microwave CAE, 2011.     

LLACA: An adaptive localized clustering algorithm for wireless ad hoc networks

Performance of ad hoc networks dramatically declines as network grows. Cluster formation in which the network hosts are hierarchically partitioned into several autonomous non-overlapping groups, based on proximity, is a promising approach to alleviate the scalability problem of ad hoc networks. In this paper, we propose a localized learning automata-based clustering algorithm for wireless ad hoc networks. The proposed clustering method is a fully distributed algorithm in which each host chooses its cluster-head based solely on local information received from neighboring hosts. The proposed algorithm can be independently localized at each host. This results in a significantly reduction in message overhead of algorithm, and allows cluster maintenance can be locally performed only where it is required. To show the performance of proposed algorithm, obtained results are compared with those of several existing clustering methods in terms of the number of clusters, control message overhead, clustering time, and load standard deviation.     

Dynamic load balancing for parallel polygon rendering

Using parallel processing for visualization speeds up computer graphics rendering of complex data sets. A parallel algorithm designed for polygon scan conversion and rendering is presented which supports fast rendering of highly complex data sets using advanced lighting models. Dedicated graphics rendering engines do not necessarily suit such data sets, although they can support real-time update of moderately complex scenes using simple lighting. Advantages to using a software-based approach include the feasibility of adding special rendering features to the program and the capability of integrating a parallel scientific application with a parallel graphics renderer. A new work decomposition strategy presented, called task adaptive, is based on dynamically partitioning the amount of computational work left at a given time. The algorithm uses a heuristic for dynamic task decomposition in which image space tasks are partitioned without requiring interruption of the partitioned processor. A sophisticated memory referencing strategy lets local memory access graphics data during rendering. This permits implementation of the algorithm on a distributed memory multiprocessor. An in-depth analysis of the overhead costs accompanying parallel processing shows where performance is adequate or could be improved     

通讯信息约束下具有全局稳定性的分布式系统预测控制

本文针对一类由状态相互耦合的子系统组成的分布式系统, 提出了一种可以处理输入约束的保证稳定性的非 迭代协调分布式预测控制方法(distributed model predictive control, DMPC). 该方法中, 每个控制器在求解控制率时只与 其它控制器通信一次来满足系统对通信负荷限制; 同时, 通过优化全局性能指标来提高优化性能. 另外, 该方法在优化 问题中加入了一致性约束来限制关联子系统的估计状态与当前时刻更新的状态之间的偏差, 进而保证各子系统优化问 题初始可行时, 后续时刻相继可行. 在此基础上, 通过加入终端约束来保证闭环系统渐进稳定. 该方法能够在使用较少 的通信和计算负荷情况下, 提高系统优化性能. 即使对于强耦合系统同样能够保证优化问题的递推可行性和闭环系统的 渐进稳定性. 仿真结果验证了本文所提出方法的有效性.     

A QoS Multicast Routing Algorithm Working with Imprecise State Information

In large networks, maintaining precise global network state information is almost impossible. Many factors, including non-negligible propagation delay, infiequent link state update due to overhead concerns, link state update policy, and hierarchical topology aggregation, have impacts on the precision of the network state information. The existing QoS multicast routing algorithms do not provide satisfactory performance with imprecise state information. In this paper, we propose a distributed QoS multicast routing scheme based on traffic lights, called QMRI algorithm, which can probe multiple feasible tree branches, and select the optimal or near-optimal branch through the UR or TL mode for constructing a multicast tree with QoS guarantees if it exists. The proposed algorithm considers not only the QoS requirements but also the cost optimality of the multicast tree. Extensive simulations show that our algorithm achieves high call-admission ratio and low-cost multicast trees with modest message overhead. The algorithm can tolerate high degree of state information imprecision.     

Providing distributed certificate authority service in cluster-based mobile ad hoc networks

Nodes in a mobile ad hoc network (MANET) are more vulnerable and there is no predefined infrastructure in such a network. Providing secure communication in these networks is an important and challenging problem. Among all proposed schemes, the model of using distributed certificate authorities (CA) based on threshold cryptography and proactive share update using a cluster-based architecture seems to be a promising approach. However, there are two issues that are not well studied in the current literature for this model: (1) how to locate enough CA servers, and (2) how to perform the proactive share update. In this paper, we propose two efficient schemes with low system overhead to tackle these two problems. Compared with existing approaches, our CA architecture provides faster CA services to user nodes at reduced system overhead. The effectiveness of our proposed schemes has been verified by extensive simulation.     

基于改进PBFT算法的PKI跨域认证方案

为解决现有公钥基础设施跨域认证方案的效率问题,利用具有分布式和不易被篡改优点的区块链技术,提出基于联盟区块链的跨域认证方案。一方面,该方案对联盟链在传统实用拜占庭共识算法(PBFT)的基础上加入了节点动态增减功能;改进了主节点选举方式;将三阶段广播缩减为两阶段广播,减少了通信开销。另一方面,该方案设计了联盟链跨域认证协议,给出了区块链证书格式,描述了跨域认证协议,并进行了安全和效率分析。分析表明,在安全方面,该方案具有抵抗分布式攻击等安全属性;在效率方面,与已有跨域认证方案相比,该方案在计算开销上、通信开销上都有优势。     

CMV: File consistency maintenance through virtual servers in peer-to-peer systems

Peer-to-peer (P2P) has become a mainstream architecture in numerous diverse distributed applications. However current P2P systems do not provide consistency guarantees under multiple reader multiple writer scenarios. Such a feature is desirable as well as necessary for supporting more diverse applications than merely file-sharing systems. In this paper, we develop a highly scalable and efficient algorithm, called Consistency Maintenance through Virtual servers (CMV), in P2P systems. In this algorithm, consistency of each dynamic file is maintained by a Virtual Server (VS). A file update can only be accepted through the VS to ensure one-copy serializability consistency. The VS of a file is a logical network composed of multiple Replica Peers (RPs) that have replicas of the file. Mathematical analysis is performed for optimal parameter selections that achieve minimum overhead messages for maintaining file consistency. Simulation experiments are conducted to compare the performance of the proposed CMV algorithm with two existing schemes, namely the rumor spreading based scheme and the Update Propagation Through Replica Chain (UPTReC) scheme. Our results show that CMV can quickly commit update to the system and significantly reduce (by more than 90%) overhead messages compared to these schemes under various system conditions.     

基于正交梯度搜索的动态系统递阶优化辨识

提出了一种辨识线性时不变状态空间系统参数的正交梯度二步递阶优化方法. 通过极小化输出误差目标函数获得了系统参数估计; 提出了正交梯度搜索方法用于解决系统参数的非唯一性问题, 正交梯度搜索的本质是在输入-输出等价类相切平面的正交垂空间更新系统参数; 给出了用 L-M 算法进行参数优化的充分条件; 提出的系统参数递阶优化辨识方法包括两步: 首先用给出的自适应 L-M 算子正交梯度方法确定参数优化方向; 其次由一维搜索方法计算最佳步长. 蒙特卡罗数值仿真实验表明本文提出的方法具有收敛速度快、抗噪能力强以及数值稳定性好等优点.     

Performance analysis of synchronization for two communicating processes

Synchronization of processes is one of the major performance bottlenecks in a distributed system. The synchronization is usually achieved via message passing. There are two basic types of overhead in such a synchronization: the rate of message exchange, and the blocking probabilities of processes. In this paper we consider two processes synchronizing via message passing and study their performance behavior on the basis of the above-mentioned overheads. A number of protocols for message exchange are analyzed. The model gives rise to a three-dimensional Markov chain. An algorithm to solve the model and numerical results are presented to compare the various protocols.     

面向可变用户群体的可搜索属性基加密方案

为解决属性基加密方案中用户撤销繁琐、密文更新计算开销大的问题,提出一种面向可变用户群体的可搜索属性基加密方案.利用二叉树管理撤销列表,当需要撤销用户时,可信中心只要将其加入撤销列表,并通知云服务器更新部分密文,提高了用户撤销的效率.考虑到利用二叉树实现用户撤销会导致系统中用户数量存在上限,当某个二叉树叶结点所代表的用户被撤销后,只要更新二叉树中设置的随机值,其他用户就可以重复使用该结点.基于配对计算为用户提供密文搜索功能,并保证被撤销的用户无法搜索密文.安全性分析表明,该方案在随机谕言模型下满足选择明文不可区分安全性.性能分析和实验数据表明,该方案相比于同类方案,计算开销更小.     

基于多Agent的分布式通信对抗目标分配系统

针对通信对抗目标分配的特点,提出一种基于多Agent的分布式目标分配系统。给出问题描述和模型建立的方法,设计分布式协同拍卖机制和分布协同拍卖算法,其中,分布协同拍卖算法包括竞拍序列禁忌规则、目标威胁度更新规则等。仿真结果表明,与遗传算法相比,该算法收敛速度较快、实时性较强。     

一种层次的、混合并行离散事件仿真算法

并行仿真算法是并行离散事件仿真中心的核心问题，对于具体的应用系统，采用不同的并行仿真算法将导致其仿真性能大的差异，提出了一种针对于分布环境中特定应用系统仿真的层次的，混合并行离散事件仿真算法，测试和应用表明，和通常的保守机制或者乐观机制相比，能够较大地提高仿真效率，并且具有良好的可扩展性，首先给出了在通信开销不可忽略的环境下，保守机制和乐观机制的性能测试结果和两者适用情况的分析，然后根据测试结果和具体应用系统的特点，提出了层次的，混合并行离散事件仿真算法，给出了LP级和组级算法算，最后对算法进行了测试和性能分析。     

Task assignment in distributed computing systems

The problem is addressed of assigning a task with a precedence constraint to a distributed computing system. Task turnaround time with regard to communication overhead and idle time is adopted to measure the performance of task assignment. The assignment of the module is determined as is the sequence of message transmission to balance the processor load and reduce communication overhead. The search for the optimal task assignment with a precedence constraint is known to be NP-complete (Garey et al. 1979) in the strong sense. A heuristic algorithm with polynomial time complexity is then proposed in order to solve the task-assignment problem effectively. Experimental results show that the proposed approach produces a near-optimal or even optimal task assignment.     

Simulating Spatially Explicit Problems on High Performance Architectures

This paper addresses issues of implementation and performance optimization of simulations designed to model spatially explicit problems with the use of parallel discrete event simulation. A simulation system is presented that uses the optimistic protocol and runs on a distributed memory machine—the IBM SP. The efficiency of parallel discrete event simulations that use the optimistic protocol is strongly dependent on the overhead incurred by rollbacks. This paper introduces a novel approach to rollback processing which limits the number of events rolled back as a result of a straggler or antimessage. The method, called Breadth-First Rollback (BFR), is suitable for spatially explicit problems where the space is discretized and distributed among processes and simulation objects move freely in the space. The BFR uses incremental state saving, allowing the recovery of causal relationships between events during rollback. These relationships are then used to determine which events need to be rolled back. This paper presents an application of BFR to the simulation of Lyme disease. Our results demonstrate and almost linear speedup—a dramatic improvement over the traditional approach to rollback processing. Additionally, BFR is used as a basis of a dynamic load balancing algorithm that migrates load between the simulation processes. A brief outline of the algorithm and its potential performance are presented.     

An Adaptive Distributed Channel Allocation Strategy for Mobile Cellular Networks

A channel allocation algorithm includes a channel acquisition algorithm and a channel selection algorithm. Most of the previous work concentrates on the channel selection algorithm since early channel allocation algorithms simply use a centralized channel acquisition algorithm, which depends on a mobile switching center (MSC) to accomplish channel acquisition. Recently, distributed channel acquisition algorithms have received considerable attention due to their high reliability and scalability. There are two approaches to designing distributed channel acquisition algorithms: search and update. The update approach has shorter acquisition delay and lower call blocking rate, but higher message complexity. On the other hand, the search approach has lower message complexity, but longer acquisition delay and higher call blocking rate. In this paper, we propose a novel distributed channel acquisition algorithm, which is a significant improvement over both approaches. Also, we identify two guiding principles in designing channel selection algorithms and propose an algorithm which has low call blocking rate and low intrahandoff overhead. By integrating the channel selection algorithm into our channel acquisition algorithm, we get a complete distributed channel allocation algorithm. By keeping the borrowed channels, the channel allocation algorithm makes use of the temporal locality and adapts to the network traffic; i.e., free channels are transferred to hot cells to achieve load balance. Simulation results show that our channel allocation algorithm significantly outperforms the search approach and the update approach in terms of call blocking rate, message complexity, and acquisition delay.     

Efficient mining of association rules in distributed databases

Many sequential algorithms have been proposed for the mining of association rules. However, very little work has been done in mining association rules in distributed databases. A direct application of sequential algorithms to distributed databases is not effective, because it requires a large amount of communication overhead. In this study, an efficient algorithm called DMA (Distributed Mining of Association rules), is proposed. It generates a small number of candidate sets and requires only O(n) messages for support-count exchange for each candidate set, where n is the number of sites in a distributed database. The algorithm has been implemented on an experimental testbed, and its performance is studied. The results show that DMA has superior performance, when compared with the direct application of a popular sequential algorithm, in distributed databases     

基于分布式路径计算单元的多域光网络组密钥管理方案

针对分布式路径计算单元（PCE）架构下多域光网络的通信特点和密钥管理需求，提出一种该架构下的组密钥管理方案。首先使用超图理论对分布式PCE架构下的多域光网络密钥关系进行建模得到两层式密钥超图；然后在自治域层采用基于自认证公钥密码体制和成员过滤技术的密钥管理方法，在PCE层采用基于椭圆曲线密码体制的组密钥协商方法；最后完成密钥的产生、分发、更新和动态管理，较好地解决了成员的私钥保密性问题和第三方节点的冒充问题，减少了密钥更新时的计算开销。性能分析显示，该方案具有前向安全性、后向安全性、密钥保密性和抗合谋攻击等特点，与典型的分散式方案相比，在密钥存储量、加解密次数和通信开销等方面取得了较优的性能。     

移动自组织网络下的基本蚁群路由算法

针对移动自组织网络资源受限的特点和目前已有的蚁群路由算法比较复杂的问题,提出一种基本蚁群路由算法。通过对蚁群路由流程的分析,只维持基本的蚁群路由机制,不增加额外开销。详细讨论算法中信息素更新和信息素使用两项关键机制,并且通过模拟实验分析它们对性能的影响。实验结果表明,该算法能够以很低的开销取得与其他路由协议相近的性能。