Efficient agreement using fault diagnosis

Summary We give an extremely simple Byzantine agreement protocol that usesO(t ²) processors, min(f+2,t+1) rounds of communication,O(n·t·f·log|V|) total message bits, andO(log|V|) maximum message size, wheren is the total number of processors that actually participate in the protocol,t is an upper bound on the number of faulty processors,f is the number of processors that actually fail in a given execution, andV is the set of possible inputs. This protocol uses roughly the same resources as a more complex protocol due to Dolev, Reischuk, and Strong. By adding explicit fault diagnosis to our first protocol, we produce a some-what more complicated protocol that usesO(t ^1.5) processors, min(f+2,t+1) rounds,O(n·t ² ·f·log|V|) total message bits, andO(t·log|V|) maximum message size. Brian A. Coan received the B.S.E. degree in electrical engineering and computer science from Princeton University in 1977, the M.S. degree in computer engineering from Stanford University in 1979, and the Ph.D. degree in computer science from the Massachusetts Institute of Technology in 1987. He has worked for Amdahl Corporation and AT&T Bell Laboratories. Since 1987 he has been a member of the technical staff in the Network Systems Research Department at Bellcore. His main research interests are in distributed systems, fault tolerance, and platforms to support distributed multimedia systems.A preliminary version of this paper appeared in the Proceedings of the 26th Annual Allerton Conference on Communication, Control, and Computing, pp 663–672, 1988     

Modified distributed snapshots algorithm for protocol stabilization

This paper assesses the use of Chandy and Lamport's distributed snapshots algorithm (DSA) for stabilizing a communication protocol, a special type of distributed system. We show that when a loss of coordination occurs during the distributed execution of the protocol, DSA is not guaranteed to terminate, and therefore it sometimes fails to obtain a global state or snapshot. We propose some modifications to DSA to solve this problem. Finally, we discuss how, in the case of a loss of coordination, the modified algorithm can be used to stabilize a communication protocol, and we assess the suitability of the global state obtained by DSA as a recovery point to be used later in a backward recovery procedure.     

The incremental agreement

To achieve reliable distributed systems, the fault-tolerance must be studied. One of the most important problems of fault-tolerance issues lies in the Byzantine Agreement (BA) problem. The primary issue surrounding BA is that fault-free processors must obtain common agreement even in cases where faults persist. In this field, the fault diagnosis protocol has been proposed so that each fault-free processor detects/locates a common set of faulty processors. However, in this study, the incremental agreement is invoked to make each processor able to agreement upon executing the fault diagnosis protocol using minimal rounds of message exchange in the presence of dual failure characteristics of processors.     

Efficient distributed snapshots in an anonymous asynchronous message-passing system

We present a global snapshot algorithm with concurrent initiators, with termination detection in an anonymous asynchronous distributed message-passing system having FIFO channels. In anonymous systems, process identifiers are not available and an algorithm cannot use process identifiers in its operation. Such systems arise in several domains due to a variety of reasons. In the proposed snapshot algorithm for anonymous systems, each instance of algorithm initiation is identified by a random number (nonce); however, this is not used as an address in any form of communication. In the algorithm, each process can determine an instant when the local snapshot recordings at all the processes have terminated. This is a challenging problem when an algorithm cannot use process identifiers and a process does not know the number of processes in the system or the diameter of the network and cannot use a predefined topology overlay on the network, because there is no easy way to identify the global termination condition. The message complexity of our algorithm is (cn²)$\left(c{n}^2\right)$, where c$c$ is the number of concurrent initiators and n$n$ is the number of processes in the system, which is much better than that of the algorithm by Chalopin et al. (2012) [6]. Further, the algorithm by Chalopin et al. also requires knowledge of the network diameter.     

Solution of the Dirac equation in lattice QCD using a domain decomposition method

Efficient algorithms for the solution of partial differential equations on parallel computers are often based on domain decomposition methods. Schwarz preconditioners combined with standard Krylov space solvers are widely used in this context, and such a combination is shown here to perform very well in the case of the Wilson-Dirac equation in lattice QCD. In particular, with respect to even-odd preconditioned solvers, the communication overhead is significantly reduced, which allows the computational work to be distributed over a large number of processors with only small parallelization losses.     

Topology optimization of flow domains using the lattice Boltzmann method

We consider the optimal design of two- (2D) and three-dimensional (3D) flow domains using the lattice Boltzmann method (LBM) as an approximation of Navier-Stokes (NS) flows. The problem is solved by a topology optimization approach varying the effective porosity of a fictitious material. The boundaries of the flow domain are represented by potentially discontinuous material distributions. NS flows are traditionally approximated by finite element and finite volume methods. These schemes, while well established as high-fidelity simulation tools using body-fitted meshes, are effected in their accuracy and robustness when regular meshes with zero-velocity constraints along the surface and in the interior of obstacles are used, as is common in topology optimization. Therefore, we study the potential of the LBM for approximating low Mach number incompressible viscous flows for topology optimization. In the LBM the geometry of flow domains is defined in a discontinuous manner, similar to the approach used in material-based topology optimization. In addition, this non-traditional discretization method features parallel scalability and allows for high-resolution, regular fluid meshes. In this paper, we show how the variation of the porosity can be used in conjunction with the LBM for the optimal design of fluid domains, making the LBM an interesting alternative to NS solvers for topology optimization problems. The potential of our topology optimization approach will be illustrated by 2D and 3D numerical examples.     

Asymptotically optimal algorithms for approximate agreement

This paper introduces some algorithms to solve crash-failure, failure-by-omission and Byzantine failure versions of the Byzantine Generals or consensus problem, where non-faulty processors need only arrive at values that are close together rather than identical. For each failure model and each value ofS, we give at-resilient algorithm usingS rounds of communication. IfS=t+1, exact agreement is obtained. In the algorithms for the failure-by-omission and Byzantine failure models, each processor attempts to identify the faulty processors and corrects values transmited by them to reduce the amount of disagreement. We also prove lower bounds for each model, to show that each of our algorithms has a convergence rate that is asymptotic to the best possible in that model as the number of processors increases. Alan Fekete was born in Sydney Australia in 1959. He studied Pure Mathematics and Computer Science at the University of Sydney, obtaining a B.Sc.(Hons) in 1982. He then moved to Cambridge, Massachusetts, where he obtained a distributed Ph.D. degree, awarded by Harvard University's Mathematics department for work supervised by Nancy Lynch in M.I.T.'s Laboratory for Computer Science. He spend the year 1987–1988 at M.I.T. as a postdoctoral Research Associate, and is now Lecturer in Computer Science at the University of Sydney. His research concentrates on understanding the modularity in distributed algorithms, especially those used for concurrency control in distributed databases.A preliminary version of this paper has appeared in the Proceedings of the 5th ACM Symposium on Principles of Distributed Computing (August 1986). This work was begun in the Department of Mathematics, Harvard University, and completed at the Laboratory for Computer Science at Massachusetts Institute of Technology. The work was supported in part (through Professor N. Lynch) by the Office of Naval Research under Contract N00014-85-K-0168, by the Office of Army Research under contract DAAG29-84-K-0058, by the National Science Foundation under Grants MCS-8306854, DCR-83-02391, and CCR-8611442, and by the Defense Advanced Research Projects Agency (DARPA) under Contract N00014-83-K-0125     

Evaluating interrater agreement in SPICE-based assessments

Software process assessment (SPA) is a subjective measurement procedure. Hence, the reliability of the measures provided by human assessors contributes greatly to the level of confidence one can have in SPA results. Cohen's Kappa coefficient has been the most popular measure of reliability for measuring the degree of interrater agreement beyond chance. The application of the Kappa coefficient is incorrect in certain situations, however, due to two Kappa “paradoxes.” These paradoxes show that the value of a Kappa coefficient is biased downwards due to violations of the Kappa assumptions. To cope with cases of the insufficiency of Kappa, this study uses another simpler index of observed agreement between two teams of assessors along with Kappa to evaluate interrater agreement. Both measures, Kappa and observed agreement, were applied to 485 process attributes from 8 SPAs based on ISO/IEC 15504. Results show that in some cases, the Kappa coefficient cannot be used to measure the reliability of assessments, and the same paradoxes occur using a weighted Kappa coefficient. The use of the index of observed agreement circumvents these difficulties. Application of observed agreement is simple and easy to understand. It is also more amenable to the use of meaningful statistical tests to understand trends in interrater agreement. Moreover, the index of observed agreement can be used as a complementary method when the Kappa paradoxes do not apply.     

Semiparametric regression for assessing agreement using tolerance bands

This article describes a Bayesian semiparametric approach for assessing agreement between two methods for measuring a continuous variable using tolerance bands. A tolerance band quantifies the extent of agreement in methods as a function of a covariate by estimating the range of their differences in a specified large proportion of population. The mean function of differences is modelled using a penalized spline through its mixed model representation. The covariance matrix of the errors may also depend on a covariate. The Bayesian approach is straightforward to implement using the Markov chain Monte Carlo methodology. It provides an alternative to the rather ad hoc frequentist likelihood-based approaches that do not work well in general. Simulation for two commonly used models and their special cases suggests that the proposed Bayesian method has reasonably good frequentist coverage. Two real data sets are used for illustration, and the Bayesian and the frequentist inferences are compared.     

Extending binary Byzantine agreement to multivalued Byzantine agreement

A binary Byzantine agreement algorithm can be extended to produce a multivalued Byzantine agreement algorithm. The resulting multivalued algorithm is cheaper than previously published algorithms when the cost of transmitting values from the multivalued domain is significant.     

基于ECC的同态密钥协商

简要回顾了密钥管理的基本内容,指出常见的密钥协商协议的不足.介绍了ECC公钥密码体制和整数环上的同态加密机制,提出了基于ECC的同态密钥协商.该协议主要利用ECC的公钥和同态加密机制建立一个等献的、前向保密的会话密钥.和Diffie-Hellman系列密钥协商协议相比,提出的密钥协商协议具有更快的运算速度和基于口令的密钥协商协议相比,提出的密钥协商协议具有较好的安全性.并利用BAN逻辑证明了该协议的安全性.     

基于快照的大规模动态图相似节点查询算法

动态图拓扑结构演进过程中,为了量化在一定时间域内节点间联系的变化情况,定义了一种泛相似节点的概念,通过衡量其与当前节点的联系是否频繁、分布是否均匀来确定与当前节点的泛相似程度,并提出了一种基于快照的大规模动态图泛相似节点查询处理算法。具体包括:图动态演进过程的快照集表示,即演进动态图;图动态演进过程中的节点泛相似的语义及其形式化表示方式,从联系的频繁程度与分布的均匀程度对节点的相似程度进行了刻画;节点泛相似语义的矩阵表示及处理方式;针对这种语义的泛相似节点查询处理算法。真实数据集和合成数据集上的实验结果均表明算法能够处理大规模动态图上泛相似节点的查询问题,并在实际应用中运用实现。     

可信计算环境下基于TPM的认证密钥协商协议

基于身份的认证密钥协商协议存在密钥托管、ID管理、ID唯一性和私钥的安全分发等问题,目前的可信计算技术为此提供了很好的解决方案。利用TPM平台中EK和tpmproof唯一性的特点,结合McCullagh-Barreto认证密钥协商协议思想,提出了一个在可信计算环境下基于TPM的认证密钥协商协议,该协议较好地解决了上述基于身份的密钥协商协议所存在的问题。用CK模型对所提协议进行了安全性分析,结果表明该协议具备已知密钥安全性,完善前向保密性及密钥泄露安全性等CK安全模型下相应的安全属性。     

Solving lattice QCD systems of equations using mixed precision solvers on GPUs

Modern graphics hardware is designed for highly parallel numerical tasks and promises significant cost and performance benefits for many scientific applications. One such application is lattice quantum chromodynamics (lattice QCD), where the main computational challenge is to efficiently solve the discretized Dirac equation in the presence of an SU(3) gauge field. Using NVIDIA's CUDA platform we have implemented a Wilson-Dirac sparse matrix-vector product that performs at up to 40, 135 and 212 Gflops for double, single and half precision respectively on NVIDIA's GeForce GTX 280 GPU. We have developed a new mixed precision approach for Krylov solvers using reliable updates which allows for full double precision accuracy while using only single or half precision arithmetic for the bulk of the computation. The resulting BiCGstab and CG solvers run in excess of 100 Gflops and, in terms of iterations until convergence, perform better than the usual defect-correction approach for mixed precision.     

基于ECC的高效可认证组密钥协商协议

基于椭圆曲线密码体制(ECC)，建立了一个高效可认证的组密钥协商协议。该方案具有如下特点：(1)协议仅需要两轮交互，就可以实现组密钥协商; (2)利用类ElGamal密码系统，无需使用密钥分享技术，因此减轻了各参与方的计算量与通信负担; (3) 协议能够抵抗自适应选择消息攻击。     

Structured analysis of the ISI Atomic Pair Actions dataset using workflows

Understanding pair-wise activities is an essential step towards studying complex group and crowd behaviors in video. However, such research is often hampered by a lack of datasets that concentrate specifically on Atomic Pair Actions; [Here, we distinguish between the atomic motion of individual objects and the atomic motion of pairs of objects. The term action in Atomic Pair Action means an atomic interaction movement of two objects in video; a pair activity, then, is composed of multiple actions by a pair or multiple pairs of interacting objects ( and ). Please see Section 1 for details.] in addition, the general dearth in computer vision of a standardized, structured approach for reproducing and analyzing the efficacy of different models limits the ability to compare different approaches. In this paper, we introduce the ISI Atomic Pair Actions dataset, a set of 90 videos that concentrate on the Atomic Pair Actions of objects in video, namely converging, diverging, and moving in parallel. We further incorporate a structured, end-to-end analysis methodology, based on workflows, to easily and automatically allow for standardized testing of state-of-the-art models, as well as inter-operability of varied codebases and incorporation of novel models. We demonstrate the efficacy of our structured framework by testing several models on the new dataset. In addition, we make the full dataset (the videos, along with their associated tracks and ground truth, and the exported workflows) publicly available to the research community for free use and extension at <http://research.sethi.org/ricky/datasets/>.     

Boundary treatment for the lattice Boltzmann method using adaptive relaxation times

In this paper, we propose a new boundary treatment with almost second-order accuracy that does not require neighboring lattice information. In order to achieve improved accuracy for the boundary lattices, we used adaptive relaxation times reflecting boundary length scales that were unequal to the length scale of the internal fluid region lattices. Since the boundary treatment using adaptive relaxation times at the boundaries was formulated without information about the neighboring lattices, it could be easily applied to complex geometries. Numerical results using the proposed boundary treatment showed almost second-order accuracy for two-dimensional and three-dimensional problems without using information from neighboring lattices, unlike interpolation or extrapolation methods.     

A lattice computing approach for on-line fMRI analysis

We introduce an approach to fMRI analysis based on the Endmember Induction Heuristic Algorithm (EIHA). This algorithm uses the Lattice Associative Memory (LAM) to detect Lattice Independent vectors, which can be assumed to be Affine Independent, and therefore candidates to be the endmembers of the data. Induced endmembers are used to compute the activation levels of voxels as result of an unmixing process. The endmembers correspond to diverse activation patterns, one of these activation patterns corresponds to the resting state of the neuronal tissue. The on-line working of the algorithm does not need neither a previous training process nor a priori models of the data. Results on a case study compare with the results given by the state of art SPM software.     

基于身份的密钥协商协议研究

提出了两种基于身份的密钥协商协议.在这些协议中,所有用户共享一个秘密信息,通过较少的步骤实现密钥协商,用户无须复杂的证书管理,且提出的协议满足较高的安全性.     

Large eddy simulation of turbulent open duct flow using a lattice Boltzmann approach

Large eddy simulations of turbulent open duct flow are performed using the lattice Boltzmann method (LBM) in conjunction with the Smagorinsky sub-grid scale (SGS) model. A smaller value of the Smagorinsky constant than the usually used one in plain channel flow simulations is used. Results for the mean flow and turbulent fluctuations are compared to experimental data obtained in an open duct of similar dimensions. It is found that the LBM simulation results are in good qualitative agreement with the experiments.