Necessary and sufficient conditions on information for causal message ordering and their optimal implementation

Summary. This paper formulates necessary and sufficient conditions on the information required for enforcing causal ordering in a distributed system with asynchronous communication. The paper then presents an algorithm for enforcing causal message ordering. The algorithm allows a process to multicast to arbitrary and dynamically changing process groups. We show that the algorithm is optimal in the space complexity of the overhead of control information in both messages and message logs. The algorithm achieves optimality by transmitting the bare minimum causal dependency information specified by the necessity conditions, and using an encoding scheme to represent and transmit this information. We show that, in general, the space complexity of causal 0message ordering in an asynchronous system is , where is the number of nodes in the system. Although the upper bound on space complexity of the overhead of control information in the algorithm is , the overhead is likely to be much smaller on the average, and is always the least possible. Received: January 1996 / Accepted: February 1998     

一种高性能的全序组播算法

全序组播是构建分布式应用程序的一种重要组通信原语,它能够保证一个通信组中的所有成员都按照同样的顺序接收消息.目前的全序组播算法不能同时获取低延迟和高吞吐量,并且缺乏对应用程序通信模式的适应性,因此不适用于高性能计算环境.在分析已有算法排序机制基础上,指出影响全序组播算法性能的关键因素,并提出一种基于leader/followers模式和阻塞检测机制的新算法.算法工作原理如下:每一个组成员都可以在任意时刻发送消息,但只能提交来自当前leader成员的消息;一旦leader成员进入不活跃状态,则通过特殊的命令来指定某个活跃的follower成员为新的leader成员.模拟实验结果表明,该算法在延迟时间和吞吐量等性能指标方面都优于已有算法,同时在突发消息模式下能够大幅度提升性能.     

Performance of the optimal causal multicast algorithm: a statistical analysis

An optimal causal message ordering algorithm for asynchronous distributed systems was proposed by Kshemkalyani and Singhal and its optimality was proven theoretically. For a system of n processes, although the space complexity of this algorithm was shown to be O(n/sup 2/) integers, it was expected that the actual space overhead would be much less than n/sup 2/. It is difficult to determine the behavior of this algorithm by a theoretical analysis. We measure the overheads of two different implementations of the optimal causal message ordering algorithm via simulation under a wide range of system conditions. The optimal algorithm is seen to display significantly less message space overhead and log space overhead than the canonical Raynal-Schiper-Toueg algorithm.     

一种基于移动计算环境的因果日志卷回恢复算法

由于移动节点的不可靠和无线网络连接的脆弱性,研究移动计算系统容错机制具有重要意义.对可以跨区移动、随时可以与网络断开的自治性很强的移动节点来说,异步的卷回恢复是一种重要的容错手段.现有的移动计算环境下的卷回恢复算法都无法完全实现一致的异步卷回恢复.基于因果消息日志,提出一种新的移动计算环境的卷回恢复算法:通过先行图来记录节点间的消息依赖关系,将异步检查点、基于发送方的暂存消息日志和先行图全部在移动支持站上存储和处理,为移动节点提供一种透明的容错服务,完全消除依赖关系在移动节点之间造成的影响.用形式化的方法证明了系统的一致性.仿真结果表明,在卷回开销达到最低的同时,也显著降低了无错运行时的通信和存储开销.     

Dynamic route maintenance for geographic forwarding in mobile ad hoc networks

Traditional route maintenance requires mobile nodes periodically exchange beacon messages with their neighbors in geographic forwarding algorithms. The interval at which these nodes broadcast their beacon messages is typically fixed. However, determining an appropriate value for this interval is challenging. A longer interval reduces the number of beacons needed, but may result in significant location errors. Conversely, a shorter interval guarantees more accurate location information, but induces heavier control overheads. Additionally, since a fixed value is assigned to the lifetime of each routing entry, the forwarding algorithm cannot adapt well to different mobility environments. Therefore, this paper presents a dynamic route maintenance algorithm (DRM) for beacon-based geographic routing. In the approach, the mobile nodes dynamically adjust their beacon intervals based on their speed of movement. Moreover, the routing information can be well managed using the mobility prediction. The simulation results show that DRM not only significantly decreased the routing overheads in a low mobility scenario but also guaranteed the high quality packet delivery in high mobility environments.     

使用发布订阅中间件支持移动计算

提出了一个扩展发布订阅中间件以支持移动计算的新协议．该协议针对移动计算的需求，由老的事件代理暂存客户移动期间到达的消息，客户在连接到新的事件代理后，消息被自动有序发送给客户，保证了移动透明性．此外协议采用同步算法和消息合并操作防止了消息丢失和重复．移动客户可以在不同的地域与不同的事件代理节点连接和可靠接收消息．实验表明谈协议完全满足移动应用的要求，保证了应用的透明性、消息完整性和有序性．     

基于链接预测的水下WSN消息转发算法

随着移动自组织网络的发展以及为了更加便捷地监测和探索水下环境,水下无线传感器网络开始出现并逐渐受到研究人员的重视.水下无线传感器网络可广泛应用于海洋环境监测、资源开采、水下生物研究、海难搜救等诸多水下场景.与传统的无线传感器网络不同,通常,水下无线传感器网络中存在锚定节点和移动节点两种类型的节点,并且由于水声通信的不规...     

基于星球机器人分布计算系统的原子组播协议

针对星球机器人分布计算系统容错的可靠组播通信,提出了一种基于向量时间的原子组组播协议.协议从星球机器人分布计算系统及通信模型的特点出发,使用向量时间和令牌进程来标识和保证全局投递顺序,通过令牌进程对不稳定消息的转发和两阶段提交来保证投递原子性和虚同步.模拟实验表明,协议提供了一个代价较小的可靠组播方法,具有快速和轻量的优点.     

Total ordering group communication protocol based on coordinating sequencers for multiple overlapping groups

This paper presents a total ordering protocol for group communication systems with multiple overlapping groups. Our protocol takes advantages of the simplicity of the sequencer-based approach, but employs multiple sequencers to achieve better load balance. For a given message, the sequencer of the destination group constructs a sequencing array by requesting for relative delivery positions from the sequencers of the overlapping groups. The sequencing array is used by any receiving process to determine the delivery sequence of the message. The notion of logical clock is used for determining the relative delivery sequences of the messages. The coordination between the sequencers is performed in a simple, asynchronous and non-blocking manner. The delivery operation at a receiving process is very simple, and a message can be delivered as soon as it becomes deliverable. These factors amount to a significant saving of the computing and communication overhead for the system. As the protocol demands the minimum effort from the group members it is suitable for mobile computing environment in which mobile devices are typically tight on resources. In the paper, we also present some ways to enhance the performance of the system. Extension of the protocol to encompass the preservation of causality, the dynamic group membership and the failure recovery is included in the paper.     

Mobile Agent Connection Establishment and Management (CEMA)—Message Exchange for Pervasive Computing Environments

Pervasive computing is an emerging technology that offers new possibilities to distributed computing and computer networking; it employs a wide variety of smart, ubiquitous devices throughout an individual's working and living environment. Mobile agents are software entities that can migrate between servers (mobile agent environments) of the network accomplishing various tasks on the behalf of their owners. The objective of this paper is to describe a test and prototyping environment for experimenting with mobile agents in pervasive environments. A prototype environment for a novel, proactive infrastructure is described for mobile agent assisted pervasive computing. In addition, a new message passing algorithm is provided for mobile agent connection establishment and management (CEMA). Simulation results show the performance of the proposed approach.     

Optimal NODUP all-to-all broadcast schemes in distributed computingsystems

Broadcast, referring to a process of information dissemination in a distributed system whereby a message originating from a certain node is sent to all other nodes in the system, is a very important issue in distributed computing. All-to-all broadcast means the process by which every node broadcasts its certain piece of information to all other nodes. In this paper, we first develop the optimal all-to-all broadcast scheme for the case of one-port communication, which means that each node can only send out one message in one communication step, and then, extend our results to the case of multi-port communication, i.e., k-port communication, meaning that each node can send out k messages in one communication step. We prove that the proposed schemes are optimal for the model considered in the sense that they not only require the minimal number of communication steps, but also incur the minimal number of messages     

V2V车联网中隐私保护性异构聚合签密方案

随着5G/6G移动通信技术的发展,车联网对于车辆对基础设施、车辆对车辆之间快速交换信息的要求明显提高。然而,在5G/6G网络切片技术中,不同的网络切片采用不同的密码体制,从而会形成异构网络通信。异构车联网可以实现车辆信息的即时共享,但开放的无线通信通道使车辆隐私信息易被泄露,这需要保证共享数据的机密性和完整性。提出一种隐私保护性异构聚合签密方案。该方案使用异构签密技术,在公钥基础设施和基于身份的密码系统（IBC）网络切片环境中可实现不同密码系统注册车辆之间的异构安全通信,同时采用聚合技术,在IBC环境中的车辆将接收到的密文消息进行聚合并对其解密。为确保解密后的密文消息完整,接收车辆对消息进行批量验证,以减少解签密过程所需的时间及传输量。在随机预言模型下,该方案对适应性选择密文攻击具有不可区分性,对适应性选择消息攻击具有存在性与不可伪造性。实验结果表明,相比基于边缘计算的无证书聚合签密方案与车联网高效签密方案,该方案在发送车辆对消息进行签密的阶段中所用时间减少了18.91%~63.12%,在接收车辆对密文进行解签密的阶段中所用时间减少了5.91%~33.66%,具有较高的计算效率。     

A reliable multicast protocol for distributed mobile systems:design and evaluation

Reliable multicast is a powerful communication primitive for structuring distributed programs in which multiple processes must closely cooperate together. We propose a protocol for supporting reliable multicast in a distributed system that includes mobile hosts and evaluate the performance of our proposal through simulation We consider a scenario in which mobile hosts communicate with a wired infrastructure by means of wireless technology. Our proposal provides several novel features. The sender of each multicast may select among three increasingly strong delivery ordering guarantees: FIFO, causal, total. Movements do not trigger the transmission of any message in the wired network as no notion of hand-off is used. The set of senders and receivers (group) may be dynamic. The size of data structures at mobile hosts, the size of message headers, and the number of messages in the wired network for each multicast are all independent of the number of group members. The wireless network is assumed to provide only incomplete spatial coverage and message losses could occur even within cells. Movements are not negotiated and a mobile host that leaves a cell may enter any other cell, perhaps after a potentially long disconnection. The simulation results show that the proposed protocol has good performance and good scalability properties     

一种基于信道不可靠环境的协调式检查点协议

在分布式计算环境中经常使用检查点／恢复策略来进行容错。文中主要研究在信道不可靠的环境中通过协调使相互通信的各进程所做的检查点保持全局一致性的方法。通过分析中途消息与信道可靠性之闯的关系以及已有检查点协议对于中途消息处理方法,提出了一种应用于信道不可靠环境下的协调式检查点方法,其消息复杂度为O（N）且不引入其他的计算负担,只通过一次同步即可达到全局一致性状态,相比于以往的协调式检查点协议大大减小了时间开销,提高了在不可靠信道环境中做全局一致检查点的效率。     

Distributed directory service and message routing for mobile agents

Research about networks and agents has identified the need for a layer that provides a uniform protocol to communicate with fixed and mobile agents. In order to preserve the compatibility with existing infrastructures, proposed solutions have involved a “home agent”, which forwards messages to a mobile entity. The mechanism of a home agent puts a burden on the infrastructure, which may hamper the scalability of the approach, in particular, in massively distributed systems, such as the amorphous computer or the ubiquitous/pervasive computing environment. Free from any compatibility constraint, we have designed an algorithm to route messages to mobile agents that does not require any fixed location. The algorithm has two different facets: a distributed directory service that maintains distributed information about the location of a mobile agent, and a message router that uses the directory service to deliver messages to a mobile agent. Two properties of the algorithm were established. Safety ensures that messages are delivered to the agent they were aimed at, whereas liveness guarantees that messages eventually get delivered. A mechanical proof of the properties was carried out using the proof assistant Coq.     

ADOPT-ing: unifying asynchronous distributed optimization with asynchronous backtracking

This article presents an asynchronous algorithm for solving distributed constraint optimization problems (DCOPs). The proposed technique unifies asynchronous backtracking (ABT) and asynchronous distributed optimization (ADOPT) where valued nogoods enable more flexible reasoning and more opportunities for communication, leading to an important speed-up. While feedback can be sent in ADOPT by COST messages only to one predefined predecessor, our extension allows for sending such information to any relevant agent. The concept of valued nogood is an extension by Dago and Verfaille of the concept of classic nogood that associates the list of conflicting assignments with a cost and, optionally, with a set of references to culprit constraints. DCOPs have been shown to have very elegant distributed solutions, such as ADOPT, distributed asynchronous overlay (DisAO), or DPOP. These algorithms are typically tuned to minimize the longest causal chain of messages as a measure of how the algorithms will scale for systems with remote agents (with large latency in communication). ADOPT has the property of maintaining the initial distribution of the problem. To be efficient, ADOPT needs a preprocessing step consisting of computing a Depth-First Search (DFS) tree on the constraint graph. Valued nogoods allow for automatically detecting and exploiting the best DFS tree compatible with the current ordering. To exploit such DFS trees it is now sufficient to ensure that they exist. Also, the inference rules available for valued nogoods help to exploit schemes of communication where more feedback is sent to higher priority agents. Together they result in an order of magnitude improvement.     

一个可公开验证和前向安全的签密方案

利用双线性对提出一个满足公开验证性和前向安全的基于身份的签密方案,并且能够将签名的验证和消息的恢复分别独立进行,可以应用于为移动设备过滤垃圾信息等移动电子商务场合。在BDH问题是困难的假设下用随机预言模型给出了安全性证明,经过分析比较,该方案具有很高的安全性和效率。     

基于异构消息匹配QoS全局最优E-workflow组合研究

提出了一种分布消息匹配的工作流组合方法。移动agent代理E-service,构成一个自治的感知单元,移动agent通过语义的协商确认匹配关系,E-workflow组合可以通过移动agent的演化完成。通过接口消息对应匹配的方法,完成了服务之间关系的确定,建立工作流组合的全局结构,将E-workflow的QoS全局优化转化为一个多目标的优化问题,通过基于快速排序算法改进的NSGA-II算法进行求解。通过仿真表明方法实现了分布自组织和全局适应性的功能。