Adaptive solutions to the mutual exclusion problem

Summary Algorithms for mutual exclusion that adapt to the current degree of contention are developed. Afilter and a leader election algorithm form the basic building blocks. The algorithms achieve system response times that are independent of the total number of processes and governed instead by the current degree of contention. The final algorithm achieves a constant amortized system response time. Manhoi Choy was born in 1967 in Hong Kong. He received his B.Sc. in Electrical and Electronic Engineerings from the University of Hong Kong in 1989, and his M.Sc. in Computer Science from the University of California at Santa Barbara in 1991. Currently, he is working on his Ph.D. in Computer Science at the University of California at Santa Barbara. His research interests are in the areas of parallel and distributed systems, and distributed algorithms. Ambuj K. Singh is an Assistant Professor in the Department of Computer Science at the University of California, Santa Barbara. He received a Ph.D. in Computer Science from the University of Texas at Austin in 1989, an M.S. in Computer Science from Iowa State University in 1984, and a B.Tech. from the Indian Institute of Technology at Kharagpur in 1982. His research interests are in the areas of adaptive resource allocation, concurrent program development, and distributed shared memory.A preliminary version of the paper appeared in the 12th Annual ACM Symposium on Principles of Distributed ComputingWork supported in part by NSF grants CCR-9008628 and CCR-9223094     

基于信任评估的量子区块链网络匿名选举协议

为了在量子通信网络中实现效率更高且具备信任评估功能的匿名选举协议,引入了区块链技术与节点信任评估模型。区块链技术架构具有去中心化、去信任、匿名性、防窜改等优势,节点信任评估模型在选举协议开始前完成任意两节点间的身份可信评估,使选举协议更加高效且可信。协议安全模型分析与对比结果表明,与现有协议相比该协议安全性能更好,且具有更好的匿名性、不可窜改性、可验证性等优点,在现有的技术条件下也更容易被实现。     

传感器网络中基于多级选举的非均匀簇头选择算法

为了节省和平衡网络中簇头的能耗,提出了一种基于多级选举的非均匀簇头选择算法MSEBNECHSA。该算法首先通过空间虚拟网格、簇头和Sink构成的三级选举机制构造网络候选簇头的能量分布图,然后采用基于候选簇头能量和距离的模拟退火算法,使网络中簇头的竞争范围随着到Sink的距离远近而相应从小到大非均匀分布。仿真实验表明,该算法能够以较低的能量成本将网络中的节点有效分簇,并且平衡网络中的能量消耗。     

结合简短可链接环签名的智能合约选举方案

目前一些电子选举协议利用可链接环签名或一次性环签名来保护投票者的隐私,并防止重复投票的情况发生,但签名大小随投票人数的增大而增大,而简短可链接环签名大小始终固定不变,但已有简短可链接环签名算法效率较低。针对这些问题,利用累加器和基于知识证明的签名,构造新的高效的简短可链接环签名,结合匿名地址及星际文件系统,提出一种新的智能合约选举方案,分别设计了选举的创建、投票、计票等阶段的操作。对方案的不可伪造性、可链接性、匿名性、隐私性、公开验证性以及运行效率进行了证明和分析。最后进行了实验仿真评估,结果显示,随着投票者人数的增大,该方案选票的签名大小及Gas消耗保持不变且较少,生成时间及验证时间增长缓慢且较少。     

Parameterized complexity of control problems in Maximin election

Elections are a central model in a variety of areas. This paper studies parameterized computational complexity of five control problems in the Maximin election. We obtain the following results: constructive control by adding candidates is W[2]-hard with respect to the parameter “number of added candidates”; both constructive and destructive control by adding/deleting voters are W[1]-hard with respect to the parameter “number of added/deleted voters”.     

Fault containment in weakly stabilizing systems

Research on fine tuning stabilization properties has received attention for more than a decade. This paper presents probabilistic algorithms for fault containment. We demonstrate two exercises in fault containment in a weakly stabilizing system, which expedite recovery from single failures, and confine the effect of any single fault to the constant-distance neighborhood of the faulty process. The most significant aspect of the algorithms is that the fault gap, defined as the smallest interval after which the system is ready to handle the next single fault with the same efficiency, is independent of the network size. We argue that a small fault gap increases the availability of the fault-free system.     

The election problem in asynchronous distributed systems with bounded faulty processes

Determining the “weakest” failure detectors is a central topic in solving many agreement problems such as Consensus, Non-Blocking Atomic Commit and Election in asynchronous distributed systems. So far, this has been studied extensively for several such fundamental problems. It is stated that Perfect Failure Detector P is the weakest failure detector to solve the Election problem with any number of faulty processes. In this paper, we introduce Modal failure detector M and show that to solve Election, M is the weakest failure detector to solve election when the number of faulty processes is less than ⌈n/2⌉. We also show that it is strictly weaker than P.

RBC-OLSR: Reputation-based clustering OLSR protocol for wireless ad hoc networks

We consider the problem of assuring the trustworthiness (i.e. reliability and robustness) and prolonging the lifetime of wireless ad hoc networks, using the OLSR routing protocol, in the presence of selfish nodes. Assuring the trustworthiness of these networks can be achieved by selecting the most trusted paths, while prolonging the lifetime can be achieved by (1) reducing the number of relay nodes (MPR) propagating the topology control (TC) messages and (2) considering the residual energy levels of these relay nodes in the selection process. In this paper, we propose a novel clustering algorithm and a relay node selection algorithm based on the residual energy level and connectivity index of the nodes. This hybrid model is referred to as H-OLSR. The OLSR messages are adapted to handle the cluster heads election and the MPR nodes selection algorithms. These algorithms are designed to cope with selfish nodes that are getting benefits from others without cooperating with them. Hence, we propose an incentive compatible mechanism that motivates nodes to behave truthfully during the selection and election processes. Incentive retributions increase the reputation of the nodes. Since network services are granted according to nodes’ accumulated reputation, the nodes should cooperate. Finally, based on nodes’ reputation, the most trusted forwarding paths are determined. This reputation-based hybrid model is referred to as RH-OLSR. Simulation results show that the novel H-OLSR model based on energy and connectivity can efficiently prolong the network lifetime, while the RH-OLSR model improves the trustworthiness of the network through the selection of the most trusted paths based on nodes’ reputations. These are the two different processes used to define the reputation-based clustering OLSR (RBC-OLSR) routing protocol.     

论华中抗日根据地基层政权的民主选举——以乡选为中心的考察

为从根本上改造基层政权，中国共产党领导下的华中抗日根据地广泛开展了一场轰轰烈烈的民主选举运动。根据地颁布了一系列法令、条例，使选举规范化；人民群众在实践中也充分发挥智慧创造了适合自己的选举方式。选举体现了广泛性、平等性、真实性的特点。这一运动使基层政权性质彻底改变，为争取抗战乃至整个新民主主义革命的胜利提供了重要保证。