Safety,liveness and fairness in temporal logic

In this paper we present syntactic characterization of temporal formulas that express various properties of interest in the verification of concurrent programs. Such a characterization helps us in choosing the right techniques for proving correctness with respect to these properties. The properties that we consider include safety properties, liveness properties and fairness properties. We also present algorithms for checking if a given temporal formula expresses any of these properties.This work is partly supported by NSF grant CCR-9212183. A preliminary version of this paper appeared in the Fourth ACM Symposium on Principles of Distributed Computing.     

基于博弈论的百万富翁协议

在经典的百万富翁协议中,一方在得到最后的财富比较结果后,没有动机将结果告诉另一方,或者告诉另一方一个错误的结果。结合博弈论和密码算法,提出一种百万富翁协议。在此协议中,参与者背离协议的收益小于遵守协议的收益,遵守协议是参与者的最优策略,任何百万富翁的欺骗行为都能被鉴别和发现,因此理性的参与者有动机发送正确的数据。最后每个参与者都能公平地得到最后的财富比较结果。     

On-Line Multi-Threaded Paging

Abstract. In this paper we introduce a generalization of Paging to the case where there are many threads of requests. This models situations in which the requests come from more than one independent source. Hence, apart from deciding how to serve a request, at each stage it is necessary to decide which request to serve among several possibilities. Four different on-line problems arise depending on whether we consider fairness restrictions or not, with finite or infinite input sequences. We study all of them, proving lower and upper bounds for the competitiveness of on-line algorithms. The main competitiveness results presented in this paper state that when no fairness restrictions are imposed it is possible to obtain competitive algorithms for finite and infinite inputs. On the other hand, for the fair case in general there exist no competitive algorithms. In addition, we consider three definitions of competitiveness for infinite inputs. One of them forces algorithms to behave efficiently at every finite stage, while the other two aim at comparing the algorithms' steady-state performances. A priori, the three definitions seem different. We study them and find, however, that they are essentially equivalent. This suggests that the competitiveness results that we obtain reflect the intrinsic difficulty of the problem and are not a consequence of a too strict definition of competitiveness.     

Open source content contributors’ response to free-riding: The effect of personality and context

We address concerns about the sustainability of the open source content model by examining the effect of external appropriation, whereby the product of open source contributors’ efforts is monetized by a party that did not contribute to the project, on intended effort withdrawal (reduction in contribution level). We examine both the personality of contributors and their contextual motivations to contribute, using a scenario-based survey of Wikipedia contributors. The findings suggest that perceived justice of the open source license terms, and intrinsic motivations are both negatively related with effort withdrawal intentions. Moreover, we find that the effect of the fairness personality trait on effort withdrawal is stronger for individuals who are low in perceived justice and weaker for individuals high in justice. The findings of factors predicting effort withdrawal contribute to the open source literature, which tends to focus on contribution and motivations, but not on what impacts changes in individual contribution levels.     

对一种公平非否认协议的新改进

Zhou-Gollmann协议是一种公平非否认协议,近年来得到广泛讨论.Kim发现该协议在时限公平性方面存在缺陷,针对该缺陷提出一种改进的协议,但其改进方法高度依赖于网络时钟的同步.通过详细分析,发现在缺乏时钟同步时Kim的改进协议也可导致不公平.针对此问题,提出一种新的改进方案.新的改进消除了协议对时钟同步的依赖性,保持了协议的公平非否认性,且不会降低协议的效率.     

基于流的 AD Hoc 网络接入公平性分析与研究

在 Ad Hoc 网络中,系统的不公平性会严重影响服务质量.针对该问题,提出一种以流为单位、用 WFQ 机制进行本地信息调度、采用交换节点信息调节退避时间的协调算法--FBFA.该算法计算节点每条流的服务指数,与邻节点进行交换,结合节点本身的信息和邻居节点的信息确定退避时间,提高系统的公平性.实验结果表明,FBFA 算...     

基于公平性的多银行电子现金

随着电子商务的发展,电子支付系统逐渐发展起来。而现有多数的电子现金不能在多家金融机构中流通,并且电子现金的数额在发放时就被固定了,交易时只能在本系统中使用。利用椭圆曲线密钥机制,基于Song-Korba的电子现金框架基础,提出一种由某一权威的金融机构(如中央银行)统一发行,可在多家银行中流通的电子现金体系。对Song-Korba框架做了一些改进,使电子现金交易后的体积不变,可实现余额的合并,安全性更高的电子现金机制。     

一种基于智能卡的匿名公平移动支付系统

提出了一种基于智能卡的匿名公平移动支付系统模型,基于该模型提出了一个可追踪匿名的脱线式数字现金协议,它使用智能卡作为分布匿名代理,实现了数字现金的动态匿名和兑零的功能;证明了匿名数字现金满足安全性和可追踪匿名性,该协议的效率高于基于盲签名和匿名代理服务器技术的协议.提出了一个关于时间敏感商品的公平移动支付方案,即使用智...     

主动网络中CPU和带宽资源分配的公平性

传统的包调度方案能实现单一资源分配的公平性,但不能直接应用于主动网络中的主动节点上,因为主动节点包含多种相互关联的资源。提出一种能实现在主动节点中公平分配资源的包调度算法。仿真实验结果显示,该算法能在主动流之间实现CPU和带宽资源的有效公平分配。