Information about http://www.cs.washington.edu/homes/tom/pubs/hotos01.pdf
Systems Directions for Pervasive…
Tags: adam macbeth, ben hendrickson, brian bershad, comput, computing devices, computing environment, david wetherall, electronic publishing, eric lemar, gaetano borriello, janet davis, networking infrastructure, pervasive computing, robert grimm, stems, steven gribble, swanson, tier applications, tions, tom anderson,Pages: 5
Language: english
Created: Sun Mar 17 19:16:00 2002
Display cached document
Page 1
Page 2
Page 3
Page 4
Page 5
Systems Directions for Pervasive Computing
Robert Grimm, Janet Davis, Ben Hendrickson, Eric Lemar, Adam MacBeth,
Steven Swanson, Tom Anderson, Brian Bershad, Gaetano Borriello,
Steven Gribble, David Wetherall
University of Washington
one@cs.washington.edu
Abstract tions are email for communication and the World Wide Web
as a medium for electronic publishing and as a client inter-
Pervasive computing, with its focus on users and their tasks face to multi-tier applications.
rather than on computing devices and technology, provides
This lack of applications is directly related to the fact that
an attractive vision for the future of computing. But, while
it is difficult to design, build, and deploy applications in a
hardware and networking infrastructure to realize this vi-
pervasive computing environment. The pervasive comput-
sion are becoming a reality, precious few applications run
ing space has been mapped as a combination of mobile and
in this infrastructure. We believe that this lack of applica-
stationary devices that draw on powerful services embedded
tions stems largely from the fact that it is currently too hard
in the network to achieve users' tasks [9]. The result is a gi-
to design, build, and deploy applications in the pervasive
ant, ad-hoc distributed system, with tens of thousands of de-
computing space.
vices and services coming and going. Consequently, the key
In this paper, we argue that existing approaches to dis-
challenge for developers is to build applications that con-
tributed computing are flawed along three axes when ap-
tinue to provide useful services, even if devices are roaming
plied to pervasive computing; we sketch out alternatives
across the infrastructure and if the network provides only
that are better suited for this space. First, application data
limited services, or none at all.
and functionality need to be kept separate, so that they can
evolve gracefully in a global computing infrastructure. Sec- As part of our research into pervasive computing, we
ond, applications need to be able to acquire any resource are building one.world , a system architecture for pervasive
they need at any time, so that they can continuously pro- computing [14]. Based on our experiences with this archi-
vide their services in a highly dynamic environment. Third, tecture, we believe that existing distributed computing tech-
pervasive computing requires a common system platform, nologies are ill-suited to meet this challenge. This is not to
allowing applications to be run across the range of devices say that discovery services [1, 2, 8] or application-aware
and to be automatically distributed and installed. adaptation [19] are not useful in a pervasive computing en-
vironment. On the contrary, we consider them clearly ben-
eficial for pervasive computing applications. However, they
1. Introduction are not sufficient to successfully design, build, and deploy
applications in the pervasive computing space.
Pervasive computing [10, 26] promises a computing infras- Moreover, we argue that current approaches to building
tructure that seamlessly and ubiquitously aids users in ac- distributed applications are deeply flawed along three axes,
complishing their tasks and that renders the actual com- which -- to express their depth -- we call fault lines. In
puting devices and technology largely invisible. The basic the rest of this paper, we explore the three fault lines in de-
idea behind pervasive computing is to deploy a wide va- tail; they are summarized in Table 1. First, Section 2 makes
riety of smart devices throughout our working and living our case against distributed objects and outlines a more ap-
spaces. These devices coordinate with each other to provide propriate approach to integrating application data and func-
users with universal and immediate access to information tionality. Next, Section 3 discusses the need to write appli-
and support users in completing their tasks. The hardware cations that continuously adapt in a highly dynamic envi-
devices and networking infrastructure necessary to realize ronment. Finally, Section 4 argues for a common pervasive
this vision are increasingly becoming a reality, yet precious computing platform that spans the different classes of de-
few applications run in this infrastructure. Notable excep- vices. We conclude this paper in Section 5.
Problem Cause Proposed Solution
Objects do not scale well across Encapsulation of data and function- Keep data and functionality sepa-
large, wide-area distributed sys- ality within a single abstraction rate
tems
Programming for change: Applica-
Availability of application services Transparency in a highly dynamic tions need to be able to acquire any
is limited or intermittent environment resource they need at any time
Programming and distributing ap- Common system platform with an
Heterogeneity of devices and sys-
plications is increasingly unman- integrated API and a single binary
tem platforms
ageable format
Table 1. Overview of the three fault lines discussed in this paper, listing the problem, cause, and
proposed solution for each fault line.
2. Data and Functionality ready rely on mobile code for their services. For exam-
ple, Bayou propagates updates as procedures and not sim-
The first fault line concerns the relationship between data ply as data [23]. The Oracle8i database not only supports
and functionality and how they are represented. Several dis- SQL stored procedures, but also includes a fully featured
tributed systems, such as Legion [16] or Globe [25], are tar- Java virtual machine [11]. On the other hand, mobile code
geted at a global computing environment and have explored systems have seen limited success in the absence of a stan-
the use of objects as the unifying abstraction for both data dard data model and the corresponding data management
and functionality. We are skeptical about this use of objects solutions. For example, while many projects have explored
for distributed computing for two reasons. mobile agents [18], they have not been widely adopted, in
First, objects as an encapsulation mechanism are based part because they lack storage management. Java, which
on two assumptions: (1) Implementation and data layout was originally marketed as a mobile code platform for the
change more frequently than an object's interface, and (2) Internet, has been most successful in the enterprise, where
it is indeed possible to design interfaces that accommo- access to databases is universal [21].
date different implementations and hold up as a system The result is considerable tension between integrating
evolves. However, these assumptions do not hold for a data and functionality too tightly -- in the form of objects
global distributed computing environment. Increasingly, -- and not integrating them tightly enough. one.world re-
common data formats, such as HTML or PNG, are specified solves this tension by keeping data and functionality sep-
by industry groups or standard bodies, notably the World arate and by introducing a new, higher-level abstraction to
Wide Web Consortium, and evolve at a relatively slow pace. group the two. In our architecture, data is represented by tu-
In contrast, application vendors compete on functionality, ples, which essentially are records with named and option-
leading to considerable differences in application interfaces ally typed fields, while functionality is provided by compo-
and implementations and a much faster pace of innovation. nents, which implement units of functionaly. Environments
Second, it is preferable to store and communicate data serve as the new unifying abstraction: They are contain-
instead of objects, as it is generally easier to access passive ers for stored tuples, components, and other environments,
data rather than active objects. In particular, safe access to providing a combination of the roles served by file system
active objects in a distributed system raises important is- directories and nested processes [5, 12, 24] in more tradi-
sues, notably system security and resource control, that are tional operating systems. Environments make it possible to
less difficult to address when accessing passive data. This group data and functionality when necessary. At the same
is clearly reflected in today's Internet: Access to regular time, they allow for data and functionality to evolve sepa-
HTML or PDF documents works well, while active content rately and for applications to store and exchange just data,
results in an ever continuing string of security breaches [17]. thus avoiding the two problems associated with objects dis-
Based on these two realizations, we argue that data and cussed above.
functionality should be kept separate rather than being en- To summarize, we are arguing that data and functionality
capsulated within objects. need to be supported equally well in large distributed sys-
At the same time, data and functionality depend on each tems, yet also need to be kept separate. We are not arguing
other, especially when considering data storage and mo- that object-oriented programming is not useful. one.world is
bile code. On one hand, data management systems al- implemented mostly in Java and makes liberal use of object-
oriented language features such as inheritance to provide its their data between nodes. Checkpointing and migration are
functionality.1 At the same time, our architecture clearly useful primitives for building failure resilient applications
separates data and functionality, using tuples to represent and for improving performance in a distributed system. Fur-
data and components to express functionality. thermore, migration is attractive for applications that follow
a user as she moves through the physical world.
3. Programming for Change Checkpointing and migration affect an environment and
its contents, including all nested environments. Checkpoint-
ing captures the execution state of all components in an
The second fault line is caused by transparent access to re- environment tree and saves that state in form of a tuple,
mote resources. By building on distributed file systems or making it possible to later restore the saved state. Migra-
remote procedure call packages, many existing distributed tion moves an environment tree, including all components
systems mask remote resources as local resources. This and stored tuples, from one device to another. Since ap-
transparency certainly simplifies application development. plications already need to be able to dynamically acquire
From the programmer's viewpoint, accessing a remote re- resources they need, both checkpointing and migration es-
source is as simple as a local operation. However, this chew transparency and are limited to the resources con-
comes at a cost in failure resilience and service availability. tained in the environment tree being checkpointed or mi-
Network connections and remote servers may fail. Some grated. As a result, their implementation in one.world can
services may not be available at all in a given environ- avoid the complexities typically associated with full pro-
ment. As a result, if a remote service is inaccessible or un- cess checkpointing and migration [18], and migration in the
available, distributed applications cannot provide their ser- wide area becomes practical.
vices, because they were written without the expectation of To summarize, the main idea behind programming for
change. change is to force developers to build applications that bet-
We believe that this transparency is misleading in a per- ter cope with a highly dynamic environment, while also pro-
vasive computing environment, because it encourages a pro- viding primitives that make it easier to implement applica-
gramming style in which a failure or the unavailability of a tions.
resource is viewed as an extreme case. But in an environ-
ment where tens of thousands of devices and services come
and go, the unavailability of some resource may be the com- 4. The Need for a Common Platform
mon (or at least frequent) case. We are thus advocating a
programming style that forces applications to explicitly ac- The third fault line is rooted in the considerable and inher-
quire all resources, be they local or remote, and to be pre- ent heterogeneity of devices in a pervasive computing en-
pared to reacquire them or equivalent resources at any time. vironment. Computing devices already cover a wide range
In one.world , applications need to explicitly bind all of platforms, computing power, storage capacity, form fac-
resources they use, including storage and communication tors, and user interfaces. We expect this heterogeneity to
channels. Leases are used to control such bindings and, increase over time rather than decrease, as new classes of
by forcing applications to periodically renew them, provide devices such as pads or car computers become widely used.
timeouts for inaccesible or unavailable resources. While Today, applications are typically developed for specific
leases have been used in other distributed systems, such as classes of devices or system platforms, leading to separate
Jini [2], to control access to remote resources, we take them versions of the same application for handhelds, desktops,
one step further by requiring that all resources be explic- or cluster-based servers. Furthermore, applications typi-
itly bound and leased. Furthermore, resource discovery in cally need to be distributed and installed separately for each
one.world can use late binding, which effectively binds re- class of devices and processor family. As heterogeneity
sources on every use and thus reduces applications' expo- increases, developing applications that run across all plat-
sure to failures or changes in the environment [1]. forms will become exceedingly difficult. As the number of
This style of programming for change imposes a strict devices grows, explicitly distributing and installing appli-
discipline on applications and their developers. Yet, pro- cations for each class of devices and processor family will
gramming for change also presents an opportunity by en- become unmanageable, especially in the face of migration
abling system services that make it easier to build applica- across the wide area.
tions. one.world provides support for saving and restoring We thus argue for a single application programming in-
application checkpoints and for migrating applications and terface (API) and a single binary distribution format, includ-
1 Though,
ing a single instruction set, that can be implemented across
for several features, including the implementation of tuples,
mixin-based inheritance [4] and multiple dispatch as provided by Multi-
the range of devices in a pervasive computing environment.
Java [7] would have provided a better match than Java's single inheritance A single, common API makes it possible to develop appli-
and single dispatching of methods. cations once, and a single, common binary format enables
the automatic distribution and installation of applications. It development, data and functionality should be kept separate
is important to note that Java does not provide this common for pervasive computing applications as they typically need
platform. While the Java virtual machine is attractive as to evolve independently. Second, applications need to be
a virtual execution platform (and used for this purpose by explicitly programmed to gracefully handle change. While
one.world ), Java as an application platform does not meet this style of programming imposes a strict discipline on ap-
the needs of the pervasive computing space. In particular, plication developers, it also enables system services, such
Java's platform libraries are rather large, loosely integrated, as checkpointing and migration, previously not available in
and often targeted at conventional computers. Furthermore, distributed systems of this scale. Third, pervasive comput-
Java, by itself, fails to separate data and functionality and ing requires a common system platform, so that applications
does not encourage programming for change, as discussed can run across (almost) all devices in this infrastructure and
in Sections 2 and 3 respectively. can be automatically distributed and installed.
Given current hardware trends and advances in virtual We are exploring how to address these fault lines with
execution platforms, such as the Java virtual machine or one.world , a system architecture for pervasive computing.
Microsoft's common language runtime [22], we can rea- In an effort to better understand the needs of application
sonably expect that most devices can implement such a per- developers, we have taught an undergraduate course that
vasive computing platform. Devices that do not have the leverages one.world as the basis for students' projects. We
capacity to implement the full platform, such as small sen- are also building pervasive applications within our archi-
sors [15], can still interact with it by using proxies or em- tecture and are collaborating with other researchers in the
ulating the platform's networking protocols. Furthermore, department to implement additional infrastructure services
legacy applications can be integrated by communicating on top of it. Further information on one.world , including
through standard networking protocols, such as HTTP or a source distribution, is available at http://one.cs.
SOAP [3], and by exchanging data in standard formats, such washington.edu/.
as XML.
A pervasive computing platform that runs across a wide
Acknowledgments
range of devices does impose a least common denominator
on the core APIs. Applications can only assume the services
defined by the core APIs; they must implement their basic We thank David Notkin for helping us to refine our obser-
functionality within this framework. At the same time, a vations and Brendon Macmillan as well as the anonymous
common platform does not prevent individual devices from reviewers for their comments on an earlier version of this
exposing additional services to applications. It simply de- paper.
mands that additional services be treated as optional and
dynamically discovered by applications. References
As part of our research on one.world , we are exploring
how to scale a common platform across the range of de- [1] W. Adjie-Winoto, E. Schwartz, H. Balakrishnan, and J. Lil-
vices. Taking a cue from other research projects [6, 13, 15, ley. The design and implementation of an intentional naming
20], which have successfully used asynchronous events at system. In Proceedings of the 17th ACM Symposium on Op-
very different points of the device space, our architecture erating Systems Principles, pages 186201, Kiawah Island
also relies on asynchronous events to express control flow. Resort, South Carolina, Dec. 1999.
All system interfaces are asynchronous, and application [2] K. Arnold, B. O'Sullivan, R. W. Scheifler, J. Waldo, and
components interact by exchanging asynchronous events. A. Wollrath. The Jini Specification. Addison-Wesley, 1999.
The hope behind this design decision is that it will consider- [3] D. Box, D. Ehnebuske, G. Kakivaya, A. Layman,
N. Mendelsohn, H. F. Nielsen, S. Thatte, and D. Winer. Sim-
ably aid with the scalability of the architecture. one.world 's
ple object access protocol (SOAP) 1.1. W3C note, World
implementation currently runs on Windows and Linux com-
Wide Web Consortium, Cambridge, Massachusetts, May
puters, and a port to Compaq's iPAQ handheld computer is 2000.
under way. [4] G. Bracha and W. Cook. Mixin-based inheritance. In Pro-
ceedings of the ACM Conference on Object-Oriented Pro-
5. Outlook gramming Systems, Languages, and Applications '90, pages
303311, Ottawa, Canada, Oct. 1990.
[5] P. Brinch Hansen. The nucleus of a multiprogramming sys-
In this paper, we have argued that current approaches to dis- tem. Communications of the ACM, 13(4):238241, 250,
tributed computing are ill-suited for the pervasive comput- Apr. 1970.
ing space and have identified three fault lines of existing dis- [6] P. Chou, R. Ortega, K. Hines, K. Partridge, and G. Borriello.
tributed systems. First, while object-oriented programming ipChinook: An integrated IP-based design framework for
continues to provide an attractive paradigm for application distributed embedded systems. In Proceedings of the 36th
ACM/IEEE Design Automation Conference, pages 4449, 1999 USENIX Annual Technical Conference, pages 199
New Orleans, Louisiana, June 1999. 212, Monterey, California, June 1999.
[7] C. Clifton, G. T. Leavens, C. Chambers, and T. Millstein. [21] A. Radding. Java emerges as server-side standard. Informa-
MultiJava: Modular open classes and symmetric multiple tionWeek, (987):121128, May 22, 2000.
dispatch for Java. In Proceedings of the ACM Conference [22] J. Richter. Microsoft .NET framework delivers the platform
on Object-Oriented Programming Systems, Languages, and for an integrated, service-oriented web. MSDN Magazine,
Applications '00, pages 130145, Minneapolis, Minnesota, 15(9):6069, Sept. 2000.
Oct. 2000. [23] D. B. Terry, M. M. Theimer, K. Petersen, A. J. Demers, M. J.
[8] S. E. Czerwinski, B. Y. Zhao, T. D. Hodes, A. D. Joseph, and Spreitzer, and C. H. Hauser. Managing update conflicts in
R. H. Katz. An architecture for a secure service discovery Bayou, a weakly connected replicated storage system. In
service. In Proceedings of the 5th ACM/IEEE International Proceedings of the 15th ACM Symposium on Operating Sys-
Conference on Mobile Computing and Networking, pages tems Principles, pages 172183, Copper Mountain Resort,
2435, Seattle, Washington, Aug. 1999. Colorado, Dec. 1995.
[9] M. L. Dertouzos. The future of computing. Scientific Amer- [24] P. Tullmann and J. Lepreau. Nested Java processes: OS
ican, 281(2):5255, Aug. 1999. structure for mobile code. In Proceedings of the 8th ACM
[10] M. Esler, J. Hightower, T. Anderson, and G. Borriello. Next SIGOPS European Workshop, pages 111117, Sintra, Por-
century challenges: Data-centric networking for invisible tugal, Sept. 1998.
computing. In Proceedings of the 5th ACM/IEEE Interna- [25] M. van Steen, P. Homburg, and A. S. Tanenbaum. Globe: A
tional Conference on Mobile Computing and Networking, wide-area distributed system. IEEE Concurrency, 7(1):70
pages 256262, Seattle, Washington, Aug. 1999. 78, 1999.
[11] S. Feuerstein. Guide to Oracle8i Features. O'Reilly, Oct. [26] M. Weiser. The computer for the twenty-first century. Sci-
1999. entific American, 265(3):94104, Sept. 1991.
[12] B. Ford, M. Hibler, J. Lepreau, P. Tullmann, G. Back, and
S. Clawson. Microkernels meet recursive virtual machines.
In Proceedings of the 2nd USENIX Symposium on Operating
Systems Design and Implementation, pages 137151, Seat-
tle, Washington, Oct. 1996.
[13] S. D. Gribble, E. A. Brewer, J. M. Hellerstein, and D. Culler.
Scalable, distributed data structures for internet service con-
struction. In Proceedings of the 4th USENIX Symposium on
Operating Systems Design and Implementation, pages 319
332, San Diego, California, Oct. 2000.
[14] R. Grimm, T. Anderson, B. Bershad, and D. Wetherall. A
system architecture for pervasive computing. In Proceedings
of the 9th ACM SIGOPS European Workshop, pages 177
182, Kolding, Denmark, Sept. 2000.
[15] J. Hill, R. Szewczyk, A. Woo, S. Hollar, D. Culler, and
K. Pister. System architecture directions for networked sen-
sors. In Proceedings of the 9th ACM International Confer-
ence on Architectural Support for Programming Languages
and Operating Systems, pages 93104, Cambridge, Mas-
sachusetts, Nov. 2000.
[16] M. Lewis and A. Grimshaw. The core Legion object model.
In Proceedings of the Fifth IEEE International Symposium
on High Performance Distributed Computing, pages 551
561, Syracuse, New York, Aug. 1996.
[17] G. McGraw and E. W. Felten. Securing Java: Getting Down
to Business with Mobile Code. Wiley Computer Publishing,
John Wiley & Sons, 1999.
[18] D. Miloji iŽ , F. Douglis, and R. Wheeler, editors. Mobility--
cc
Processes, Computers, and Agents. ACM Press. Addison-
Wesley, Feb. 1999.
[19] B. D. Noble, M. Satyanarayanan, D. Narayanan, J. E. Tilton,
J. Flinn, and K. R. Walker. Agile application-aware adapta-
tion for mobility. In Proceedings of the 16th ACM Sym-
posium on Operating Systems Principles, pages 276287,
Saint-Malo, France, Oct. 1997.
[20] V. S. Pai, P. Druschel, and W. Zwaenepoel. Flash: An
efficient and portable Web server. In Proceedings of the