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     

The abstract MAC layer

A diversity of possible communication assumptions complicates the study of algorithms and lower bounds for radio networks. We address this problem by defining an abstract MAC layer. This service provides reliable local broadcast communication, with timing guarantees stated in terms of a collection of abstract delay functions applied to the relevant contention. Algorithm designers can analyze their algorithms in terms of these functions, independently of specific channel behavior. Concrete implementations of the abstract MAC layer over basic radio network models generate concrete definitions for these delay functions, automatically adapting bounds proven for the abstract service to bounds for the specific radio network under consideration. To illustrate this approach, we use the abstract MAC layer to study the new problem of Multi-Message Broadcast, a generalization of standard single-message broadcast in which multiple messages can originate at different times and locations in the network. We present and analyze two algorithms for Multi-Message Broadcast in static networks: a simple greedy algorithm and one that uses regional leaders. We then indicate how these results can be extended to mobile networks.     

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

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

Interleaved all-to-all reliable broadcast on meshes and hypercubes

All-to-all (ATA) reliable broadcast is the problem of reliably distributing information from every node to every other node in point-to-point interconnection networks. A good solution to this problem is essential for clock synchronization, distributed agreement, etc. We propose a novel solution in which the reliable broadcasts from individual nodes are interleaved in such a manner that no two packets contend for the same link at any given time-this type of method is particularly suited for systems which use virtual cut-through or wormhole routing for fast communication between nodes. Our solution, called the IHC Algorithm, can be used on a large class of regular interconnection networks including regular meshes and hypercubes. By adjusting a parameter η referred to as the interleaving distance, we can flexibly decrease the link utilization of the IHC algorithm (for normal traffic) at the expense of an increase in the time required for ATA reliable broadcast. We compare the IHC algorithm to several other possible virtual cut-through solutions and a store-and-forward solution. The IHC algorithm with the minimum value of η is shown to be optimal in minimizing the execution time of ATA reliable broadcast when used in a dedicated mode (with no other network traffic)     

Link layer for cooperating processes on a LAN with enhanced communication services

Most local area networks support multicast and broadcast communication facilities among the network nodes. However, their use among processes has been limited by the lack of support in the distributed operating system kernel and by the limited requirements of traditional computer network applications. Some applications (e.g. operating in a multicast environment) and distributed algorithms require advanced associations among processes, whose support by the operating system kernel can take advantage of properly designed functions provided by the communication subsystem. This problem is examined in the context of an architecture for LANs, and enhanced protocols are described that can be provided by a communication subsystem based on a LAN. Virtual network protocols provide classes of service suited to a multicast environment. Their availability at communication subsystem layers offers higher layers a common framework for the implementation of a computing system with distributed control.     

Dynamic end-to-end capacity in IEEE 802.16 wireless mesh networks

The IEEE 802.16 standard defines mesh mode as one of its two operational modes in medium access control (MAC). In the mesh mode, peer-to-peer communication between subscriber stations (SSs) is allowed, and transmissions can be routed via other SSs across multiple hops. In such an IEEE 802.16 mesh network, accurate and reliable determination of dynamic link capacity and end-to-end capacity of a given multi-hop route is crucial for robust network control and management. The dynamic capacities are difficult to determine in a distributed system due to decentralized packet scheduling and interference between communicating nodes caused by the broadcast nature of radio propagation. In this paper, we first propose a method for computing the dynamic link capacity between two mesh nodes, and extend that to determine the dynamic end-to-end capacity bounds of a multi-hop route based on the concept of Bottleneck Zone. The physical deployments of networks are also considered in the capacity estimation. We demonstrate the effectiveness and accuracy of our methods for computing dynamic link capacity and end-to-end capacity bounds through extensive simulations.     

Performance evaluation of wireless sensor network protocols for industrial applications

Recently, distributed wireless microsensor systems have provided more flexible leverage to emerging industrial applications. The tiny distributed wireless microsensor network systems, however, should be designed to overcome various constraints such as limited energy, bandwidth limit, and unexpected failure of communication under disturbances. In addition, their network topologies need to be managed with designated communication protocols. Thus, design of microsensor network protocols still needs to be application-specific. It should be also evaluated through designated tools at each level of networking characteristics. This research describes essential factors that affect the performance of sensor network systems in the design of wireless microsensor network protocols, and presents effective time-based network protocol and performance evaluation tool which are applicable for various protocols in industrial applications. The developed network evaluation tool, called TIE/MEMS, also includes functional comparison with recent protocols proposed for wireless microsensor networks, and provides design guidelines for multi-sensor network systems needed for emerging industrial applications.     

Broadcasting in dynamic radio networks

It is reasonable to claim that almost all major questions related to radio broadcasting can be considered closed as far as static networks are considered: the network never changes during the entire protocol's execution. On the other hand, theoretical results on communication protocols in any scenario where the network topology may change during protocol's execution (i.e. a dynamic radio network) are very few.In this paper, we present a theoretical study of broadcasting in radio networks having dynamic unknown topology. The dynamic network is modeled by means of adversaries: we consider two of them. We first analyze an oblivious, memoryless random adversary that can be seen as the dynamic version of the average-case study presented by Elsässer and Gasieniec in JCSS, 2006. We then consider the deterministic worst-case adversary that, at each time slot, can make any network change (thus the strongest adversary). This is the dynamic version of the worst-case study provided by Bar-Yehuda, Goldreich and Itai in JCSS, 1992.In both cases we provide tight bounds on the completion time of randomized broadcast protocols.     

Necessary and sufficient conditions for broadcast consensus protocols

Summary We consider consensus protocols in asynchronous distributed systems that are based on broadcast communication. We show that a necessary and sufficient condition for the existence of a deterministic consensus protocol is delivery of each broadcast message to at least (n+k+1)/2 processes in ann-process system subject tok crash failures with either eventual fair broadcasting or eventual full broadcasting. The broadcast model captures the idea of a broadcast communication medium, such as the Ethernet, in which messages, if delivered, are delivered immediately and in order but not necessarily to all processes. Louise E. Moser received the Ph.D. degree in mathematics from the University of Wisconsin, Madison, in 1970. From 1970 to 1987 she was a professor of mathematics and computer science at California State University, Hayward. In 1987 she moved to the University of California, Santa Barbara, where is currently on the faculty of the Department of Electrical and Computer Engineering. Her current research interests include parallel and distributed systems, network architectures and communication protocols, and formal methods in software engineering. P.M. Melliar-Smith received the Ph.D. degree in computer science from the University of Cambridge, Cambridge, England, in 1987. He was a senior research scientist and program director at SRI International in Menlo Park (1976–1987), senior research associate at the University of Newcastle Upon Tyne (1973–1976), and principal designer for GEC Computers Ltd. in England (1964–1973). He is currently a professor in the Department of Electrical and Computer Engineering at the University of California, Santa Barbara. His research interests include fault-tolerant distributed systems, high-speed communication networks and protocols, and formal specification and verification. Vivek Agrawala received the B.Tech. degree in chemical engineering in 1984 and the M. Tech. degree in computer technology in 1986, both from the Indian Institute of Technology, Delhi, and a Ph.D. in computer science in 1991 from the University of California, Santa Barbara. Since then he has been a Research Scientist at Siemens Corporate Research, Princeton, New Jersey. His major research interests are distributed algorithms, software design methods, and distributed systems.This research was supported by the National Science Foundation, Grant Numbers CCR-8908515 and NCR-9016361. V. Agrawala's current address is Siemens Corporate Research, 755 College Road East, Princeton, NJ 08540, USA     

无线传感网中混合业务下的触发式流控制算法

无线传感器网络中,节点所具有的能量和通信能力等都十分有限,如何设计有效的协议及算法,利用有限的资源高效地完成诸多任务,成为无线传感器网络设计所面临的一大挑战.考虑接收容量模型,研究了无线传感器网络在节点接收容量和能量联合受限情况下,面向混合业务时的效用公平流控制问题,并针对传统对偶分解算法存在着收敛速度慢、步长不易调节、通信负荷大等缺陷,进一步提出了基于事件触发的分布式求解算法.理论分析与仿真验证均表明:使用事件触发算法时,传感节点的平均广播周期比使用对偶分解算法时大很多,大幅度降低了无线传感器网络节点间的通信量,减少了网络的通信开销.仿真结果显示:与对偶分解算法相比,分布式事件触发算法具有收敛速度快、对网络规模扩展的适应性强等优势;与传统的速率公平流控制机制相比,所提的效用公平流控制模型能够更加适应弹性与非弹性业务共存的网络场景.     

Upper and lower bounds for deterministic broadcast in powerline communication networks

Powerline communication networks assume an interesting position in the communication network space: similarly to wireless networks, powerline networks are based on a shared broadcast medium; unlike wireless networks, however, the signal propagation is constrained to the power lines of the electrical infrastructure, which is essentially a graph. This article presents an algorithmic model to study the design of communication services over powerline communication networks. As a case study, we focus on the fundamental broadcast problem, and present and analyze a distributed algorithm \(\textsc {Color}\textsc {Cast}\) which terminates in at most n communication rounds, where n denotes the network size, even in a model where link qualities are unpredictable and time-varying. For comparison, the achieved broadcast time is lower than what can be achieved by any unknown-topology algorithm (lower bounds \(\varOmega (n\log n / \log (n/D))\) and \(\varOmega (n \log D)\) are proved in Kowalski and Pelc (Distrib Comput 18(1):43–57, 2005) resp. Clementi et al. (2001) where D is the network diameter). Moreover, existing known-topology broadcast algorithms often fail to deliver the broadcast message entirely in this model. This article also presents a general broadcast lower bound for the powerline model.     

A concurrent network architecture for cost-efficient parallel computing using workstation clusters

Within the past few years, workstation clusters have gained an increasing importance as platforms for parallel high-performance simulation problems. In contrast to the specialized and cost-intensive interconnection network of distributed memory multiprocessor systems, workstation clusters utilize local area networks (LANs) and common communication protocols. Therefore, the cost-efficiency of workstation clusters for parallel tasks is high while the communication performance is limited compared to parallel computer systems. To improve the communication performance of clusters, new protocols can be applied as well as specialized interconnection networks. On one hand, these solutions decrease the cost-efficiency of clusters, while on the other hand the performance of local area networks is increasing because of new technologies such as FastEthernet, GigaEthernet or ATM. In this contribution, we propose increasing the communication performance of clusters through the concurrent network architecture (CNA) with multi-channel communication systems. Through the use of parallel and independent LANs, the communication performance of a cluster can be improved while maintaining the cost-efficiency of the wide-spread LAN technology and protocols. This paper gives an overview of the CNA, the requirements of an implementation and a performance evaluation of a CNA workstation cluster.     

A Survey of Fault Management in Wireless Sensor Networks

Wireless sensor networks are resource-constrained self-organizing systems that are often deployed in inaccessible and inhospitable environments in order to collect data about some outside world phenomenon. For most sensor network applications, point-to-point reliability is not the main objective; instead, reliable event-of-interest delivery to the server needs to be guaranteed (possibly with a certain probability). The nature of communication in sensor networks is unpredictable and failure-prone, even more so than in regular wireless ad hoc networks. Therefore, it is essential to provide fault tolerant techniques for distributed sensor applications. Many recent studies in this area take drastically different approaches to addressing the fault tolerance issue in routing, transport and/or application layers. In this paper, we summarize and compare existing fault tolerant techniques to support sensor applications. We also discuss several interesting open research directions. Lilia Paradis is currently a graduate student in the Department of Mathematical and Computer Sciences, Colorado School of Mines. She is also part of the Toilers Ad Hoc Networking research group. She is interested in distributed communication protocols for wireless sensor networks. Qi Han received the PhD degree in computer science from the University of California, Irvine in 2005. She is currently an assistant professor in the Department of Mathematical and Computer Sciences, Colorado School of Mines. Her research interests include distributed systems, middleware, mobile and pervasive computing, systems support for sensor applications, and dynamic data management. She is specifically interested in developing adaptive middleware techniques for next generation distributed systems. She is a member of the IEEE and the ACM.     

Establishment of isolated failure immune real-time channels inHARTS

Fault-tolerant, real-time communication in distributed systems is very important yet difficult to achieve. Traditional protocols like the TCP/IP achieve reliable communication through acknowledgment and retransmission schemes, where one achieves the reliability at the cost of performance, In this paper, we discuss how both the timeliness and fault-tolerance of communication can be achieved by using the concept of real-time channel and exploring the inherent spatial redundancy of a given network topology, Specifically, we show how isolated failure immune real-time channels can be established in wrapped hexagonal mesh networks, thus ensuring timely delivery of messages in the presence of network component failures as long as the failures are isolated. This kind of fault-tolerance cannot be achieved with other commonly-known topologies like rings, rectangular meshes, and hypercubes. The proposed approach is to be implemented in an experimental distributed real-time system, called HARTS, whose construction is underway     

Complexity of distributed commit protocols

Summary Implementation of atomic actions in a distributed system in the presence of fail-stop failures is investigated. Worst case time and message complexities of the protocols realizing this are studied on complete graphs, rings, trees, and arbitrary graphs. Two modes of communication are considered — point-to-point and broadcast. Individual lower and upper bounds on time and messages are presented and the simultaneous achievability of the optimum message and time bounds is shown impossible in all the interesting cases.     

Near-optimal all-to-all broadcast in multidimensional all-portmeshes and tori

All-to-all communication is one of the most dense collective communication patterns and occurs in many important applications in parallel and distributed computing. In this paper, we present a new all-to-all broadcast algorithm in multidimensional all-port mesh and torus networks. We propose a broadcast pattern which ensures a balanced traffic load in all dimensions in the network so that the all-to-all broadcast algorithm can achieve a very tight near-optimal transmission time. The algorithm also takes advantage of overlapping of message switching time and transmission time, and the total communication delay asymptotically matches the lower bound of all-to-all broadcast. Finally, the algorithm is conceptually simple and symmetrical for every message and every node so that it can be easily implemented in hardware and achieves the near-optimum in practice     

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     

An interface to a reliable packet delivery service for parallelsystems

Modern distributed memory parallel computers provide hardware support for the efficient and reliable delivery of interprocessor messages. This facility needs to be accessed by lightweight protocols that do not waste the performance of the underlying hardware; the heavyweight layering techniques traditionally used in distributed systems are wholly inappropriate. A low-level communication interface is therefore presented which exploits modern architectures effectively, while maintaining a good match to existing parallel programming environments. The interface defines mechanisms to access an asynchronous reliable packet delivery service. It permits messaging protocols to be efficiently synthesized by considering the activity at their end-points alone. This arrangement effectively decouples the implementation of protocols from low-level architectural features, and hence aids the portability of parallel programming environments. Furthermore, the interface allows the communication network to be shared by multiple programming paradigms, giving additional flexibility over existing systems     

Reliable and efficient communications in sensor networks

Wireless sensor networks are inherently plagued by problems of node failure, interference to communications from environmental noise and energy-limited sensor motes. These problems pose conflicting issues in the design of suitable routing protocols. Several existing reliable routing protocols exploit message broadcast redundancy and hop count as routing metrics and their performance trade-offs are revealed during simulation. In this paper, we study and analyse related design issues in proposed efficient and reliable routing protocols that attempt to achieve reliable and efficient communication performance in both single- and multi-hub sensor networks. Simulation results of four such routing protocols show that routing performance depends more on optimal (near-optimal) routing in single hub than in multi-hub networks. Our work also shows that optimal (near-optimal) routing is better achieved when historical metrics like packet distance traversed and transmission success are also considered in the routing protocol design.     

Repetition-based cooperative broadcasting for vehicular ad-hoc networks

In vehicular ad hoc networks, most of critical applications involved with safety rely on reliable broadcast communications with low latency. Recently, repetition-based protocols have been proposed to meet the requirements of timeliness and reliability for broadcasting. In these protocols, a sender repeatedly retransmits the broadcast message during the lifetime of the message. However, existing protocols face serious problems such as deterioration of the signal quality caused by wireless fading. In particular, since excessive repetitions might cause network congestion and waste channel resources, reliability of broadcasting should be achieved with as small a number of repetitions as possible. In this paper, we therefore propose a novel repetition-based broadcast protocol which exploits a cooperative diversity technique (called RB-CD) making a small number of repetitions robust for wireless fading. To support this cooperative diversity, neighboring nodes transmit the same message almost simultaneously (that is, using the same repetition pattern for each other) in order to form a virtual antenna array. The virtual antenna array achieves a diversity gain at the receivers. In the RB-CD protocol, the virtual antenna array consists of the source and some of its neighbors (called relays) which participate in repeating the transmission of a broadcast message. In addition, a new distributed relay selection algorithm is introduced in the RB-CD protocol. From the ns-2 simulation results, we verified that RB-CD provides a more reliable broadcasting service due to its capability of exploiting cooperative diversity.