Store Atomicity for Transactional Memory

We extend the notion of Store Atomicity [Arvind and Jan-Willem Maessen. Memory model = instruction reordering + store atomicity. In ISCA '06: Proceedings of the 33rd annual International Symposium on Computer Architecture, 2006] to a system with atomic transactional memory. This gives a fine-grained graph-based framework for defining and reasoning about transactional memory consistency. The memory model is defined in terms of thread-local Instruction Reordering axioms and Store Atomicity, which describes inter-thread communication via memory. A memory model with Store Atomicity is serializable: there is a unique global interleaving of all operations which respects the reordering rules and serializes all the operations in a transaction together. We extend Store Atomicity to capture this ordering requirement by requiring dependencies which cross a transaction boundary to point in to the initiating instruction or out from the committing instruction. We sketch a weaker definition of transactional serialization which accounts for the ability to interleave transactional operations which touch disjoint memory. We give a procedure for enumerating the behaviors of a transactional program—noting that a safe enumeration procedure permits only one transaction to read from memory at a time. We show that more realistic models of transactional execution require speculative execution. We define the conditions under which speculation must be rolled back, and give criteria to identify which instructions must be rolled back in these cases.     

基于持久性内存的单向移动B^+树

由新型非易失存储介质构成的持久性内存(persistent memory,PM)具有扩展性强、按字节访问与静态能耗低等特性,为未来主存与辅存融合提供了强大的契机.然而由于LLC(last level cache)具有易失性且与主存交互粒度通常为64B,而PM的原子持久化操作粒度为8B.因此,数据从LLC更新到PM的过程中,若发生故障,则可能破坏更新操作的失败原子性,进而影响原始数据的完整性.为了保证更新操作的失败原子性,目前研究主要采用显式调用持久化指令与内存屏障指令,将数据有序地持久化到PM上,但该操作会造成显著的开销,在索引更新中尤为明显.在对索引进行更新时,往往会涉及到索引结构的变化,该变化需要大量的有序持久化开销.研究旨在减少基于PM的B+树在更新过程中为保证失败原子性而引入的持久化开销.通过分析B+树节点利用率、不同更新模式下持久化开销以及更新操作之间的关系,提出了一种基于节点内数据真实分布的数据单向移动算法.通过原地删除的方式,减少删除带来的持久化开销.利用删除操作在节点内留下的空位,减少后续插入操作造成的数据移动,进而减少数据持久化开销.基于上述算法,对B+树的重均衡操作进行优化.最后通过实验证明,相较于最新基于PM的B+树,提出的单向移动B+树能够显著提高单一负载与混合负载性能.     

满足原子性和公平匿名性的AFAP协议研究

在分析电子交易的原子性和公平匿名性基础上,应用两阶段提交协议思想,实现了电子交易的原子性,改进了Brands教授提出的公平盲签名协议,不仅实现了交易中的匿名性,还提供了非法支付的所有者追踪和货币追踪,实现了公平匿名性,并提出了一个可同时实现原子的公平匿名的电子交易协议,给出了协议的五个子协议,详细描述了各子协议的执行过程,并非形式化地证明了协议原子性和公平匿名性,保证了公平电子交易和私密性。     

安全支付协议的设计与验证研究

安全支付协议是实现电子商务在线支付的关键。目前缺乏同时支持电子商品和实物商品的在线支付协议,基于此,该文给出了一种同时支持这两类商品交易的安全支付协议,最后使用SMV工具对协议的原子性进行了分析并验证了其可行性。     

A space- and time-efficient local-spin spin lock

A simple code transformation is presented that reduces the space complexity of Yang and Anderson's local-spin mutual exclusion algorithm. In both the original and the transformed algorithm, only atomic read and write instructions are used; each process generates Θ(logN) remote memory references per lock request, where N is the number of processes. The transformed algorithm uses Θ(N) distinct variables, which is clearly optimal.     

纳米级叶蜡石结构参数的表征

阐述了叶蜡石纳米化的必要性,并从晶体化学和晶体结构的角度,根据叶蜡石的晶胞参数、晶胞内原子排列的特点等,提出了叶蜡石最小颗粒的假设,从理论上得出叶蜡石最佳的纳米尺度.同时通过对叶蜡石颗粒的晶胞数、原子数、表面晶胞数以及平行(001)面的表面原子数的计算,列出了叶蜡石纳米结构参数的表征,讨论了它们与纳米级叶蜡石颗粒尺度大小的相关规律,并结合纳米微粒的特征对其进行了简要的分析.     

Self-stabilization with r-operators

This paper describes a parameterized distributed algorithm applicable to any directed graph topology. The function parameter of our algorithm is instantiated to produce distributed algorithms for both fundamental and high level applications, such as shortest path calculus and depth-first-search tree construction. Due to fault resilience properties of our algorithm, the resulting protocols are self-stabilizing at no additional cost. Self-stabilizing protocols can resist transient failures and guarantee system recovery in a finite time. Since the condition on the function parameter (being a strictly idempotent r-operator) permits a broad range of applications to be implemented, the solution presented in our paper can be useful for a large class of distributed systems. Received: August 1999 / Accepted: January 2001     

Atomic and anonymous e-Cash transaction protocol with off-line TTP

Atomicity and anonymity are desirable properties for reliable and security e-Cash transaction and the guarantee of the participants‘ interests. But there are cotdlicts between these two properties. In this paper, an atomic and anonymous e-Cash transaction protocol with off-line TTP (Trust Third Party) based on the extended CEMBS is presented. The novel protocol is analyzed for its atomicity and anonymity. The results of the analysis show that it not only provides atomicity and anonymity under unreliable communication and dishonest participants, but also features high efficiency and practicability. The new protocol also avoids transaction from an ambiguous state. Furthermore, it will be referenced often for the application of the atomic e-Cash transaction protocol.