Search

In this article, we show that keeping track of history enables significant improvements in the communication complexity of dynamic network protocols. We present a communication optimal maintenance of a spanning tree in a dynamic network. The amortized (on the number of topological changes) message complexity is O(V), where V is the number of nodes in the network. The message size used by the algorithm is O(log ∣ID∣) where ∣ID∣ is the size of the name space of the nodes. Typically, log ∣ID∣ = O(log V). Previous algorithms that adapt to dynamic networks involved Ω(E) messages per topological change-inherently paying for re-computation of the tree from scratch. Spanning trees are essential components in many distributed algorithms. Some examples include broadcast (dissemination of messages to all network nodes), multicast, reset (general adaptation of static algorithms to dynamic networks), routing, termination detection, and more. Thus, our efficient maintenance of a spanning tree implies the improvement of algorithms for these tasks. Our results are obtained using a novel technique to save communication. A node uses information received in the past in order to deduce present information from the fact that certain messages were NOT sent by the node's neighbor. This technique is one of our main contributions. [ABSTRACT FROM AUTHOR]

A fundamental problem of distributed computing is that of simulating a secure broadcast channel, within the setting of a point-to-point network. This problem is known as Byzantine Agreement (or Generals) and has been the focus of much research. Lamport et al. [1982] showed that in order to achieve Byzantine Agreement in the plain model, more than two thirds of the participating parties must be honest. They further showed that by augmenting the network with a public-key infrastructure for digital signatures, it is possible to obtain protocols that are secure for any number of corrupted parties. The problem in this augmented model is called "authenticated Byzantine Agreement". In this article, we consider the question of concurrent, parallel and sequential composition of authenticated Byzantine Agreement protocols with a single common setup. We present surprising impossibility results showing that: (1) Authenticated Byzantine Agreement protocols that remain secure under parallel or concurrent composition (even for just two executions) and tolerate a third or more corrupted parties, do not exist. (2) Deterministic authenticated Byzantine Agreement protocols that run for r rounds and tolerate a third or more corrupted parties, can remain secure for at most 2r -- 1 sequential executions. In contrast, we present randomized protocols for authenticated Byzantine Agreement that remain secure under sequential composition, for any polynomial number of executions. We exhibit two such protocols. In the first protocol, an honest majority is required. In the second protocol, any number of parties may be corrupted; however, the complexity of the protocol is in the order of 2n ·n! for n parties. In order to have this polynomial in the security parameter k (used for the signature scheme in the protocol), this requires the overall number of parties to be limited to O(log k/ log log k). The above results are achieved due to a new protocol for authenticated Byzantine Generals for three parties that can tolerate any number of faulty parties and composes sequentially. Finally, we show that when the model is further augmented so that in each session, all the participating parties receive a common session identifier that is unique to that session, then any polynomial number of authenticated Byzantine agreement protocols can be concurrently executed, while tolerating any number of corrupted parties. [ABSTRACT FROM AUTHOR]

There has been considerable recent interest in probabilistic packet marking schemes for the problem of tracing a sequence of network packets back to an anonymous source. An important consideration for such schemes is the number of packet header bits that need to be allocated to the marking protocol. Let b denote this value. All previous schemes belong to a class of protocols for which b must be at least log n, where n is the number of bits used to represent the path of the packets. In this article, we introduce a new marking technique for tracing a sequence of packets sent along the same path. This new technique is effective even when b =1. In other words, the sequence of packets can be traced back to their source using only a single bit in the packet header. With this scheme, the number of packets required to reconstruct the path is O(22n), but we also show that Ω(2n) packets are required for any protocol where b =1. We also study the trade-off between b and the number of packets required. We provide a protocol and a lower bound that together demonstrate that for the optimal protocol, the number of packets required (roughly) increases exponentially with n, but decreases doubly exponentially with b. The protocol we introduce is simple enough to be useful in practice. We also study the case where the packets are sent along k different paths. For this case, we demonstrate that any protocol must use at least log(2k -1) header bits. We also provide a protocol that requires log(2k +1)header bits in some restricted scenarios. This protocol introduces a new coding technique that may be of independent interest. [ABSTRACT FROM AUTHOR]

Presents a study which showed how methods of automated reasoning can be used to prove properties of network routing protocols. Correctness of the asynchronous distributed Bellman-Ford protocol as specified in the Internet Engineering Task Force Routing Information Protocol standard; Verification of networking standards; Approaches to verifying algorithms; Characteristics of routing protocol used in the Internet.

Describes a multilink multisource model of the Transmission Control Protocol (TCP) Vegas congestion control mechanism. Background on TCP; Objective of Vegas; Interpretation of the Vegas algorithm; Examination of the phenomenon of persistent congestion.

Presents information on a study which examined an on-line problem that is motivated by the networking problem of dynamically adjusting delays of acknowledgments in the Transmission Control Protocol. Usefulness of applying packet arrival time prediction to the problem; Description of the algorithms.

Byzantine Fault Tolerant (BFT) protocols have the ability to work correctly even when up to a threshold f of system servers are compromised. This makes them appealing for the construction of critical systems connected to the Internet, which are constantly a target for cyber attacks. BFT protocols differ based on the kind of application, deployment settings, performance, access control mechanisms, number of servers in the system, and protocol implementation. The large number of protocols present in the literature and their differences make it difficult for a system builder to choose the solution that best satisfies the requirements of the system that he wants to build. In particular, the main difference among BFT protocols lies in their system models: server-side versus client-side. In the server-side model each client relies on the system to consistently order and replicate updates, while in the client-side model each client actively participates in the protocol. In this article, we classify BFT protocols as server-side or client-side. We analyze the trade-offs between the two models, describe systems that use these models and the trade-offs they choose, highlight the research gaps, and provide guidelines to system builders in order to choose the solution that best satisfies their needs. [ABSTRACT FROM AUTHOR]

Wireless self-organizing networks (WSONs) have attracted considerable attention from the network research community; however, the key for their success is the rigorous validation of the properties of the network protocols. Applications of risk or those demanding precision (like alert-based systems) require a rigorous and reliable validation of deployed network protocols. While the main goal is to ensure the reliability of the protocols, validation techniques also allow the establishment of their correctness regarding the related protocols' requirements. Nevertheless, even if different communities have carried out intensive research activities on the validation domain, WSONs still raise new issues for and challenging constraints to these communities. We thus, advocate the use of complementary techniques coming from different research communities to efficiently address the validation of WSON protocols. The goal of this tutorial is to present a comprehensive review of the literature on protocol engineering techniques and to discuss difficulties imposed by the characteristics of WSONs on the protocol engineering community. Following the formal and nonformal classification of techniques, we provide a discussion about components and similarities of existing protocol validation approaches. We also investigate how to take advantage of such similarities to obtain complementary techniques and outline new challenges. [ABSTRACT FROM AUTHOR]

During the past ten years, the field of multiple-access communication has developed into a major area of both practical and theoretical interest within the field of computer communications. The multiple-access problem arises from the necessity of sharing a single communication channel among a community of distributed users. The distributed algorithm used by the stations to share the channel is known as the multiple-access protocol. In this paper we examine the multiple-access problem and various approaches to its resolution. In this survey we first define the multiple-access problem and then present the underlying issues and difficulties in achieving multiple-access communication. A taxonomy for multiple-access protocols is then developed in order to characterize common approaches and to provide a framework within which these protocols can be compared and contrasted. Different proposed protocols are then described and discussed, and aspects of their performance are examined. The use of multiple-access protocols for "real- time" or "time-constrained" communication applications, such as voice transmission, is examined next. Issues in time-constrained communication are identified, and recent work in the design of time-constrained multiple-access protocols is surveyed. [ABSTRACT FROM AUTHOR]