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     

几种航空有源电子干扰装备的比较

本文对远距离支援干扰飞机、随队支援干扰飞机、机载自卫电子对抗系统以及最近国外正在大力发展的分布式电子干扰系统等几种航空有源电子干扰装备的作战对象、战术应用、功能、使用局限性等特点进行了比较 ,探讨了综合发展和运用这几型装备的重要意义     

Distributed election in complete networks

An improved version of Afek and Gafni's synchronous algorithm for distributed election in complete networks is given and anO(n) expected message complexity is shown. M.Y. Chan received her Ph.D. in 1988 from the University of Hong Kong, and her M.S. and B.A. degrees in computer science from the University of California, San Diego in 1980 and 1981, respectively. She is currently an Assistant Professor at the University of Texas at Dallas. Francis Y.L. Chin (S71-M76-SM85) received the B.Sc. degree in engineering science from the University of Toronto, Toronto, Canada, in 1972, and the M.S., M.A., and Ph.D. degrees in electrical engineering and computer science from Princeton University, New Jersey, in 1974, 1975, and 1976, respectively. Since 1975, he has taught at the University of Maryland, Baltimore Country, University of California, San Diego, University of Alberta, and Chinese University of Hong Kong. He is currently Head of the Department of Computer Science, University of Hong Kong. He has served as a program co-chairman of the 1988 International Conference on Computer Processing of Chinese and Oriental Languages (Toronto) and the International Computer Science Conference '88 (Hong Kong). His current research interests include algorithm design and analysis, parallel and distributed computing.     

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

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

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

为了节省和平衡网络中簇头的能耗,提出了一种基于多级选举的非均匀簇头选择算法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.