(n1,n2,…,nk)型k重(r1,r2,…,rk)-循环矩阵求逆的快速算法

本文给出了(n1，n2，…，nk)型k重(r1，r2，…，rk)-循环矩阵求逆的快速算法，其计算复杂性为O[(Ⅱ↑ki=1ni)logsⅡ↑ki=1ni]。     

多输出弹性k-旋转对称布尔函数的存在性与构造

多输出布尔函数可由多个单输出布尔函数表示,在分组密码中有着广泛的应用.多输出k-旋转对称布尔函数(k-RSBF)是多输出旋转对称布尔函数(RSBF)的扩展.本文首先研究多输出旋转对称函数和多输出k-旋转对称函数的轨道分布情况,给出了计算两类函数中长度相同轨道个数的方法.其次研究了平衡多输出k-旋转对称布尔函数的存在性,给出了在选择合适的k的前提下,n=pr、n=2pr和n=2r时,平衡(n,m)k-RSBF的构造方法.之后研究弹性多输出k-旋转对称布尔函数的存在性,分别给出了r≥3,n=2r,2≤m≤2r-r,k=2时1阶弹性(n,m)k-RSBF的构造方法,以及p为奇素数,r≥2,n=pr,2≤m≤p-1,k=p时1阶弹性(n,m)k-RSBF的构造方法.最后我们还对两种方法得到的1阶弹性多输出k-旋转对称布尔函数进行仿真测试.     

输出反馈极点配置的一种新方法

有关文献已证明,完全可控可观系统(ABC)通过定常输出反馈K,至少可配置max(m,r) 以及几乎总可以配置min(n,m+r-1)个极点任意接近事先指定的对称分布值,并给出了 配置的方法--并矢法.本文给出了输出反馈系统配置max(m,r)和min(n,m+r-1)个 互异不属于σ(A)的极点的非并矢方法,并矢法是其特殊情况.此方法也适用于状态反馈系统 及带动态补偿器输出反馈系统的极点配置.     

SLS算法求解平衡正则(k,2r)-CNF公式

可满足性问题的求解算法和结构性质研究是计算机科学中重要问题之一，为寻求某些CNF公式子类问题有效算法或算法改进途径，对公式的结构加以某些限制，其中限定子句长度为恒定常数和变元出现次数是常见的处理方式。研究具有正则结构且每个变元正负出现均衡的结构化公式的可满足性问题求解，其随机生成模型的构建及随机实验测试有助于观察解分布状况。并且，随机局部搜索算法在求解具有一定规则结构CNF公式实例中具有良好效率。本文集中研究平衡正则(k, 2r)-CNF公式的求解问题，即限制每个子句的长度为k，每个变元出现的次数为偶数2r,并且每个变元正负出现的次数在相等情况下的可满足性问题求解。给出BR(n,  k, 2r)模型，以此模型来生成具有特殊结构的平衡正则(k, 2r)-CNF公式实例，利用随机局部搜索算法求解问题。通过限制初始指派的0文字和1文字各占一半且均匀生成，以WalkSAT算法和NSAT算法做实验对比，发现对于平衡正则(k, 2r)-CNF公式，实例具有明显效率。     

面向内存表的可动态配置预写日志框架

通常情况下,NoSQL数据库管理系统启动后,其多个数据库或数据分区的预写日志（WAL）会固定地写入一个或多个日志文件,因而形成强耦合的对应关系。由于数据库逻辑模型与分区配置是由应用业务和计算环境所决定的,在预写日志被强耦合的情况下,数据库管理系统无法对预写日志的个数、大小等进行配置以实现性能调优。针对该问题,提出了一种面向内存表的可动态配置预写日志框架,该框架记录了重写日志,内存表可以动态地被分配给不同的预写日志队列,支持可变的对应关系,实现了预写日志与具体应用之间的解耦。在物联网时序数据库Apache IoTDB上实现了该框架,并进行了相关实验,结果表明使用可动态配置预写日志框架后可以找到比强耦合的预写日志更优的配置方案,写入性能可提高8%～19%,说明该框架能针对不同计算环境和应用负载实现动态性能调优。     

基于IP网络规划与设计的抖动模型的研究

提出了一个典型的模型,该模型考虑到包延时的相关性和串联队列的相关性,这对端到端的抖动有重要影响。针对一个单队列的Poisson流量分布的抖动,给出了一个非常易于计算的公式,然后推广到基于串联队列的标记流的端到端抖动。通过模拟实验可以发现,模型的分析值和模拟值基本吻合,在大流量背景下更为精确,更重要的是对于抖动而言该值是可信的,这样就可以用于网络设计过程中。     

Facebook Cassandra架构和设计的可信性研究

文章简要介绍了Cassandra分布存储系统的设计理念及其使用的各种分布存储技术。文章首先分析了Cassandra分布存储系统出现的缘由——Facebook社交网络的系统需求,然后着重介绍了Cassandra系统中区别传统关系型数据库的数据结构,最后文章对Cassandra系统进行了可信分析,还叙述了Cassandra的优缺点。     

B样条曲线节点插入和升阶的统一方法

利用 B样条基转换矩阵的有关结果 ,本文给出了 B样条曲线插入节点和升阶的统一方法及算法 .本文方法建立在严密的数学背景上 ,以简洁严谨的递推公式给出其算法的数学模型 ,相应的算法效率高且易实现 ,算法的时间复杂性为 O((k- k 1) kn) ,其中 k,k分别为升阶前后曲线的阶 ,n k 1为插入节点和升阶后的节点数 .而且 ,本文方法及算法使用灵活 ,适用范围广 ,可用于同时插入任意个相同的或不同的节点并升任意阶 ,也可用于只插入节点或只升阶 .Cohen等的 Oslo算法、升阶方法都是本文方法的特例 ,而且本文方法效率更高     

一种新的广义(k,n)门限秘密共享方案*

基于离散对数的安全性和(k,n)门限方案给出了一种新的k-(k1,n1;k2,n2;...;kt,nt)门限方案.在该方案中,各参与者的子秘密自己选取,甚至连秘密分发者也不知道.秘密恢复过程中,各参与者能够验证其他参与者是否进行了欺骗.每个参与者只需要维护一个子秘密,就可以实现对多个秘密的共享.     

GF(2k)上的遍历矩阵及其特性分析

对有限域GF(2k)上的"遍历矩阵"进行了探讨.通过本文的分析,可以发现GF(2k)上的遍历矩阵具有很多可应用于密码学的良好特性.为了寻找所需的遍历矩阵,我们引入了GF(2k)中的一个递推公式,并基于此给出了一个寻找算法.通过该算法可以有效地找到GF(2k)上特定数目的n阶遍历矩阵,且每一个n阶遍历矩阵均可用GF(2k)上的一个n维向量来表示,因此可大大节省存储和传输相应矩阵所需的空间及带宽.     

MDICA: Maintenance of data integrity in column-oriented database applications

Current information technologies generate large amounts of data for management or further analysis, storing it in NoSQL databases which provide horizontal scaling and high performance, supporting many read/write operations per second. NoSQL column-oriented databases, such as Cassandra and HBase, are usually modelled following a query-driven approach, resulting in denormalized databases where the same data can be repeated in several tables. Therefore, maintaining data integrity relies on client applications to ensure that, for data changes that occur, the affected tables will be appropriately updated. We devise a method called MDICA that, given a data insertion at a conceptual level, determines the required actions to maintain database integrity in column-oriented databases. This method is implemented for Cassandra database applications. MDICA is based on the definition of (1) rules to determine the tables that will be impacted by the insertion, (2) procedures to generate the statements to ensure data integrity and (3) messages to warn the user about errors or potential problems. This method helps developers in two ways: generating the statements needed to maintain data integrity and producing messages to avoid problems such as loss of information, redundant repeated data or gaps of information in tables.     

Performance evaluation of the time-stamp ordering algorithm in adistributed database

Time-stamp ordering is one of the consistency preserving algorithms that is used in distributed databases. F. Baccelli (1987) has introduced a queueing model that incorporates the fork-join and resequencing synchronization constraints to analyze the algorithm's performance. The power of interpolation approximation technique is illustrated by obtaining extremely good approximations for this rather complex model. The heavy traffic approximations are obtained by showing that this model has the same diffusion limit as a system of parallel fork-join queues. The light traffic limits are obtained by applying the light traffic theory developed by M.I. Reiman and B. Simon (1989). The heavy traffic limits are computed for general arrival and service distributions, but the light traffic limits are restricted to Markovian systems     

基于Cassandra的可扩展分布式反向索引的构建

随着云计算时代的到来,大型Web应用的不断发展,海量数据不断增加,集中式的数据检索已不再满足需求.如何在分布式的环境中高效地处理数据检索成为亟待解决的问题.传统的关系型数据存储也无法完全适应云环境,NoSQL(Not only SQL)作为一种云存储形式应运而生,其中Cassandra的应用较为广泛.以分布式的多节点架...     

A novel clustered MongoDB-based storage system for unstructured data with high availability

More and more unstructured data are produced and consumed over network. How to maintain these data and improve the availability and scalability of the storage systems has become a considerable challenge. Although some NoSQL systems such as Dynamo, Cassandra, MongoDB have provided different advantages for unstructured data management, no one can provide flexible query functions like MongoDB, meanwhile guarantee the availability and scalability as Cassandra simultaneously. This paper presents a new high available distributed storage system called MyStore based on an optimized clustered MongoDB for unstructured data. Consistent hash is used to distribute data on multiple MongoDB nodes by applying virtual node method. NWR mode is applied to provide automatic backup operation and guarantee data consistency. And a gossip protocol is taken for exchanging information of failures in the system. Moreover, a user-friendly interface module and an efficient cache module are designed for improving the usability of the system. Based on above strategies, the system can realize high availability for unstructured data storage, while providing complex query functions like rational databases. Moreover, it is applied in a multi-discipline virtual experiment platform named VeePalms that has run practically. Experimental evaluation shows that the methodology is powerful enough not only to enhance the data availability, but also to improve the server’s scalability.     

A partitioning framework for Cassandra NoSQL database using Rendezvous hashing

Due to the gradual expansion in data volume used in social networks and cloud computing, the term “Big data” has appeared with its challenges to store the immense datasets. Many tools and algorithms appeared to handle the challenges of storing big data. NoSQL databases, such as Cassandra and MongoDB, are designed with a novel data management system that can handle and process huge volumes of data. Partitioning data in NoSQL databases is considered one of the critical challenges in database design. In this paper, a MapReduce Rendezvous Hashing-Based Virtual Hierarchies (MR-RHVH) framework is proposed for scalable partitioning of Cassandra NoSQL database. The MapReduce framework is used to implement MR-RHVH on Cassandra to enhance its performance in highly distributed environments. MR-RHVH distributes the nodes to rendezvous regions based on a proposed Adopted Virtual Hierarchies strategy. Each region is responsible for a set of nodes. In addition, a proposed bloom filter evaluator is used to ensure the accurate allocation of keys to nodes in each region. Moreover, a number of experiments were performed to evaluate the performance of MR-RHVH framework, using YCSB for database benchmarking. The results show high scalability rate and less time consuming for MR-RHVH framework over different recent systems.     

Pinpointing and scheduling access conflicts to improve internal resource utilization in solid-state drives

Modern solid-state drives (SSDs) are integrating more internal resources to achieve higher capacity. Parallelizing accesses across internal resources can potentially enhance the performance of SSDs. However, exploiting parallelism inside SSDs is challenging owing to real-time access conflicts. In this paper, we propose a highly parallelizable I/O scheduler (PIOS) to improve internal resource utilization in SSDs from the perspective of I/O scheduling. Specifically, we first pinpoint the conflicting flash requests with precision during the address translation in the Flash Translation Layer (FTL). Then, we introduce conflict eliminated requests (CERs) to reorganize the I/O requests in the device-level queue by dispatching conflicting flash requests to different CERs. Owing to the significant performance discrepancy between flash read and write operations, PIOS employs differentiated scheduling schemes for read and write CER queues to always allocate internal resources to the conflicting CERs that are more valuable. The small dominant size prioritized scheduling policy for the write queue significantly decreases the average write latency. The high parallelism density prioritized scheduling policy for the read queue better utilizes resources by exploiting internal parallelism aggressively. Our evaluation results show that the parallelizable I/O scheduler (PIOS) can accomplish better SSD performance than existing I/O schedulers implemented in both SSD devices and operating systems.     

Reducing Transaction Processing Latency in Hardware Transactional Memory-based Database with Non-volatile Memory

The emergency of Hardware Transactional Memory (HTM) has greatly boosted the transaction processing performance in in-memory databases. However, the group commit protocol, aiming at reducing the impact from slow storage devices, leads to high transaction commit latency. Non-Volatile Memory (NVM) opens opportunities for reducing transaction commit latency. However, HTM cannot cooperate with NVM together: flushing data to NVM will always cause HTM to abort. In this paper, we propose a technique called parity version to decouple the process of HTM execution and NVM write. Thus, the transactions can correctly and efficiently use NVM to reduce their commit latency with HTM. We have integrated this technique into DBX, a state-of-the-art HTM-based database, and propose DBXN: a low-latency and high-throughput in-memory transaction processing system. Evaluations using typical OLTP workloads including TPC-C show that it has 99% lower latency and 2.1 times higher throughput than DBX.     

基于redis的分布式缓存系统架构研究

本文主要研究在redis基础上,从系统应用角度出发,研究包括key-value向关系统型数据库设计,数据一致性、系统可靠性、数据读写分离、数据切片原理,冗余备份热切换、系统高可扩展性等多维度的分布式缓存,并且构建并验证了redis集群的分布式缓存的系统架构.