Message fragment based causal message logging

In a distributed computing system, message logging is widely used for providing nodes with recoverability. To reduce the piggyback overhead of traditional causal message logging, we present a zoning causal message logging approach in this paper. The crux of the approach is to control the propagation of dependency information: the nodes in the system are divided into zones, and by a message fragment mechanism, the dependency information of a node is only visible in the zone scope. Simulation results show that the piggyback overhead of the proposed approach is lower than that of traditional causal message logging.     

Causality tracking in causal message-logging protocols

Casual message-logging protocols have several attractive properties: they introduce no blocking, send no additional messages over those sent by the application, and never create orphans. Causal message logging, however, does require the casual effects of the deliveries of messages to be tracked. The information concerning causality tracking is piggybacked on application messages, and the amount of such information can become large. In this paper we study the cost of tracking causality in causal message-logging protocols. One can track causality as accurately as possible, but to do so requires piggybacking a considerable amount of additional information. One can reduce the amount of piggybacked information on each message by reducing the accuracy of causality tracking. But then, causal message logging may piggyback the reduced amount of information on more messages. We specify six different methods of tracking causality, each representing a natural choice based on the specification of causal message logging. We describe how these six methods can be implemented and compare them in terms of how large of a piggyback load they impose. This load depends on the application that is using causal message logging. We characterize some applications for which a given method has the smallest piggyback load, and study using simulation the size of the piggyback load for two different models of applications. Received: July 1999 / Accepted: July 2001     

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     

An Adaptive Causal Ordering Algorithm Suited to Mobile Computing Environments

Causal message ordering is required for several distributed applications. In order to preserve causal ordering, only direct dependency information between messages, with respect to the destination process(es), need be sent with each message. By eliminating other kinds of control information from the messages, the communication overheads can be significantly reduced. In this paper we present an algorithm that uses this knowledge to efficiently enforce causal ordering of messages. The proposed algorithm does not require any prior knowledge of the network topology or communication pattern. As computation proceeds, it acquires knowledge of the communication pattern and is capable of handling dynamically changing multicast communication groups, and minimizing the communication overheads. With regard to communication overheads, the algorithm is optimal for the broadcast communication case. Extensive simulation experiments demonstrate that the algorithm imposes lower communication overheads than previous causal ordering algorithms. The algorithm can be employed in a variety of distributed computing environments. Its energy efficiency and low bandwidth requirement make it especially suitable for mobile computing systems. We show how to employ the algorithm for causally ordered multicasting of messages in mobile computing environments.     

Active optimistic and distributed message logging for message‐passing applications

Message logging is an attractive solution to provide fault tolerance for message‐passing applications because it is more scalable than coordinated checkpointing. Sender‐based message logging is a well‐known optimization that allows the saving of message payload in the sender memory. Thus, only message reception events have to be logged reliably by using an event logger. This paper proposes solutions to further improve message logging protocol scalability. In existing works on message logging, the event logger has always been considered as a centralized process. We propose a distributed event logger that takes advantage of multi‐core processors that are to be executed in parallel with application processes, leveraging the volatile memory of the nodes to save events reliably. We also propose the combination of our distributed event logger and O2P, an active optimistic message logging protocol using a gossip‐based protocol to disseminate information on new stable events. Our distributed event logger and O2P are implemented in the Open MPI library. Our results show the following: (i) distributed event logging improves message logging protocol scalability and (ii) using O2P with a distributed event logger provides an efficient and scalable fault‐tolerant solution for message‐passing applications. Copyright © 2011 John Wiley & Sons, Ltd.     

基于并发性发掘的低开销回卷恢复实现方法

现有的回卷恢复容错技术存在同步约束和阻塞问题,其时间开销随系统节点规模的增大而剧增。为此,提出一种基于并发性发掘的低开销回卷恢复实现方法。利用消息传递附带跟踪消息依赖的策略解除消息日志中的同步约束,解析进程负载以发掘进程负载的并发性,构建进程负载并发执行的实现架构,采用数据缓存策略和多线程技术实现进程内部各负载的并发执行,以降低故障恢复开销。3个NASNPB2．3标准性能检测程序的实验结果表明,该方法可使检查点开销从0．63S、3．19S、1．21S分别降低到0．18S、O．67S、0．19S,日志开销率从13．4％、3．5％、18．3％分别降低到0．7％、0．1％、1．0％。     

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

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

消息联盟系统中保持消息因果序协议的研究

由多个代理服务器组成的消息中间件联盟系统提供了更好的扩展性，但没有保证消息之间的因果序关系。该文提出并设计了一个新的保证消息因果序的通信协议MOMCO，该协议基于向量时钟，不但保证在消息联盟系统中消息的因果序，而且携带的排序控制信息量小，避免了采用二维矩阵时钟导致的较高代价，适用于大规模应用的场合。     

基于图表示学习的消息回复关系判断方法

微信、QQ和钉钉等社交媒体都提供多对多聊天群组功能,这些聊天群组包含海量信息,对群组聊天内容进行有效分析,获取有价值的关联信息,是当前领域的研究热点。群组中用户间交互是群组实现的主要功能,用户间消息回复是用户间交互实现的方式,消息间的回复行为下隐藏着消息间和用户间的关系。群组消息间回复通常是隐式和非连续的,大部分群组消息间没有指定明确的回复关系,当前消息也不一定是上一条临近消息的回复,回复关系要根据具体的聊天场景确定。当消息间没有显示指定回复关系时,回复不易于分析和理解群组聊天内容,阻碍了对群组聊天内容的整体性分析。本论文针对群组消息间的回复关系,提出了基于图表示学习的消息回复关系判断方法,该方法不同于以往方法仅使用部分群组要素,是在综合学习消息的文本信息、发送消息的用户信息和上下文信息的基础上,根据群组内容构建群组图和生成自适应消息图,得到了多种群组要素信息和要素间关系组成的图结构,利用图模型在图结构上进行群组消息的表示学习,图模型输出群组消息的表示向量,拼接消息对的表示向量并进一步预测群组消息间的回复关系。在消息间回复关系的学习过程中,图模型通过任务学习更新图中消息节点,同时更新图中用户节点向量表示,经过用户向量分析实验验证了该模型输出的用户向量的有效性和合理性。在公开数据集和标注数据集上进行了对比实验和显著性检验分析,结果显示模型在多个评估指标上大幅优于对比模型,如在F1指标上,比单纯依赖BERT的句子对分类模型提高了接近20%。     

消息日志方法中的不确定性问题

消息日志是用于多进程、分布式系统中状态恢复的一种方法。本文针对传统的消息日志方法仅仅适用于确定性进程的局限性，提出一种新的消息日志思想，充分考虑到不确定性的存在在容错方面的积极作用，主张在满足应用进程一致性语义的基础上，在一定程度上允许不确定性现象的存在。从而以新的角度看待单一进程和分布式并发系统中存在的不确定性所带来的状态重建不能完全复原的问题。这样，消息日志亦能适用于某些不满足确定性条件的进程     

Proposal and evaluation of dynamic assignment of priorities in CAN

The paper deals with the scheduling of information flow in a CAN ISO IS-11898 communication system. It mainly features a bus access arbitration protocol based on a priority assigned to each message to be transmitted; if two or more messages are transmitted at the same time by different communication nodes, only the message with the highest priority continues to be transmitted, the other being stopped. In real-time applications, messages contain information which must be transmitted within strict time constraints; according to the CAN ISO IS-11898 bus arbitration protocol, respect of real-time constraints of time critical information depends on the priority assigned to the message conveying it. The aim of the paper is to propose a procedure for dynamic assignment of priorities to messages to be transmitted, in such a way the real-time requirements of the information conveyed are fulfillled. Although many other approaches can be found in literature, the proposal is original as It is based on standard full CAN communication stacks.     

An Algorithm for Finding the Causal Distributed Breakpoint

Acausal distributed breakpointis one of the fundamental mechanisms for debugging distributed programs. It is initiated by a sequential breakpoint in one process of a distributed computation, and restores each process to theearlieststate that reflects all events that happened causally before the sequential breakpoint. This paper presents an algorithm for finding the causal distributed breakpoint when a sequential breakpoint occurs. To find the causal distributed breakpoint efficiently, some information about dependency of events is piggybacked in every message and is logged at each process. The algorithm requiresO(1) information in each message and finds the causal distributed breakpoint inO(nlogn+m) time, wherendenotes the number of processes andmdenotes the number of distinct pairs of processes directly communicating with each other.     

A traffic-efficient message forwarding approach in unstructured P2P networks

With more and more peer-to-peer (P2P) applications being utilized, the P2P traffic accounts for the majority in Internet, and thus leading to the network congestion problem. Reducing the redundant propagations of messages is an effective approach for solving such problem in unstructured P2P networks. In this paper, we first define a novel message structure which contains the information of message propagation path, and then three operations, including the inheritance, supplement and collection, on the message transmission paths are proposed, based on which a node could forward the message to the nodes who have not received the message yet purposefully by using the information of the past received messages and the characteristics of space and time of node activities, and thus eliminating the bandwidth consumption problem caused by the flooding-based message propagation approaches. The simulation results show that our strategy could effectively reduce the number of the redundant messages without lowering the message coverage ratio.     

层次式体系结构下一种似然时标系统

当前,分布式系统具有越来越大的规模,而且可能层次地分布在广域网上,这些属性增加了保证分布式系统中时序关系的难度.向量时钟可以准确地探测事件间的时序关系,但是向量时钟的维度与节点数相同,就引起了效率和可扩展性问题.该文提出了层次体系结构下确定分布式系统时序关系的一种优化解决方案.首先给出了分布式系统的一种层次式体系结构,其中独立的子组通过代理进程互连,组成集群完成特定目标;在这种结构中,采用"分而治之"的策略,提出了一种似然时标系统,其特点是消息传输时的时间标签仅仅是系统时标的一部分.该时标系统能够探测大规模分布式系统中消息间的因果关系,而且具有较好的效率和可扩展性.     

Distributed recovery with K-optimistic logging

Fault-tolerance techniques based on checkpointing and message logging have been increasingly used in real-world applications to reduce service down-time. Most industrial applications have chosen pessimistic logging because it allows fast and localized recovery. The price that they must pay, however, is the high failure-free overhead. In this paper, we introduce the concept of K-optimistic logging where K is the degree of optimism that can be used to fine-tune the trade-off between failure-free overhead and recovery efficiency. Traditional pessimistic logging and optimistic logging then become the two extremes in the entire spectrum spanned by K-optimistic logging. Our results generalize several previously known protocols.Our approach is to prove that only dependencies on those states that may be lost upon a failure need to be tracked on-line, and so transitive dependency tracking can be performed with a variable-size vector. The size of the vector piggy-backed on a message then indicates the number of processes whose failures may revoke the message, and K corresponds to the upper bound on the vector size. Furthermore, the parameter K is dynamically tunable in response to changing system characteristics.     

机会网络自私节点的Bertrand博弈与激励机制研究

在真实的网络环境中,很多节点可能是自私的,它们不愿意牺牲自己的资源为其他节点转发消息。针对这种情况,提出一种基于博弈论的激励机制,可以激励节点与其他节点相互合作。该机制为二阶段激励,激励节点接收消息以协助其他节点转发,同时激励节点转发更多的消息。把源节点与中继节点之间的竞争与合作模型化为Bertrand（伯特兰德）博弈,定义了源节点和中继节点的效用函数。求解了源节点的最佳定价策略和中继节点最佳的转发计划,验证了源节点与中继节点之间存在唯一的纳什均衡。模拟仿真结果表明提出的激励机制能够鼓励自私节点参与合作,能提高路由算法的传递率,同时降低了消息传递延迟。与基于声誉的激励机制相比,所提激励机制能使消息传递成功率提高31.4%、平均时延降低9.7%。     

基于大功率消息广播的DTMSN路由机制

提出一种基于基站大功率信号广播的延迟容忍移动传感器网络消息路由机制(High-power Broadcasting based Routing scheme,HBR)。该机制使用两个通信频率f₁ 和f₂,基站以恒定大功率在频率f₁上广播已经接收到的消息,网络中传感器节点根据基站广播信息计算自身转发概率并清理冗余消息副本,节点间利用频率f₂进行通信。为进一步提升网络性能,HBR优先传输转发阈值(M)小且生存时间短的消息,并合理进行消息队列管理。仿真结果表明,与几种经典的路由机制相比,HBR在消息传输成功率、传输延迟方面有着一定的优势。     

P2P内容搜索的信息相似值计算方法

随着P2P网络的迅速发展,其用户数量不断增加,信息交互也越发频繁。为了降低内容搜索的复杂度和搜索时间,提出了一种以信息相似值为依据的计算方法。这种计算方法将无规则P2P网络中的节点按照节点的信息相似值划分为不同的域。在信息搜索时,将搜索的关键字与域头节点信息向量进行匹配,算法将整网搜索转化成域内或相邻域搜索,并根据用户兴趣值返回搜索结果。实验证明,这种信息相似值的计算方法在降低搜索时间的基础上,有较高的搜索命中率和查询准确率。     

A social-aware routing protocol for opportunistic networks

Understanding nodes mobility is of fundamental importance for data delivery in opportunistic and intermittently connected networks referred to as Delay Tolerant Networks (DTNs). The analysis of such mobility patterns and the understanding of how mobile nodes interact play a critical role when designing new routing protocols for DTNs. The Cultural Greedy Ant (CGrAnt) protocol is a hybrid Swarm Intelligence-based approach designed to address the routing problem in such dynamic and complex environment. CGrAnt is based on: (1) Cultural Algorithms (CA) and Ant Colony Optimization (ACO) and (2) operational metrics that characterize the opportunistic social connectivity between wireless users. The most promising message forwarders are selected via a greedy transition rule based mainly on local information captured from the DTN environment. Whenever global information is available, it can also be used to support decisions. We compare the performance of CGrAnt with Epidemic, PROPHET, and dLife protocols in two different mobility scenarios under varying networking parameters. Results obtained by the ONE simulator show that CGrAnt achieves a higher message delivery and lower message redundancy than the three protocols in both scenarios. The only exception is in one of the scenarios, when messages have a time to live lower than 900 min, where CGrAnt delivers a bit less messages than dLife, although with a lower message redundancy.     

Logical clock requirements for reverse engineering scenarios from adistributed system

To reverse engineer scenarios from event traces, one must infer causal relationships between events. The inferences are usually based on a trace with sequence numbers or timestamps corresponding to some kind of logical clock. In practice, there is an explosion of potentially causal relationships in the trace, which limits one's ability to extract scenarios. This work defines a more parsimonious form of causality called scenario causality that concentrates on certain major causal relationships and ignores more subtle, potentially causal links. The influence of an event is restricted to the particular scenario it is part of. An event which is not a message reception is defined to be caused by the previous event in the same software object, while a message reception is caused by a sending event in another object. The events are ordered to form a scenario event graph where typed nodes are events and the typed edges are certain causal relationships. Intuitively, we might say that most logical clocks, which identify events which "happened before" a given event and, thus, are potentially causal, give an upper bound on the set of causal events; scenario causality identifies a lower bound. The much smaller lower bound set makes it possible to reverse engineer and automate the analysis of scenarios