Embedded, Everywhere A Research Agenda for Networked Systems of Embedded Computers (2001) / Chapter Skim
Currently Skimming:
5. Models of Computation
5. Models of Computation
Pages 147-171
The Chapter Skim interface presents what we've algorithmically identified as the most significant single chunk of text within every page in the chapter.
Select key terms on the right to highlight them within pages of the chapter.
From page 147... ...
The effort needed to design systems so that they can be maintained, configured, and trusted will be substantial. If EmNets are to be designed in a principled way rather than being assembled using techniques determined on a case-bycase basis and specialized to the system being built, computational models will be needed to provide a conceptual framework in which the designs can be created, thought about, and tested.
|
From page 148... ...
In particular, functioning EmNets have been and will continue to be built without complete computational models for them. However, without such models, these systems must be built in an ad hoc fashion, and problems that are not addressed by the existing models must be addressed while the system is being constructed.
|
From page 149... ...
WHAT ARE MODELS OF COMPUTATION? Existing computational models function at many different levels of abstraction; often, high-level abstractions build on simpler ones.
|
From page 150... ...
Computational models for distributed computing have followed a similar evolution. Early models were concerned with the communication of data from one cooperating computer to another.
|
From page 151... ...
For example, one of the major differences between the distributed computing model articulated by the CORBA abstractions and the model articulated in lava Remote Method Invocation is the latter's ability to pass objects, including their methods, from one participant in the network to another. This, in turn, is implementable because the system presupposes the existence of the lava Virtual Machine on all members of the system, allowing both behavior and data to be passed in the distributed system.
|
From page 152... ...
DISTRIBUTED COMPUTING MODELS: CURRENT PRACTICE While there are several models for distributed computing, nearly all of them are based on one of two underlying abstractions: distributed objects and distributed shared memory. Both provide a basis for understanding computing systems in which elements are distributed across a network and, as such, can offer a starting point for thinking about EmNets.
|
From page 153... ...
Differences such as these call into question the use of traditional distributed computing models in the domain of EmNets. At the very least, it seems clear that certain concepts that have been abstracted out of the computational model for other kinds of systems will need to be added to reach a model that is adequate for reasoning about EmNets.2 The rest of this section elaborates on some of the assumptions made in traditional models and explores why such assumptions may not be adequate for EmNets.
|
From page 154... ...
In such systems, there is a single shared repository of information objects that is accessible to all participants in the distributed system, and communication involves writing information into such spaces and allowing it to be read out by some other member of the distributed system. The shared space can be viewed as shared memory with special access operations or as a special type of distributed object.
|
From page 155... ...
All of 4For more information on BSP tthe Bulk Synchronous Parallel computing modely, see |
From page 156... ...
Since EmNets will often interact with the physical world in a way that satisfies real-time constraints, designers will require a model that has reified the notion of time and allows making design trade-offs concerning timely response. The tight coupling of EmNets to the physical world allows those systems to make use of notions of location, coloration, and proximity that are not possible in standard computational models of distributed systems.
|
From page 157... ...
Some of the components will make use of traditional computing elements with persistent storage and abundant energy supplies and will be connected by wired networks with high reliability and bandwidth. Other components will be built with specialized processors having limited processing power, will have limited or no persistent storage, will be connected using low-bandwidth wireless networking, and will have limited, self-contained power supplies.
|
From page 158... ...
Models with Resource Constraints An immediate challenge in creating a computational model adequate for EmNets is to determine the right level of data abstraction. As discussed above, existing distributed system computational models abstract 9Distributed control systems (discussed in Chapter 3)
|
From page 159... ...
Resource constraints in the network also will stretch current computational models. In the two common distributed system models, communication is abstracted almost completely out of the problem.
|
From page 160... ...
Standard formal models of distributed computing identify failures of the components (such as crash or fail-stop failures) ; failures in the communication infrastructure; and Byzantine failures, in which a component can act in random fashion (including acting like a nonfailed component that sends incorrect information)
|
From page 162... ...
Because many of the components are assumed to be unreliable, some will inevitably fail, and when they do, other parts of the system must be able to take over critical functions or compensate for the failure in some other fashion. In addition, if the components recover or are replaced, they need to continue doing what they were doing before, which may well include knowing some of the information gathered over time.
|
From page 163... ...
The transactional model of memory is very powerful because it simplifies reasoning about many types of interactions; however, implementing a transactional model of memory is quite complex and may not be possible on all of the various kinds of nodes found in EmNets. These implementation issues may make a pure transactional memory model too expensive to be used in the design of EmNets, and it might be possible to create a compromise model for these systems.
|
From page 164... ...
Especially in sensor networks, users may be more interested in receiving information about a particular event that has been detected (for example, a chemical concentration exceeding a particular threshold) or in receiving a particular set of data (for example, the chemical concentration in a particular geographical region)
|
From page 165... ...
Both likelihoods may require adding trust notions to a model for EmNets that are traditionally outside of conventional computational models. In the case of mobile code, it will often be the case that the environment into which code is moved will need to establish a trust relationship with that code.
|
From page 166... ...
However, this type of explicit synchronization is a well-known cause of bugs, the most common of which involves a single thread assuming that a piece of shared information cannot be changed over some period of time by any of the other threads of execution, even though no lock is held on the information. Similar explicit approaches to concurrency control, such as shared job queues that allow coordinating work among the different threads of execution, are also limited in scale or prone to programmer error.
|
From page 167... ...
. In a factory, the physical world is a highly constrained, well-understood environment in which the interaction is very prescribed (for example, retrieve item Y from prespecified location X.)
|
From page 168... ...
CONDUCTING RESEARCH ON MODELS AND ABSTRACTIONS Computational models are not developed in a vacuum. The computational model for EmNets will evolve as applications of the technology are developed.
|
From page 169... ...
Such a cycle can lead to rapid evolution of the model and the run-time environment in response to the rapid development of applications; however, the initial stages of building this loop will be lengthy relative to the later stages and seemingly chaotic as well, as basic assumptions are tested and computational models are in significant flux. This is not to say that the initial inquiries into computational models and their associated run-time environments will be completely unstructured.
|
From page 170... ...
170 EMBEDDED, EVERYWHERE mation needed by EmNets (for example, information about specific nodes or components) ; accordingly, some relaxation of the layering may be a fruitful area for research.
|
From page 171... ...
As people attempt to build applications of EmNets, it will be important for them to identify suspicious assumptions or counterproductive abstractions in the current computing model, and to think of alternatives that can be built into the infrastructure for the application. Many more assumptions and abstractions will be identified than have been listed here.
|
Key Terms
This material may be derived from roughly machine-read images, and so is provided only to facilitate research.
More
information on Chapter Skim is available.