Recently I participated in a brain storming session on distributed communication and computation. One of the challenges we had was to figure out what were the use cases for this type of technology.
Imagine a (large) group of autonomous agents geographically dispersed within some region (e.g., on the ground). These agents are mobile, and may communicate with one another. Above the agents (e.g., in the air) are communication “collectors.” All of the agents may communicate with the collectors that are within some proximity. The collectors are also mobile so they come in and out of communication range of the agents on the ground. These collectors can consolidate information and pass it between themselves or perhaps to other receivers.
Communication may be bi-directional. Agents may receive information (instructions) from collectors which may receive it from their receivers.
None of this communication is particularly reliable, is certainly noisy, and may be subject to deliberate interference, and should not be susceptible to eavesdropping.
The information collected may be used, among other things, assess provisioning of resources, identify problems in the distribution of resources, etc. While the information transferred from the agents need not necessarily be complete, instructions to a given agent do need to be accurate.
An obvious example of this scenario is battlefield logistics: soldiers, drones, command center. Other examples might include nanobots in the human bloodstream being sensed by external monitors (that are not necessarily fixed). One can imagine sensors flowing through a network of pipelines that are being detected by planes flying over them. Many logistics problems fall into this category (imagine shipping containers being transported from one side of the world to another). Certainly these examples stress different aspects of the scenario: nanobots in a clinical setting are probably less worried about malicious interference and eavesdropping, where this may be an issue for the shipping container owner who wants to ensure that competitors are not getting competitive advantage by intercepting communication.
Here are some illustrations of this scenario:
What kind of computation might we need to perform with this scenario? Suppose we use our nanobot example. A nanobot can tell you the shape of the space near it, where it is to very fine resolution, and the time to millisecond resolution or better (it may use external signals to determine this information but as we know, these external signals may be poorly received). The nanobot can also signal information (not necessarily electromagnetically). Finally, it is possible to guide nanobot “clumps” to concentrate them in certain areas.
Finally, it may be when there is a concurrence that the nanobots have found a tumor cell, they release a toxin inside the cell to kill it.
We may be dealing with many millions of nanobots distributed throughout the body of the person injected with them. From the information received from the nanobots we can do imaging of the area they are in, extent of tumor spread, constituency of the tumor, etc.
The next scenario is from http://mfktech.wordpress.com/2010/10/12/better-mobile-video-delivery/. Content is being delivered to a consumer that is in motion passing by cell towers. The consumer is not in proximity of a single tower during the transmission; many towers may need to have the content to transmit. Access to the content is not necessarily linear. For example, imagine someone viewing a movie and rewinding, jumping to scenes, etc.
The simplest approach is to have a central repository of the content and to feed all requests to that repository. This can involve a lot of “back-haul”, network traffic traversing from the handset all the way potentially to web sites on the internet (think NetFlix or Hulu).
The next step to improve this is to place caches closer to the content. Now as a consumer passes from one tower (cache) to another (cache), it will pick up the content from the new tower. This works well if there is more than one user accessing the same piece of content.
The problem with caching the content at the towers is that each cache needs the entire content. With a coding approach, this need not be necessarily true. Instead, we code against a group of towers that will simultaneously transmit “chunks” of the cached content. As towers fade from reception, the fragments can be recovered at forward towers. The net capacity is reduced, and the bandwidth to put the “chunks” in place is reduced: A win-win combination.
With the use of coding, it is also possible to provide some content protection as well. Instead of
encoding the content, the coefficients for the coding can be encrypted. It may be possible to reduce the amount of copies that we need and still have strong encryption results. This requires some more thought.
We haven’t spoken much about computation in this paper. Clearly there are logistic optimization algorithms that might apply to the battlefield and container transport examples. The nanobots might require local consensus algorithms to decide where they are and if they have found a target cell. An interesting question is how to apply inexact algorithms: Algorithms designed to work with partial information (or inexact information) distributed among many agents. Another interesting area are distributed algorithms that work with local information to create global effect. For example, the way ants create trails optimizes the amount of distance traveled without global communication.
In this example, ants see some number of ants in front of them and end up “optimizing the path.
This short paper has tried to motivate distributing computing, communication, and storage with a number of use-cases. We are only scratching the surface.