Meeting the deadline: on the complexity of fault-tolerant continuous gossip

In this paper we introduce the problem of Continuous Gossip in which rumors are continually and dynamically injected throughout the network. Each rumor has a deadline, and the goal of a continuous gossip protocol is to ensure good ??Quality of Delivery,?? i.e., to deliver every rumor to every process before the deadline expires. Thus, a trivial solution to the problem of Continuous Gossip is simply for every process to broadcast every rumor as soon as it is injected. Unfortunately, this solution has high per-round message complexity. Complicating matters, we focus our attention on a highly dynamic network in which processes may continually crash and recover. In order to achieve good per-round message complexity in a dynamic network, processes need to continually form and re-form coalitions that cooperate to spread their rumors throughout the network. The key challenge for a Continuous Gossip protocol is the ongoing adaptation to the ever-changing set of active rumors and non-crashed process. In this work we show how to address this challenge; we develop randomized and deterministic protocols for Continuous Gossip and prove lower bounds on the per-round message-complexity, indicating that our protocols are close to optimal.     

A Pre-Processed Cross Link Detection Protocol for geographic routing in mobile ad hoc and sensor networks under realistic environments with obstacles

In mobile ad hoc and sensor networks, greedy-face-greedy (GFG) geographic routing protocols have been a topic of active research in recent years. Most of the GFG geographic routing protocols make an ideal assumption that nodes in the network construct a unit-disk graph, UDG, and extract a planar subgraph from the UDG for face routing. However, the assumption of UDG may be violated in realistic environments, which may cause the current GFG geographic routing protocols to fail. In this paper, we propose a Pre-Processed Cross Link Detection Protocol, PPCLDP, which extracts an almost planar subgraph from a realistic network graph, instead of a UDG, for face routing and makes the GFG geographic routing work correctly in realistic environments with obstacles. The proposed PPCLDP improves the previous work of Cross Link Detection Protocol, CLDP, with far less communication cost and better convergence time. Our simulation results show that the average communication cost and the average convergence time of PPCLDP are, respectively, 65% and 45% less than those of CLDP. This makes PPCLDP more desirable for mobile ad hoc and sensor networks.     

Virtual Time CSMA Protocols for Hard Real-Time Communication

We study virtual time CSMA protocols for hard real time communication systems, i, e., systems where messages have explicit deadlines. In this class of CSMA protocols, each node maintains two clocks; a real time clock and a virtual time clock. Whenever a node finds the channel to be idle, it resets its virtual clock. The virtual clock then runs at a higher rate than the real clock. A node transmits a waiting message when the time on the virtual clock is equal to some parameter of the message. Using different message parameters in conjunction with the virtual clock, different transmission policies can be implemented. In particular, use of message arrival time, message length, message laxity, and message deadline implements FCFS, Minimum-Length-First, Minimum-Laxity-First, and Minimum-Deadline-First transmission policies, respectively.     

Perfectly Reliable Message Transmission

We consider the problem of reliable message transmission between two synchronous players connected by n wires, some of which may be faulty. We show how to get reliability “for free”—reliable transmission of b bits involves a total communication of only O(b) bits, when b is large enough. We also construct an efficient Perfectly Secure Message Transmission Protocol.     

A cooperative game coding scheme

The transmission of a message over a Gaussian channel using a noisy feedback and signals with no bandwidth constraint can be treated as a two-person cooperative game with one of the players stationary. The resultant coding strategy allows error-free transmission at a rate R < R_c, the critical signalling rate. An expression for the probability of error is developed for finite values of the transmission interval T. In the case of noiseless feedback, this coding scheme emerges as a generalization of the scheme of Schalkwijk and Kailath.     

Scheduling time-constrained multicast messages in circuit-switched tree networks

In this paper, we consider a kind of multicast scheduling problem in a tree network. Each multicast message is transmitted through a directed subtree within the tree network. The transmission time of each multicast message is assumed to be one unit. Two messages can be transmitted at the same time if their subtrees are edge-disjoint. Each message is constrained by a ready time and a deadline, and has a weight we can gain if it is scheduled within its deadline. The optimality criterion is the total weight we gain. We assume that the degree of each subtree is bounded by a constant d and present an approximation algorithm of which the approximation ratio is at most 4d+15.     

Optimal utilization of fixed-capacity channels in feedback control

The performance limitations on the linear control of a linear plant, due to the presence of a feedback channel with finite information capacity, are considered in this paper. This situation may arise in such diverse applications as (a) the remote control of a plant, using a digital data link for feedback, (b) where quantization errors and bit errors of a digital controller may be modelled as occurring in a noisy digital channel in cascade with an ideal controller, and (c) in human-operator modelling, where the sensory feedback channels are characterized by fixed information capacity due to neural noise. The principle result obtained is that, given the state-dimension n of the plant and the channel capacity ?, reliability function E(R), and block encoding time $\text{T> >}\text{1}\text{C}$, the optimum data-rate R satisfies the equation 2R=nE(R). This rate provides the optimum tradeoff between the effects of quantization errors and message errors. It is seen that R_opt→C as n becomes large, but that good channel performance is retained provided that $\text{> >}\text{n}\text{T}$.     

Data-unit-size distribution model when message segmentations occur

This paper proposes a data-unit-size distribution model to represent the message segmentation function implemented in many protocols, such as TCP and RLC, that allows a sender to divide a message larger than the payload size ?_d into multiple packets. To develop a Markov chain for a segmented packet size sequence, we introduce an auxiliary random variable representing two packet types: body and edge packets. The body packet is defined as a segmented packet appearing between the head and penultimate packets in the original message. If a message is segmented, the edge packet is defined as the final segmented packet. If not, it is identified with the original message. The sizes of body packets are equal to ?_d, whereas those of edge packets are variable, not to exceed ?_d. Using the Markov chain, we derive analytical forms of the occurrence probability of edge packets, as well as the distribution, mean and variance of packet sizes in the steady state. The key findings from the numerical results based on traffic measurement examples include the following. (1) When Web objects embedded in static Web pages that have a long-tailed size property are transferred using TCP, the occurrence probability of edge packets is not negligible in the case of commonly used values of ?_d, such as 1460 and 2272 bytes. (2) When IP messages are transferred using RLC protocol, the occurrence probability of edge packets is small because the payload size ?_d is very small.     

Data communication channel capacity for multiple-buffered concentrators

An analytical procedure is presented to evaluate the capacity required for channels used to transmit data from multiple-buffered concentrators used in data communications networks. Three message assembly procedures are compared. The parameters considered in the analysis are queuing discipline, buffer size, and computational complexity. The influence of these factors on channel capacity is examined. It is shown that the required channel capacity C for a first-come, first-served message assembly procedure satisfies C?2 C¹, where C¹ is the lowest possible channel capacity, achieved when the incoming messages are completely packed. Other, more efficient, procedures are examined and compared.     

Defending RFID authentication protocols against DoS attacks

In this paper, we present a security weakness of a forward secure authentication protocol proposed by Tri Van Le et al. called O-FRAP which stands for Optimistic Forward secure RFID Authentication Protocol. In particular, we point out that in the O-FRAP protocol, the server can be subject to a denial-of-service attack due to a flaw in the database querying procedure. Our attack also applies to a simplified version of O-FRAP called O-RAP (Optimistic RFID Authentication Protocol) which is essentially O-FRAP but without a secret key updating procedure (and thus forward security). We then propose two improved protocols called O-FRAP⁺ and O-RAP⁺ which prevent the said denial-of-service attack. In addition, the O-FRAP⁺ protocol also addresses two security weaknesses of O-FRAP pointed out earlier by Khaled and Raphael. In terms of performance, comparing to O-FRAP, O-FRAP⁺ requires a few more computational steps but much less storage at the back-end server.     

Solutions to a class of linear-quadratic-Gaussian (LQG) stochastic team problems with nonclassical information

We consider a stochastic dynamic team problem with two controllers and nonclassical information, which can be viewed as the transmission of a garbled version of a Gaussian message over a number of noisy channels under a fidelity criterion. We show that the optimum solution (under a quadratic loss functional) consists of linearly transforming the garbled message to a certain (optimum) power level P^* and then optimally decoding it by using a linear transformation at the receiving end. The power level P^* is determined by the solution of a fifth order algebraic equation. The paper also discusses an extension of this result to the case when the channel noise is correlated with the input random variable, and shows that for the single channel case the optimum solution is again linear.     

Analysis of Practical Backoff Protocols for Contention Resolution with Multiple Servers

Backoff protocols are probably the most widely used protocols for contention resolution in multiple access channels. In this paper, we analyze the stochastic behavior of backoff protocols for contention resolution among a set of clients and servers. each server being a multiple access channel that deals with contention like an ethernet channel. We use the standard model in which each client generates requests for a given server according to a Bernoulli distribution with a specified mean. Theclient–server request rateof a system is the maximum over all client–server pairs (i, j) of the sum of all request rates associated with either clientior serverj. (Having a subunit client–server request rate is a necessary condition for stability for single-server systems.) Our main result is that any superlinear polynomial backoff protocol is stable for any multiple-server system with a subunit client–server request rate. Our result is the first proof of stability for any backoff protocol for contention resolution with multiple servers. (The multiple-server problem does not reduce to the single-server problem, because each client can only send a single message at any step.) Our result is also the first proof thatanyweakly acknowledgment based protocol is stable for contention resolution with multiple servers and such high request rates. Two special cases of our result are of interest. Hastad, Leighton, and Rogoff have shown that for a single-server system with a subunit client–server request rate anymodifiedsuperlinear polynomial backoff protocol is stable. These modified backoff protocols are similar to standard backoff protocols but require more random bits to implement. The special case of our result in which there is only one server extends the result of Hastad, Leighton, and Rogoff to standard (practical) backoff protocols. Finally, our result applies to dynamic routing in optical networks. Specifically, a special case of our result demonstrates that superlinear polynomial backoff protocols are stable for dynamic routing in optical networks.     

Robust and efficient membership management in large-scale dynamic networks

Epidemic protocols are a bio-inspired communication and computation paradigm for large-scale networked systems based on randomised communication. These protocols rely on a membership service to build decentralised and random overlay topologies. In large-scale, dynamic network environments, node churn and failures may have a detrimental effect on the structure of the overlay topologies with negative impact on the efficiency and the accuracy of applications. Most importantly, there exists the risk of a permanent loss of global connectivity that would prevent the correct convergence of applications. This work investigates to what extent a dynamic network environment may negatively affect the performance of Epidemic membership protocols. A novel Enhanced Expander Membership Protocol (EMP+) based on the expansion properties of graphs is presented. The proposed protocol is evaluated against other membership protocols and the comparative analysis shows that EMP+ can support faster application convergence and is the first membership protocol to provide robustness against global network connectivity problems.     

Position-based coding and convex splitting for private communication over quantum channels

The classical-input quantum-output (cq) wiretap channel is a communication model involving a classical sender X, a legitimate quantum receiver B, and a quantum eavesdropper E. The goal of a private communication protocol that uses such a channel is for the sender X to transmit a message in such a way that the legitimate receiver B can decode it reliably, while the eavesdropper E learns essentially nothing about which message was transmitted. The \(\varepsilon \)-one-shot private capacity of a cq wiretap channel is equal to the maximum number of bits that can be transmitted over the channel, such that the privacy error is no larger than \(\varepsilon \in (0,1)\). The present paper provides a lower bound on the \(\varepsilon \)-one-shot private classical capacity, by exploiting the recently developed techniques of Anshu, Devabathini, Jain, and Warsi, called position-based coding and convex splitting. The lower bound is equal to a difference of the hypothesis testing mutual information between X and B and the “alternate” smooth max-information between X and E. The one-shot lower bound then leads to a non-trivial lower bound on the second-order coding rate for private classical communication over a memoryless cq wiretap channel.     

Contention Resolution under Selfishness

In many communications settings, such as wired and wireless local-area networks, when multiple users attempt to access a communication channel at the same time, a conflict results and none of the communications are successful. Contention resolution is the study of distributed transmission and retransmission protocols designed to maximize notions of utility such as channel utilization in the face of blocking communications. An additional issue to be considered in the design of such protocols is that selfish users may have incentive to deviate from the prescribed behavior, if another transmission strategy increases their utility. The work of Fiat et al. (in SODA ’07, pp. 179–188, SIAM, Philadelphia 2007) addresses this issue by constructing an asymptotically optimal incentive-compatible protocol. However, their protocol assumes the cost of any single transmission is zero, and the protocol completely collapses under non-zero transmission costs. In this paper we treat the case of non-zero transmission cost c. We present asymptotically optimal contention resolution protocols that are robust to selfish users, in two different channel feedback models. Our main result is in the Collision Multiplicity Feedback model, where after each time slot, the number of attempted transmissions is returned as feedback to the users. In this setting, we give a protocol that has expected cost Θ(n+clogn) and is in o(1)-equilibrium, where n is the number of users.     

The application of wireless local area network technology to the control of mobile robots

This paper describes a communications and control infrastructure for distributed mobile robotics, which makes use of wireless local area network (WLAN) technology and Internet Protocols (IPs). The use of commercial off-the-shelf (COTS) hardware and software components, and protocols, results in a powerful platform for conducting experiments into collective or co-operative robotics. Standard Transmission Control Protocol/Internet Protocol (TCP/IP) compatible applications programming interfaces (APIs) allow for rapid and straightforward development of applications software. Further, the message bandwidth available from WLAN interfaces (1–2 Mbits/s) facilitates multi-robot experiments requiring high data rates, for instance in robot vision or navigation. The infrastructure described is equally applicable to tele-operated mobile robots.     

Integrated dynamic scheduling of hard and QoS degradable real-time tasks in multiprocessor systems

Many time-critical applications require predictable performance and tasks in these applications have deadlines to be met. For tasks with hard deadlines, a deadline miss can be catastrophic while for Quality of Service (QoS) degradable tasks (soft real-time tasks) timely approximate results of poorer quality or occasional deadline misses are acceptable. Imprecise computation and (m,k)-firm guarantee are two workload models that quantify the trade-off between schedulability and result quality. In this paper, we propose dynamic scheduling algorithms for integrated scheduling of real-time tasks, represented by these workload models, in multiprocessor systems. The algorithms aim at improving the schedulability of tasks by exploiting the properties of these models in QoS degradation. We also show how the proposed algorithms can be adapted for integrated scheduling of multimedia streams and hard real-time tasks, and demonstrate their effectiveness in quantifying QoS degradation. Through simulation, we evaluate the performance of these algorithms using the metrics – success ratio (measure of schedulability) and quality. Our simulation results show that one of the proposed algorithms, multilevel degradation algorithm, outperforms the others in terms of both the performance metrics.     

The effect of quantum noise on two different deterministic remote state preparation of an arbitrary three-particle state protocols

Multi-particle quantum state deterministic remote preparation is a fundamental and important technical branch in quantum communication. Since quantum noise is unavoidable in realistic quantum communication, it is important to analyze the effect of noise on multi-particle quantum communication protocols. In this paper, we study the effects of noise, such as amplitude damping, phase damping, bit-flip and depolarizing noises, on two deterministic remote preparation of an arbitrary three-particle state protocols, which are based on two different entangled channels, namely \(\chi \) state and Brown state. The detailed mathematical analysis shows that the output states of two deterministic remote state preparation (DRSP) protocols are the same in the same noisy environment. That is to say, in the same noisy environment, the effects of noise on two DRSP protocols are the same. This conclusion proves that these two DRSP protocols will produce the same arbitrary three-particle states in the same noise channel environment, and so that these protocols are inherently convergent and can be substituted for each other in certain circumstances. In addition, this paper also takes three-particle states \(a\left| {000} \right\rangle + b{\mathrm{e}^{ic}}\left| {111} \right\rangle \) as an example and studies the relationship between the fidelity, the target state and the size of the noise factor. The results show that if the target state can be selected, an appropriate target state can effectively resist on the bit-flip noise. If the target state cannot be selected, as the increase in the size of noise factor, the fidelities of the two DRSP schemes in the amplitude damping noise and phase damping noise are always larger than those in the bit-flip noise and depolarizing noise. This conclusion indicates that two protocols have better resistance on amplitude damping and phase damping noise than the bit-flip and depolarizing noises. These findings and analyses will provide valid help in deterministic remote preparation of an arbitrary three-particle state in a noisy environment.     

Evaluating transport protocol performance over a wireless mesh backbone

IEEE 802.11n wireless physical layer technology increases the deployment of high throughput wireless indoor mesh backbones for ubiquitous Internet connectivity at the urban and metropolitan areas. Most of the network traffic flows in today’s Internet use ‘Transmission Control Protocol’ (TCP) as the transport layer protocol. There has been extensive works that deal with TCP issues over wireless mesh networks as well as noisy wireless channels. Further, IEEE 802.11n is well known for its susceptibility to increased channel losses during high data rate communication. This paper investigates the dynamics of an end-to-end transport layer protocol like TCP in the presence of burst and correlated losses during IEEE 802.11n high data rate communication, while maintaining fairness among all the end-to-end flows. For this purpose, we evaluate four TCP variants-Loss Tolerant TCP (LT-TCP), Network Coded TCP (TCP/NC), TCP-Horizon and Wireless Control Protocol (WCP), where the first two protocols are known to perform very well in extreme lossy networks, and the last two are specifically designed for mesh networks. Our evaluation shows that WCP performs better in a IEEE 802.11n supported mesh networks compared to other three variants. However, WCP also results in negative impact at high data rates, where end-to-end goodput drops with the increase in physical data rate. The analysis of the results reveals that explicit loss notifications and flow balancing are not sufficient to improve transport protocol performance in an IEEE 802.11n supported mesh backbone, rather a specific mechanism is required to synchronize the transport queue management with lower layer scheduling that depends on IEEE 802.11n features, like channel bonding and frame aggregation. The findings of this paper give the direction to design a new transport protocol that can utilize the full capacity of IEEE 802.11n mesh backbone.     

Analysing a stream authentication protocol using model checking

In this paper, we consider how one can analyse a stream authentication protocol using model checking techniques. In particular, we will be focusing on the Timed Efficient Stream Loss-tolerant Authentication Protocol, TESLA. This protocol differs from the standard class of authentication protocols previously analysed using model checking techniques in the following interesting way: an unbounded stream of messages is broadcast by a sender, making use of an unbounded stream of keys; the authentication of the n-th message in the stream is achieved on receipt of the n+1-th message. We show that, despite the infinite nature of the protocol, it is possible to build a finite model that correctly captures its behaviour.