We study the problems of failure detection and consensus in asynchronous systems in which processes may crash and recover, and links may lose messages. We first propose new failure detectors that are particularly suitable to the crash-recovery model. We next determine under what conditions stable storage is necessary to solve consensus in this model. Using the new failure detectors, we give two consensus algorithms that match these conditions: one requires stable storage and the other does not. Both algorithms tolerate link failures and are particularly efficient in the runs that are most likely in practice - those with no failures or failure detector mistakes. In such runs, consensus is achieved within 3d time and with 4n messages, where d is the maximum message delay and n is the number of processes in the system.

We study the problem of achieving reliable communication with quiescent algorithms (i.e., algorithms that eventually stop sending messages) in asynchronous systems with process crashes and lossy links. We first show that it is impossible to solve this problem without failure detectors. We then show that, among failure detectors that output lists of suspects, the weakest one that can be used to solve this problem is <>P, a failure detector that cannot be implemented. To overcome this difficulty, we introduce an implementable failure detector called Heartbeat and show that it can be used to achieve quiescent reliable communication. Heartbeat is novel: in contrast to typical failure detectors, it does not output lists of suspects and it is implementable without timeouts. With Heartbeat, many existing algorithms that tolerate only process crashes can be transformed into quiescent algorithms that tolerate both process crashes and message losses. This can be applied to consensus, atomic broadcast, k-set agreement, atomic commitment, etc.

Keywords: Byzantine agreement; computer networks - Protocols; computer systems, digital; Distributed; distributed consensus protocols; probabilistic failure; probability - Applications; reliable computing; stopping times; theory; verification

We introduce the concept of unreliable failure detectors and study how they can be used to solve Consensus in asynchronous systems with crash failures. We characterise unreliable failure detectors in terms of two properties - completeness and accuracy. We show that Consensus can be solved even with unreliable failure detectors that make an infinite number of mistakes, and determine which ones can be used to solve Consensus despite any number of crashes, and which ones require a majority of correct processes. We prove that Consensus and Atomic Broadcast are reducible to each other in asynchronous systems with crash failures; thus the above results also apply to Atomic Broadcast. A companion paper shows that one of the failure detectors introduced here is the weakest failure detector for solving Consensus [CHT92].

Keywords: design; management; performance

We describe algorithms for finding shortest paths and distances in a planar digraph which exploit the particular topology of the input graph. An important feature of our algorithms is that they can work in a dynamic environment, where the cost of any edge can be changed or the edge can be deleted. For outerplanar digraphs, for instance, the data structures can be updated after any such change in only O(logn) time, where n is the number of vertices of the digraph. We also describe the first parallel algorithms for solving the dynamic version of the shortest path problem. Our results can be extended to hold for digraphs of genus o(n).

Unlike static networks, ad-hoc networks have no spatial hierarchy and suffer from frequent link failures which prevent mobile hosts from using traditional routing schemes. Under these conditions, mobile hosts must find routes to destinations without the use of designated routers and also must dynamically adapt the routes to the current link conditions. This paper proposes a distributed adaptive routing protocol for finding and maintaining stable routes based on signal strength and location stability in an ad-hoc network and presents an architecture for its implementation. (Also cross-referenced as UMIACS-TR-96-34)

Keywords: Consensus / Broadcast

Keywords: concurrency control; distributed deadlock detection algorithm; distributed processing; loosely connected; probes; state machines; system recovery

The research presented in this dissertation deals with the following performance issues in mobile wireless networks: recovery, location management and routing. The mobile wireless environment poses challenging fault-tolerant data management problems due to the mobility of the users, limited bandwidth on the wireless link, and power restrictions on the mobile hosts. Thus, traditional fault-tolerance schemes cannot be directly applied to these systems. To this effect, extensions to existing traditional recovery schemes are presented whichsuit this environment. Analytical models are built to analyze the performance of these schemes to determine those environments where a particular recovery scheme is best suited. The trade-off parameters to evaluate the recovery scheme are identified. It is determined that in addition to the failure rate of the host, the performance of a recovery scheme depended on the mobility of the hosts and the wireless bandwidth.

In order to communicate with a user, one needs to know their location. The network thus faces a problem of continuously keeping track of the location of every user. An important issue in mobile wireless networks is the design and analysis of location management schemes. This dissertation presents the design and analysis of centralized and distributed location management schemes. Significant performance improvements are obtained over existing protocols.

Dynamic mobile wireless networks consist of mobile hosts which can communicate with each other over the wireless links (direct or indirect) without any static network interaction. In such networks the mobile host has the capability to communicate directly with another mobile host in its vicinity. The mobile hosts also have the capability to forward (relay) packets. The problem in hand is the complexity of updating the routing information in such a dynamic network. The dynamism in the network is due to host mobility, and disconnections. This dissertation presents a cluster-based methodology for routing in such dynamic networks. Algorithms for cluster creation and maintenance are presented and analyzed. Compared to existing and conventional routing protocols, the proposed cluster-based approach incurs lower overhead during topology updates and also provides quicker reconvergence.

Keywords: fault tolerance; interactive consistency; network communications; network operating systems; reliability

Rumor mongering (also known as gossip) is an epidemiological protocol that implements broadcasting with a reliability that can be very high. Rumor mongering is attractive because it is generic, scalable, adapts well to failures and recoveries, and has a reliability that gracefully degrades with the number of failures in a run. In this paper we present a protocol that superficially resembles rumor mongering but is deterministic. We show that this new protocol has most of the same attractions as rumor mongering. The one attraction that rumor mongering has - namely graceful degradation - comes at a high cost in terms of the number of messages sent. We compare the two approaches both at an abstract level and in terms of how they perform in an Ethernet.

Ethernet is a branching broadcast communication system for carrying digital data packets among locally distributed computing stations. The packet transport mechanism provided by Ethernet has been used to build systems which can be viewed as either local computer networks or loosely coupled multiprocessors.

An Ethernet's shared communication facility, its Ether, is a passive broadcast medium with no central control. Coordination of access to the Ether for packet broadcasts is distributed among the contending transmitting stations using controlled statistical arbitration.

Switching of packets to their destinations on the Ether is distributed among the receiving stations using packet address recognition. Design principles and implementation are described, based on experience with an operating Ethernet of 100 nodes along a kilometer of coaxial cable. A model for estimating performance under heavy loads and a packet protocol for error controlled communication are included for completeness.

Keywords: broadcast; broadcast communication; communication; computer networks; computer systems, digital - Real Time Operation; computers - Data Communication Systems; data transmission; digital communication systems; distributed communication; distributed computing; distributed control; Ethernet; LANs; multiprocessing; multiprocessors; networks; operating; packet switching; statistical arbitration; switching systems

Moving toward the integration of driver-vehicle-infrastructure technology based on data from Swedish field trials

Keywords: automotive electronics; Autonomous intelligent cruise control; Communication; Computer applications; Control systems; Driver vehicle infrastructure; driver-vehicle-; infrastructure; Intelligent cruise control; intelligent cruise control system; Intelligent transportation systems; intelligent transportation systems; Motor transportation; one-directional short-; range system; road vehicles; Roadside information; Speed control; traffic signals; Vehicles; velocity control

Keywords: design; performance; reliability

Reliable broadcast protocols are important tools in distributed and fault-tolerant programming. They are useful for sharing information and for maintaining replicated data in a distributed system. However, a wide range of such protocols has been proposed. These protocols differ in their fault tolerance and delivery ordering characteristics. There is a tradeoff between the cost of a broadcast protocol and how much ordering it provides. It is, therefore, desirable to employ protocols that support only a low degree of ordering whenever possible. This dissertation presents techniques for deciding how strongly ordered a protocol is necessary to solve a given application problem. We show that there are two distinct classes of application problems: problems that can be solved with efficient, asynchronous protocols, and problems that require global ordering. We introduce the concept of a linearization function that maps partially ordered sets of events to totally ordered histories. We show how to construct an asynchronous implementation that solves a given problem if a linearization function for it can be found. We prove that in general the question of whether a problem has an asynchronous solution is undecidable. Hence there exists no general algorithm that would automatically construct a suitable linearization function for a given problem. Therefore, we consider an important subclass of problems that have certain commutativity properties. We present techniques for constructing asynchronous implementations for this class. These techniques are useful for constructing efficient asynchronous implementations for a broad range of practical problems.

Intelligent Mobile Information Systems support information-centered applications that require support for a large number of distributed mobile users collaborating on a common mission and with interests in a common situation domain. A mobile user operating in the field changes location, consumes resources, investigates situations “on the horizon,” and performs other incrementally evolving activities. A mobile user's information needs are therefore continually evolving in a neighborhood of interrelated data centered on the user's current location. Broadcast data dissemination is most effective when each broadcast information packet has multiple interested parties. To maximize the value of multicast dissemination, we dynamically cluster similar user profiles into aggregate user classifications that are served by independent multicast channels of custom information packets. Mobile user locations are also continuously tracked and mapped onto a cartographic representation of the real scenario. Spatial proximity between users is then computed by taking into account real boundaries as described in the cartographic map. Spatial information and spatial relationships among mobile users are then provided to the clustering algorithm with an eventual improved quality of the disseminated data.