Identity-based fault-tolerant conference key agreement

Lots of conference key agreement protocols have been suggested to secure computer network conference. Most of them operate only when all conferees are honest, but do not work when some conferees are malicious and attempt to delay or destruct the conference. Recently, Tzeng proposed a conference key agreement protocol with fault tolerance in terms that a common secret conference key among honest conferees can be established even if malicious conferees exist. In the case where a conferee can broadcast different messages in different subnetworks, Tzeng's protocol is vulnerable to a "different key attack" from malicious conferees. In addition, Tzeng's protocol requires each conferee to broadcast to the rest of the group and receive n - 1 message in a single round (where n stands for the number of conferees). Moreover, it has to handle n simultaneous broadcasts in one round. In this paper, we propose a fault-tolerant conference key agreement protocol, in which each conferee only needs to send one message to a "semitrusted" conference bridge and receive one broadcast message. Our protocol is an identity-based key agreement, built on elliptic curve cryptography. It is resistant to the different key attack from malicious conferees and needs less communication cost than Tzeng's protocol.     

Efficient task migration algorithm for distributed systems

The objective of the study was to achieve balanced load among processors, reduce the communication overhead of the load balancing algorithm, and improve respource utilization, which results in better average resonse time. A communication protocol and a fully distributed algorithm for dynamic load balancing through task migration in a connected N-processor network are presented. Each processor communicates its load directly with only a subset (of the size √ N) of processors, reducing communication traffic and average response time. It is proved that the given algorithm will perform task migration even if there is only one light load processor and one heavy load processor in the system. Simulation results show that the proposed scheme can save up to 60% of the protocol messages used by the broadcast algorithms and can reduce the average response time     

A fault-tolerant protocol for atomic broadcast

A general protocol for atomic broadcast in networks is presented. The protocol tolerates loss, duplication, reordering, delay of messages, and network partitioning in an arbitrary network of fail-stop sites (i.e. no Byzantine site behavior is tolerated). The protocol is based on majority-concensus decisions to commit on unique ordering of received broadcast messages. Under normal operating conditions, the protocol requires three phases to complete and approximately 4N/V messages where N is the number of sites. This overhead is distributed among the messages of which the delivery decision is made and the heavier the broadcast message traffic, the lower the overhead per broadcast message becomes. Under abnormal operating conditions, a decentralized termination protocol (also presented) is invoked. A performance analysis of this protocol is presented, showing that this protocol commits with high probability under realistic operating conditions without invoking termination protocol if N is sufficiently large. The protocol retains its efficiency in wide-area networks where broadcast communication media are unavailable     

Broadcast protocols for distributed systems

An innovative approach is presented to the design of fault-tolerant distributed systems that avoids the several rounds of message exchange required by current protocols for consensus agreement. The approach is based on broadcast communication over a local area network, such as an Ethernet or a token ring, and on two novel protocols, the Trans protocol, which provides efficient reliable broadcast communication, and the Total protocol, which with high probability promptly places a total order on messages and achieves distributed agreement even in the presence of fail-stop, omission, timing, and communication faults. Reliable distributed operations, such as locking, update, and commitment, typically require only a single broadcast message rather than the several tens of messages required by current algorithms     

An Adaptive Causal Ordering Algorithm Suited to Mobile Computing Environments

Causal message ordering is required for several distributed applications. In order to preserve causal ordering, only direct dependency information between messages, with respect to the destination process(es), need be sent with each message. By eliminating other kinds of control information from the messages, the communication overheads can be significantly reduced. In this paper we present an algorithm that uses this knowledge to efficiently enforce causal ordering of messages. The proposed algorithm does not require any prior knowledge of the network topology or communication pattern. As computation proceeds, it acquires knowledge of the communication pattern and is capable of handling dynamically changing multicast communication groups, and minimizing the communication overheads. With regard to communication overheads, the algorithm is optimal for the broadcast communication case. Extensive simulation experiments demonstrate that the algorithm imposes lower communication overheads than previous causal ordering algorithms. The algorithm can be employed in a variety of distributed computing environments. Its energy efficiency and low bandwidth requirement make it especially suitable for mobile computing systems. We show how to employ the algorithm for causally ordered multicasting of messages in mobile computing environments.     

Efficient Dissemination of Transaction-Consistent Data in Broadcast Environments

In this paper, we present a novel protocol for disseminating data in broadcast environments such that view consistency, a useful correctness criterion for broadcast environments, is guaranteed. Our protocol is based on concurrency control information that is constructed by the server and is broadcasted at the beginning of each broadcast cycle. The concurrency control information mainly captures read-from relations among update transactions. A salient feature of the protocol is that the concurrency control information is small in size, but precise enough for reducing unnecessary abortion of mobile transactions. The small-sized concurrency control information implies low communication overhead on broadcasting system. In addition, the computation overheads imposed by the algorithm on the server and the clients are low. We also address the reliability issue of wireless communication and the incorporation of a prefetching mechanism into our protocol. Simulation results demonstrate the superiority of our protocol in comparison with existing methods. Furthermore, we have extended our protocol to deal with local view consistency which requires that all mobile transactions submitted by the same client observe the same serial order of update transactions     

Efficient algorithms for all-to-all communications in multiportmessage-passing systems

We present efficient algorithms for two all-to-all communication operations in message-passing systems: index (or all-to-all personalized communication) and concatenation (or all-to-all broadcast). We assume a model of a fully connected message-passing system, in which the performance of any point-to-point communication is independent of the sender-receiver pair. We also assume that each processor has k⩾1 ports, through which it can send and receive k messages in every communication round. The complexity measures we use are independent of the particular system topology and are based on the communication start-up time, and on the communication bandwidth     

A one-round secure message broadcasting protocol through a key sharing tree

A key sharing graph is one in which each vertex corresponds to a player, and each edge corresponds to a secret key shared by the two players incident with the edge. Assume that, given a key sharing graph which contains a spanning tree, any designated player wishes to broadcast a message to all the other players securely against an eavesdropper. This can be easily done by flooding the message on the tree using the one-time pad scheme. However, the number of communication rounds in such a protocol is equal to the height of the tree. This paper provides another efficient protocol, which has exactly one communication round, i.e., we give a non-interactive protocol.     

Processor membership in asynchronous distributed systems

Presents protocols for determining processor membership in asynchronous distributed systems that are subject to processor and communication faults. These protocols depend on the placement of a total order on broadcast messages. The types of systems for which each of these protocols is applicable are characterized by the properties of the communication mechanisms and by the availability of stable storage. In the absence of stable storage or of a mechanism for distinguishing promptly delivered messages, the authors show that no membership protocol can exist. They also discuss their experience in implementing these membership protocols     

Using optimistic atomic broadcast in transaction processing systems

Atomic broadcast primitives are often proposed as a mechanism to allow fault-tolerant cooperation between sites in a distributed system. Unfortunately, the delay incurred before a message can be delivered makes it difficult to implement high performance, scalable applications on top of atomic broadcast primitives. Recently, a new approach has been proposed for atomic broadcast which, based on optimistic assumptions about the communication system, reduces the average delay for message delivery to the application. We develop this idea further and show how applications can take even more advantage of the optimistic assumption by overlapping the coordination phase of the atomic broadcast algorithm with the processing of delivered messages. In particular, we present a replicated database architecture that employs the new atomic broadcast primitive in such a way that communication and transaction processing are fully overlapped, providing high performance without relaxing transaction correctness.     

Adaptive broadcast by fault-tolerant spanning tree switching

Adaptation is a desirable requirement in a distributed system as it helps the system to perform efficiently under different environments. For many problems, more than one protocol exists, such that one protocol performs better in one environment while the other performs better in another. In such cases, adaptive distributed systems can be designed by dynamically switching between the protocols as the environment changes. Distributed protocol switching is also important for performance enhancement, or fault-tolerance of a distributed system. In this work, we illustrate distributed protocol switching by providing a distributed algorithm for adaptive broadcast that dynamically switches from a BFS tree to a DFS tree. The proposed switching algorithm can also handle arbitrary crash failures. It ensures that switching eventually terminates in spite of failures and the desired tree (DFS tree) results as the output. We also investigate the properties that can be guaranteed on the delivery of broadcast messages under specific failure conditions. We show that under no failure, each broadcast message is eventually correctly delivered to all the nodes in spite of switching. Under arbitrary crash fault, we ensure that switching eventually terminates with the desired tree as the broadcast topology. We also investigate the specific delivery guarantees that can be provided when a single crash fault happens, both during switching and when no switching is in progress.     

Optimal NODUP all-to-all broadcast schemes in distributed computingsystems

Broadcast, referring to a process of information dissemination in a distributed system whereby a message originating from a certain node is sent to all other nodes in the system, is a very important issue in distributed computing. All-to-all broadcast means the process by which every node broadcasts its certain piece of information to all other nodes. In this paper, we first develop the optimal all-to-all broadcast scheme for the case of one-port communication, which means that each node can only send out one message in one communication step, and then, extend our results to the case of multi-port communication, i.e., k-port communication, meaning that each node can send out k messages in one communication step. We prove that the proposed schemes are optimal for the model considered in the sense that they not only require the minimal number of communication steps, but also incur the minimal number of messages     

Concurrent Broadcast for Information Dissemination

Concurrent broadcast involves the dissemination of a database, consisting of messages initially distributed among the nodes of a network, so that a copy of the entire database eventually resides at each node. One application is the dissemination of network status information for adaptive routing in a communications network. This paper examines the time complexity and communication complexity of several distributed procedures for concurrent broadcast. The procedures do not use information depending on the network topology. The worst-case time complexity of a flooding procedure for concurrent broadcast is shown to be linear in the number of nodes plus the number of messages, and no other procedure for concurrent broadcast has a better worst-case time complexity. A variant of flooding is proposed to eliminate redundant message receipts from the flooding process by real-time signaling between neighbors concerning messages residing at each. This variant can reduce communication complexity, while having a worst-case time complexity similar in form to that of the flooding procedure. Special properties of concurrent broadcast in a tree are also given. The present time complexity results can be used to bound the time during which inconsistent databases may reside at different nodes, to evaluate and compare procedures for (or including) concurrent broadcast, and to schedule a sequence of instances of concurrent broadcast so that the instances do not overlap and there is no need for sequence numbers.     

Atomic broadcast in asynchronous crash-recovery distributed systems and its use in quorum-based replication

Atomic broadcast is a fundamental problem of distributed systems: It states that messages must be delivered in the same order to their destination processes. This paper describes a solution to this problem in asynchronous distributed systems in which processes can crash and recover. A consensus-based solution to atomic broadcast problem has been designed by Chandra and Toueg for asynchronous distributed systems where crashed processes do not recover. We extend this approach: it transforms any consensus protocol suited to the crash-recovery model into an atomic broadcast protocol suited to the same model. We show that atomic broadcast can be implemented requiring few additional log operations in excess of those required by the consensus. The paper also discusses how additional log operations can improve the protocol in terms of faster recovery and better throughput. To illustrate the use of the protocol, the paper also describes a solution to the replica management problem in asynchronous distributed systems in which processes can crash and recover. The proposed technique makes a bridge between established results on weighted voting and recent results on the consensus problem.     

基于秘密共享的无线传感器网络广播密钥分发协议

在无线传感器网络中,能量消耗主要集中在节点之间的通信上,节点计算所消耗的能量远小于通信所消耗的能量。由于无线传感器网络的"一对多"和"多对一"通信模式,广播是节约能量的主要通信方式。为了保证广播实体和消息的合法性和保密性,必须首先解决无线传感器网络广播密钥安全分发问题。本文在充分考虑无线传感器网络自身特点的基础上,基于Shamir的门限秘密共享方案,提出了椭圆曲线双线性对上的无线传感器网络广播密钥分发协议,并对其进行安全性和性能分析。分析发现,该协议不仅满足安全性要求,同时,能够适合无线传感器网络的特殊应用要求。     

Authenticating tripartite key agreement protocol with pairings

In this paper, an authenticated tripartite key agreement protocol is proposed, which is an ID-based one with pairings. This protocol involves only one round. The authenticity of the protocol is assured by a special signature scheme, so that messages carrying the information of two ephemeral keys can be broadcasted authentically by an entity. Consequently, one instance of the protocol results in eight session keys for three entities. In other word, one instance of the protocol generates a session key, which is eight times longer than those obtained from traditional key agreement protocols. Security attributes of the protocol are presented, and the computational overhead and bandwidth of the broadcast messages are analyzed as well.     

WSN中一种基于身份的短签名广播认证协议

广播认证是传感器网络中很重要的安全服务,它允许发送者通过安全的方式广播信息给多个节点。无线传感器网络中的μTESLA、M-μTESLA等基于消息认证码的广播认证协议存在一些不足,加上最近的研究显示,基于双线性对的加密算法可应用于资源有限的传感器节点。本文介绍一种高效的基于身份的无证书短签名协议,它拥有目前最短的签名长度160bits,计算量相比其他公钥签名低得多,还能提供认证多个基站的广播信息的功能。基于MICA2DOT平台对其通信和计算能量消耗进行分析,以及对该协议的其他性能的分析,得出该协议引入的能量消耗小,满足广播认证的一些重要性质,适合无线传感器网络环境。     

Simple and efficient oracle-based consensus protocols for asynchronous Byzantine systems

This paper is on the consensus problem in asynchronous distributed systems where (up to f) processes (among n) can exhibit a Byzantine behavior, i.e., can deviate arbitrarily from their specification. One way to solve the consensus problem in such a context consists of enriching the system with additional oracles that are powerful enough to cope with the uncertainty and unpredictability created by the combined effect of Byzantine behavior and asynchrony. This paper presents two kinds of Byzantine asynchronous consensus protocols using two types of oracles, namely, a common coin that provides processes with random values and a failure detector oracle. Both allow the processes to decide in one communication step in favorable circumstances. The first is a randomized protocol for an oblivious scheduler model that assumes n > 6f. The second one is a failure detector-based protocol that assumes n > tif. These protocols are designed to be particularly simple and efficient in terms of communication steps, the number of messages they generate in each step, and the size of messages. So, although they are not optimal in the number of Byzantine processes that can be tolerated, they are particularly efficient when we consider the number of communication steps they require to decide and the number and size of the messages they use. In that sense, they are practically appealing.     

Optimal bounds on the gain of permitting dynamic allocation of communication channels in distributed computing

Consider a distributed system consisting of n computers connected by a number of identical broadcast channels. All computers may receive messages from all channels. We distinguish between two kinds of systems: systems in which the computers may send on any channel (dynamic allocation) and system where the send port of each computer is statically allocated to a particular channel. A distributed task (application) is executed on the distributed system. A task performs execution as well as communication between its subtasks. We compare the completion time of the communication for such a task using dynamic allocation and channels with the completion time using static allocation and channels. Some distributed tasks will benefit very much from allowing dynamic allocation, whereas others will work fine with static allocation. In this paper we define optimal upper and lower bounds on the gain (or loss) of using dynamic allocation and channels compared to static allocation and channels. Our results show that, for some tasks, the gain of permitting dynamic allocation is substantial, e.g. when , there are tasks which will complete 1.89 times faster using dynamic allocation compared to using the best possible static allocation, but there are no tasks with a higher such ratio. Received: 26 February 1998 / 26 July 1999     

一个新的分布式最小连通支配集近似算法

在计算机网络中广泛使用广播来解决一些网络问题,设计有效的广播算法是一项重要的课题。文中提出一种分布地计算网络最小连通支配集的近似算法并给出了它的正确性证明。它只需要网络节点具有局部的网络状态信息,可伸缩性强。通过此算法可以在网络中自动形成一个虚拟骨干网,从而可为网络中的广播和路由操作提供一个有效的通信基础。模拟结果表明,文中提出的算法求得的连通支配集小,能较好地应用于一般网络以及移动自组网络中。