For more up-to-date notes see http://www.cs.yale.edu/homes/aspnes/classes/465/notes.pdf.

Mostly we've been looking at very idealized models of distributed systems: either a SharedMemory system where processes communicate via shared objects (themselves often somewhat idealized), or a MessagePassing system where processes communicate across some underlying network with a fixed topology and a simple send/receive interface. Providing these clean interfaces is usually considered to be the job of hardware and operating system designers in the shared-memory case and network engineers in the message-passing case.

In some situations it is not possible to provide a perfect abstract network, and it may make sense to expose more of the underlying structure to applications. An example is a radio network, where instead of clean, simple point-to-point message-passing, each process has the ability to broadcast across some geographically-defined neighborhood, with the possibility of collisions between simultaneous broadcasts.

1. Basic radio network models

Typical features:

Synchrony

(It's hard to avoid collisions otherwise).

Geography

Points are embedded in some metric space (typically assumed to be the plane ℝ²), and you can hear me if and only if you are within a 1-unit radius in this space. The resulting communication graph is called a unit disk graph. (More sophisticated models take into account geography and transmission power, we won't talk about these.)

Broadcasts with shadowing and collisions

Everybody in my neighborhood hears every message I send, unless somebody else sends a message they can hear at the same time; in the last case, either the stronger message drowns out the weaker one (shadowing), or no message at all is received (collision). Collisions can generally be detected by the receiver, but not necessarily by senders (e.g., if the senders are more than 1 unit away from each other). Shadowing is often not detectable by receivers at all, except by comparing what messages are received to which are sent.

Power issues

Devices using radio probably aren't connected to the power grid (otherwise we could run network cables between them). So we have to worry about conserving our batteries by minimizing the number and strength of transmissions. On the other side, we may also be able adjust the effective communication graph by adjusting transmission power (for example, by throttling back to only talk to very close nodes and thereby avoid swamping the entire neighborhood). These issues quickly get into rather detailed physics and engineering; a common abstract model is to assume that I can talk to you if the signal strength at reception is above some constant noise floor, where the signal strength is equal to my transmission strength times a distance-based attenuation factor of the form d^-α for some constant α (at least 2 by the inverse square law, but possibly as much as 6 in real-world measurements).

2. Things we want to do

Avoid collisions

This means making sure that nobody close to me broadcasts at the same time I do. Typical solution is to assign each node a color that is distinct from that of all other nodes 2 hops away or less, and do round-robin scheduling between color classes. Finding the coloring requires running a distributed algorithm of some sort (and dealing with the collisions that occur while running the algorithm). In more elaborate models we may also need to deal with interference we don't control.

Route packets

Suppose I want to simulate a standard point-to-point network. I need to figure out a way to get my packets in New Haven to my friend in Los Angeles. Normally this would involve using routing tables describing the available intermediate connections. But in a radio network I can do geometric routing, where I use the fact that each node has a location in some well-behaved space to decide where to go next. The simplest approach is greedy routing: I forward each packet to the neighbor closest to the target node's location. This works fine in dense networks, but can get stuck in local optima. A provably effective method for avoid local optima in unit-disk graphs is face routing: compute a planer subgraph of the original graph, and use maze-following tricks to guarantee that we eventually get unstuck whenever we get stuck.

Fix locations

In order to do geometric routing, we need to know where all the nodes are. If we are lucky, the nodes all possess GPS receivers and can figure it out. But if we aren't (cheap nodes, or GPS not available), we can make compute local coordinates via trilateration (like triangulation but using distances instead of angles) based on simple measures of distance obtained by measuring the signal strength of received transmissions. Finding the correct coordinates (or even a good approximation) is NP-hard in general, but there are algorithms that work well for sufficiently dense networks.

Prune excess edges

This goes by the name of topology control and is relevant both to routing and collision avoidance. The idea is that the underlying communication graph may have many more edges than we need, and these extra edges might give it properties we don't like (e.g. make it non-planar).

Deal with mobility

If nodes can move around, then topology control becomes much more exciting, and we also have to deal with building some sort of directory service to let us find where some particular node is now, or at least where we can forward its mail to.

Combine and summarize measurements

Many radio networks are sensor networks, where each node is attached to some measuring device (weather instruments, strain gages, toxin detectors) and we want to collect the data at some central location. Here there are many algorithmic issues involved in how we can cheaply gather up summary data without

There are many other issues that come up, and you can take entire courses on radio networks. Some slides from a nice tutorial for the algorithm side can be found here. (The same folks also have a more recent survey of open algorithmic issues specifically for sensor networks in particular at http://dcg.ethz.ch/publications/icdcn08.pdf.)

We'll avoid trying to compress an entire course into one lecture (or web page), but we can do an example of a simple problem that arises in radio networks that has a nice distributed-computing flavor.

3. Collision avoidance with adversaries

Here we'll use a model proposed by Seth Gilbert and Rachid Guerraoui in this paper from OPODIS 2006. We have n processes with access to a single broadcast channel (no geography), where simultaneous broadcasts cause either shadowing or collisions. One of the players (Collin) is evil, and wants to prevent the other players from communicating: he does so by injecting powerful messages that shadow the messages of the other players (the model in the paper allows for collisions, but mere collisions are not as useful to Collin); it is assumed however that all players receive the same message as a result (so, for example, the transmitter can in fact detect shadowing—this assumption may not be entirely plausible with real radio hardware).

The other players (Alice and Bob in the 3-player case) are not evil, and want to communicate with each other despite the evil player Collin's interference. To keep Collin from jamming every transmission, we give him a limited message budget: he can only send β messages before his batteries run down. We assume Collin is the usual powerful adversary with total knowledge of the other players' protocols and unlimited computational power: in particular, he can always successfully spoof messages from either player.

We now want to solve the following 3-player game: Alice and Bob start with values v_a and v_b drawn from the range 1..V, where V > 1 is known to both players. After finitely many rounds of communication, we want Alice and Bob to output the values v_b and v_a respectively (demonstrating successful communication) and terminate. It is assumed that Alice and Bob don't know Collin's message budget β, but that they each have a message budget β+Δ > β. Our goal is to stay within budget while minimizing the number of rounds.

3.1. Upper bound

Here we start with only one-way communication, where Alice sends a message to Bob and Bob is silent. The key idea is that Collin can't fake silence, so Alice can send v_a by not sending messages (and detecting when Collin fakes a message instead).

3.1.1. One-bit protocol

Use two rounds:

1. Alice sends 1 if her bit is 1, sends nothing otherwise. Bob interprets any round-1 message as a 1, and silence as a 0.

2. Alice sends veto if Collin jammed her in round 1. Bob ignores any vetoed bits.

Three possible outcomes:

No jamming

Bob receives the but and it isn't vetoed. Collin spends 0 messages and Alice at most 1.

Bit is 0

Collin can jam by sending a message in round 1, forcing Alice to veto. No bit transmitted, Collin and Alice both pay 1.

Bit is 1

Now Collin jams by sending a veto message. No bit transmitted, and again Collin and Alice both pay 1.

This continues until Collin runs out of bullets; we finish in 2β+2 rounds.

3.1.2. (lg V)-bit protocol

Use the same protocol, but switch to the next bit in v_a after each successful bit transmission. This takes 2β + 2 lg V rounds (since we need 2 lg V rounds with no interference). The message budget for Alice is β + lg V. (The paper gives slower protocols that tolerate a smaller message budget β+Δ, but the cost goes up fast as Δ drops below lg V.)

3.1.3. Bidirectional protocol

Alice transmits first, then Bob when Alice is done. Collin can split his β messages between the two protocols, but the total cost is still only (2β₁ + 2 lg V) + (2β₂ + 2 lg V) = 2β + 4 lg V.

3.2. Lower bound

Amazingly, the upper bound is almost optimal: the paper shows a lower bound of 2β + (lg V)/2 rounds for bidirectional communication with no restriction on Alice and Bob's message budget, using techniques vaguely resembling the FischerLynchPaterson bound. We won't do this in class.

---

CategoryDistributedComputingNotes