|
 |
 |
|
|
 |
Student Publications
Author: Festus Olubukunmi Ajibuwa
Title:
Alternative Computer Paradigms
Area:
Country :
Profile:
Program:
Available for Download:
Yes
Sharing knowledge is a vital component in
the growth and advancement of our society
in a sustainable and responsible way. Through
Open Access, AIU and other leading institutions
through out the world are tearing down the
barriers to access and use research literature.
Our
organization is interested in the dissemination
of advances in scientific research fundamental
to the proper operation of a modern society,
in terms of community awareness, empowerment,
health and wellness, sustainable development,
economic advancement, and optimal functioning
of health, education and other vital services.
AIU’s mission
and vision is consistent with
the vision expressed in the Budapest Open
Access Initiative and Berlin Declaration
on Open Access to Knowledge in the Sciences
and Humanities. Do you have something you
would like to share, or just a question
or comment? We would be happy to hear from
you, please use the Request Info link below.
For more information on the AIU's Open Access
Initiative, click
here.
|
|
| |
|
|
| |
Abstract
This research work examines the future of computers, considers
Integrated Circuit technology in
the areas of how it drives computer design, and what the fundamental
limitations are. Examines
the proposed alternatives, including neurobiologically inspired
computing, DNA computing,
Tuple Board Paradigm, Mobile Computing and Quantum Computing. Views
of different schools
of thoughts, organizations, companies and Universities are
critically assessed and compiled
within this write-up.
Nowadays computers are in the centre of almost all areas of modern
society and their
computational abilities very often determine superiority of one
product with respect to another.
Traditional computers are able to deal with only finite numbers
because arithmetic developed for
infinite numbers leave undetermined many operations (e.g., -) or
represent infinite numbers
by infinite sequences of finite numbers (e.g., non-standard analysis
approaches). Thus, in spite of
the key role of infinitesimals and infinite in Physics and
Mathematics (e.g., derivatives, integrals,
and differential equations), the parts of natural sciences related
to infinite and infinitesimals
remain purely theoretical fields.
The new unconventional approach proposed very recently by the author
uses a new
computational paradigm (that is not related to traditional
non-standard analysis approaches) for
creating a new revolutionary type of computer Infinity Computer
able to store infinite, finite,
and infinitesimal numbers and to execute arithmetical operations
with all of them. The key
methodological idea is usage of a new positional system with
infinite radix allowing one to
express finite, infinite, and infinitesimal numbers in a unique
framework by a finite number of
symbols.
The Infinity Computer will have a very high impact in Computer
Science, Mathematics, Physics,
and Economics because: it gives possibilities to execute
calculations of a new type; leads to
infinite accuracy of calculus; allows people to study complex
systems where infinitesimal
changes of parameters lead to finite and infinite changes in the
output; simplifies scientific fields
(and their teaching at schools and universities) where usage of
infinity and infinitesimals is
necessary.
Toward a new computing paradigm: Views of Microsoft Developer Div
chief architect David
Vaskevitch
(Enterprise Systems Journal)
July, 1995
We live in interesting times. As with any era of profound change, we
find ourselves in need of a
new paradigm -- a paradigm not just of computing but of human
relationships on a global scale.
But a paradigm is not something you simply define in advance; it is
marked by a cultural shift in
the shared mindset. Its pieces evolve slowly until it reaches a
critical mass and points the way
into the new era. We are at that critical point: Information
technology, already undergoing
tremendous change as a result of the business process reengineering
movement, has entered into
a new era.
The need for a new computer paradigm
The CHAOS-Based Systems
A New Computing Paradigm: (Chaos-Based System That "Evolves" Answers
May Be
Alternative to Current Computers)
Science Daily
2
A revolutionary new computing technique that
uses a network of chaotic elements to "evolve" its
answers could provide an alternative to the digital computing
systems widely used today.
Described for the first time in the September 7 issue of Physical
Review Letters this "dynamics-
based computation" may be well suited for optical computing using
ultra-fast chaotic lasers and
computing with silicon/neural tissue hybrid circuitry.
The system has so far demonstrated an ability to handle a wide range
of common operations,
including addition and multiplication, as well as Boolean logic and
more sophisticated operations
such as finding the least common multiplier in a sequence of
integers. Because it depends on
interaction among its coupled elements, the system is naturally
parallel.
"We have shown that this can be done, but we've only seen the tip of
the iceberg," said Dr.
William L. Ditto, professor of physics at the Georgia Institute of
Technology. "This is a glimpse
of how we can make common dynamic systems work for us in a way
that's more like how we
think the brain does computation. It's an entirely new computing
paradigm."
For many years, scientists have observed the rich variety of
behavioral patterns created by
chaotic systems, including those found in living organisms. Ditto
and collaborator Sudeshna
Sinha of the Institute of Mathematical Sciences in Madras, India,
reasoned that these natural
chaotic systems should have been eliminated through evolution unless
they served a purpose.
Ditto and Sinha devised an experiment to see if a simple network of
chaotic computer elements
could be made to handle computations. They joined the chaotic
elements into a lattice using an
adaptive connecting mechanism that would open whenever an element
exceeded a certain critical
value. The mechanism was designed so that the researchers could set
a wide range of critical
values to vary the connection between elements.
The researchers then encoded values into the chaotic lattice using a
variety of different
techniques. In some cases, they chose patterns in the chaotic
elements to represent numbers. In
other cases, the numbers were represented by the amplitude of waves
emitted by the chaotic
elements or the frequency of "spiking" behavior.
After encoding the numbers, they stimulated the elements to begin
interacting.
Elements containing values above the critical level triggered the
connecting mechanism,
allowing the excess value to "avalanche" into neighboring elements.
That transfer then created
additional avalanches in other connected elements. With additional
stimulation, the domino
effect continued until the imbalance was conducted out of the system
-- as the answer to the
mathematical problem.
"We have the elements interconnected so that they respond to their
neighbors like the
avalanching that occurs when you pile grains of sand onto a
sandpile," Ditto explained. "You
allow the elements to avalanche and the system to evolve
chaotically, and then do the
avalanching again until the system settles down to the right answer.
It takes a couple of iterations
for it to settle down."
In a simple example, values of three and four would be encoded into
a system set with a critical
value of one. The values would create an imbalance that would
avalanche through the chaotic
elements until it was conducted out of the system -- as the value of
seven.
Chaotic elements are useful to this system because they can assume
an infinite number of
behaviors that can be used to represent different values or
different systems such as logic gates.
Because of this flexibility, altering the initial encoding and
changing the connections between the
chaotic elements allow a single generic system to perform a variety
of computations using its
inherent self organization. In conventional computing, systems are
more specialized to perform
certain operations.
"We are not really setting up rules in the same sense that digital
computers are programmed,"
Ditto explained. "The system develops its own rules that we are
simply manipulating. It is using
pattern formation and self-organized criticality to organize toward
an answer. We don't
3
micromanage the computing, but let the dynamics
do the hard work of finding a pattern that
performs the desired operation."
Just as the numbers can be encoded in a variety of ways, the answer
also comes out in a variety
of ways: a rate of change, amplitude, or a specific chaotic
behavior.
"There are a surprisingly large number of ways that the system can
perform the computations
and give you the answer," he added. "By slightly changing the
connectivity and the parameters of
the chaotic system, we can have it multiply several different ways
through the system's self
organization."
Because this new system differs dramatically from existing digital
computers, it is likely to have
different strengths and weaknesses. "It might be better than digital
computing for those activities
that digital computing doesn't do very well -- such as pattern
recognition or detecting the
difference between two pieces of music," Ditto said.
He compared dynamics-based computation to DNA computing and quantum
computing, both of
which are new computing paradigms still in their early stages of
development.
Ditto believes the new system would work particularly well in
optical systems. He has done
theoretical work applying dynamics-based computing to an ammonia
laser system and hopes to
see the system implemented experimentally.
"Potentially, we could stimulate a very fast system of coupled
lasers to perform a highly
complicated operation like very fast arithmetic operations, pattern
detection and Fourier
transforms" he said. "We have something that very naturally performs
an operation in an optical
system. This would provide an alternative to existing efforts, which
try to make optical systems
do operations more like transistors."
Beyond the systems they have tried, Ditto believes virtually any
coupled dynamic system could
be used to perform computation. "We hope that you can take any
dynamical system, stimulate it
in the correct way, and then get it to perform an operation for
you," he said. "This would provide
an alternative to engineering a system from the ground up."
Ditto acknowledges a number of engineering issues that may hamper
development of a practical
system based on this new computing paradigm. But he notes that in
their early days, digital
computers had to overcome a daunting set of obstacles to overtake
earlier techniques.
Support for the work has come from the U.S. Office of Naval
Research, and from Control
Dynamics, Inc., a company partially owned by Ditto.
Note: This story has been adapted from a news release issued by
Georgia Institute of
Technology.
Introduction
Computer science is a soft science. That is, computer science, like
mathematics is based of
accepting the true of some basic theorems. The mathematical laws on
which the conventional
CS paradigm is based have served to guide CS during its history of
incredible improvements of
CPU speed and memory size, but like the relationship between the
arrangements of the fingers
on the hand and the layout of the QWERTY keyboard, the relationship
between these laws and
the real world of electrons, light beams and digital circuits is
arbitrary. Absolute physical
benchmarks used in the physical sciences such as Physics and
Chemistry are ignored in the
conventional CS paradigm. Instead, algorithm analysis depends on the
nature of an algorithm in
the limit. That is, even though computers are of a finite size and
the speed of electricity is
bounded, algorithm analysis is based on processing unlimited data
sizes and efficiently utilizing
increasingly insignificant CPU and memory costs while ignoring the
impact of the complexity of
algorithms on the increasingly dominate programming costs.
4
Unfortunately since the laws for the current
paradigm are taught as absolute truths to every CS
freshman, they are very difficult to challenge. Indeed, the
perception is that they are infallible.
The traditional relationship between mathematics and the sciences
has been for mathematicians
to develop abstract construct without regard to engineering or
science and then, later, perhaps
centuries later, discovered that they have a useful application.
However, in the case of computer
science, the abstract laws and theorems of mathematics have become
the very basis of computer
science with the consequence that any alternative paradigm can be
proven to be inferior. The
result is that new computer paradigms, architectures and languages,
which could address many
of todays issues such as the inefficiency of multitasking operating
systems and hardware, have
been overlooked, even suppressed. The wealth of alternative computer
architectures,
programming languages and alternative paradigms of earlier years,
such as systolic arrays, data
flow, data parallelism and associative computing, has been
abandoned.
This point is illustrated by the Connection Machine fiasco of the
late 80s and early 90s. The
CM that was designed at MIT and promoted by DARPA was an attempt to
develop alternative
machine architecture. It failed because of inappropriate algorithm
paradigms and programming
techniques. That is, because of the mismatch between the accepted CS
paradigm and the
available programming languages and the reality of the machine, the
programmers could not
develop "cost effective" algorithms. The most obvious example of
this mismatch is sorting
versus searching. The need for sorting data for efficient retrieval
is accepted without question in
the conventional paradigm. To suggest that data can be efficiently
retrieved without sorting is
not only heresy, but can be proved to be wrong by any freshman
computer scientist using
conventional paradigm laws. Yet the CM, using data parallelism,
could and did find any datum
in memory in one step O(1) time. This would be an existence proof
in any other discipline, but
it was not and still is not accepted by the CS community because the
standard paradigm "proves"
that it takes at least O(log n) time to find something (even
conveniently ignoring the cost of
sorting the data.) As a result, the massive searching approach to
data selection and retrieval was
not pursued. One of the results of the law that data need to be
sorted in order to find them
efficiently is the tree organizations. However, using a data
parallel searching paradigm, there is
no need for nested menu trees or any other type of sorted data. Data
parallel searching, by
eliminating the need for sorting, does not need linked lists and
allows all data organizations
chronological, by recipient, by topical category to be utilized
simultaneously via associatively.
That is, data parallelism and associative computing is one possible
answer to simpler computing.
This approach requires that you go back to the flat tables of
yesteryear, but with gigabytes of
memory and gigahertz of speed, flat tables are manageable, even
preferable.
Moreover, the data parallel search based paradigm is well suited for
high school level tabular
data structures and natural language communication with your
computer. Both features
significantly reduce programming costs. But unfortunately, like the
internal combustion engine,
once a technology has progressed it a certain point, it is
practically impossible to overcome it.
However, as there is the possibility that the eventual depletion of
our natural energy resources
will cause economic changes in the design of car engines, the
eventual depletion of "free"
improvements in speed and memory may force a change in the
conventional CS paradigm. Even
today, super computers spend from 70 to 95% of their computing power
in overcoming the
limitations of the current paradigm so that only 5 to 30% of the
actual speed improvements are
obtained by the user. However, a change in paradigm is most likely
to occur in the Laptop, PDA
and cell phone environment not the super computer environment,
because the lack of power is
not the driving point, but the lack of physical space for keyboards,
display screens, mice, etc. and
the demand for easier modes of computing. Eventually, hopefully,
computer scientists will come
5
to realize that, CS has been trapped by the von
Neumann models success and that just as the laws
of plain geometry work well over a small portion of the Earths
surface, but fail when applied to
a much larger portion, so too, the laws of the current CS paradigm
work well for the old world of
"slow", few, expensive computers and cheap programmers, but are not
well suited to the new
world of fast, ubiquitous cheap computers and expensive programmers.
New Advances in Reconfigurable Computing and its Applications
J.UCS Special Issue by: (Miguel A. Vega-Rodríguez, Juan A.
Gómez-Pulido, Juan M. Sánchez-
Pérez Dept. Technologies of Computers and Communications, Univ.
Extremadura Escuela
Politécnica, Campus Universitario s/n. 10071 Cáceres, Spain
This is a survey of different papers about reconfigurable computing
and its applications. These
papers treat very different reconfigurable-computing applications:
cryptography, computer
vision, SOPC, microprocessor architecture, self-timed circuits,
sensor systems, detection of
ultrasonic emissions, FPGA compilation aspects (like data-dependent
loops), and motion
estimation. We can say that reconfigurable computing is becoming an
increasingly important
computing paradigm, being a good alternative for many real
applications.
As the Reconfigurable Computing is becoming an increasingly
important computing paradigm,
more and more FPGA-based applications are appearing. FPGA devices
are making it possible for
thousands of computer engineers to have access to digital design
technology in an easier way,
obtaining a better performance with a similar flexibility to
software. In addition, ASIC engineers
are now "reconfiguring" themselves as FPGA engineers for economic
reasons and adding to the
growing legions of FPGA designers.
In conclusion, reconfiguration of circuitry at runtime to suit the
application at hand has created a
promising paradigm of computing that blurs traditional frontiers
between software and hardware.
At present, reconfigurable computing is a good alternative for many
real applications in image
and signal processing, multimedia, robotics, telecommunications,
cryptography, networking and
computation in general.
This Special Issue brings together high-quality state-of-the-art
contributions about reconfigurable
computing and its applications. Concretely, the special issue
contains 7 papers that represent the
diverse applications and designs being addressed today by the
reconfigurable-computing
research community. With authors from around the world, these
articles bring us an international
sampling of significant work.
New Computing Paradigm: A Chaos-Based System That Evolves Science
and Engineering News
(09/11/98)
San Diego, CA -- As John Toon reported for GIT, A revolutionary new
computing technique that
uses a network of chaotic elements to "evolve" its answers could
provide an alternative to the
digital computing systems widely used today. Described for the first
time in the September 7
issue of Physical Review Letters this "dynamics-based computation"
may be well suited for
optical computing using ultra-fast chaotic lasers and computing with
silicon/neural tissue hybrid
circuitry.
The system has so far demonstrated an ability to handle a wide range
of common operations,
including addition and multiplication, as well as Boolean logic and
more sophisticated operations
such as finding the least common multiplier in a sequence of
integers. Because it depends on
6
interaction among its coupled elements, the
system is naturally parallel.
"We have shown that this can be done, but we've only seen the tip of
the iceberg," said William
L. Ditto, professor of physics at the Georgia Institute of
Technology. "This is a glimpse of how
we can make common dynamic systems work for us in a way that's more
like how we think the
brain does computation. It's an entirely new computing paradigm."
For many years, scientists have observed the rich variety of
behavioral patterns created by
chaotic systems, including those found in living organisms. Ditto
and collaborator Sudeshna
Sinha of the Institute of Mathematical Sciences in Madras, India,
reasoned that these natural
chaotic systems should have been eliminated through evolution unless
they served a purpose.
Ditto and Sinha devised an experiment to see if a simple network of
chaotic computer elements
could be made to handle computations. They joined the chaotic
elements into a lattice using an
adaptive connecting mechanism that would open whenever an element
exceeded a certain critical
value. The mechanism was designed so that the researchers could set
a wide range of critical
values to vary the connection between elements.
The researchers then encoded values into the chaotic lattice using a
variety of different
techniques. In some cases, they chose patterns in the chaotic
elements to represent numbers. In
other cases, the numbers were represented by the amplitude of waves
emitted by the chaotic
elements or the frequency of "spiking" behavior.
After encoding the numbers, they stimulated the elements to begin
interacting.
Elements containing values above the critical level triggered the
connecting mechanism,
allowing the excess value to "avalanche" into neighboring elements.
That transfer then created
additional avalanches in other connected elements. With additional
stimulation, the domino
effect continued until the imbalance was conducted out of the system
-- as the answer to the
mathematical problem.
"We have the elements interconnected so that they respond to their
neighbors like the
avalanching that occurs when you pile grains of sand onto a
sandpile," Ditto explained. "You
allow the elements to avalanche and the system to evolve
chaotically, and then do the
avalanching again until the system settles down to the right answer.
It takes a couple of iterations
for it to settle down."
In a simple example, values of three and four would be encoded into
a system set with a critical
value of one. The values would create an imbalance that would
avalanche through the chaotic
elements until it was conducted out of the system -- as the value of
seven.
Chaotic elements are useful to this system because they can assume
an infinite number of
behaviors that can be used to represent different values or
different systems such as logic gates.
Because of this flexibility, altering the initial encoding and
changing the connections between the
chaotic elements allow a single generic system to perform a variety
of computations using its
inherent self organization. In conventional computing, systems are
more specialized to perform
certain operations.
"We are not really setting up rules in the same sense that digital
computers are programmed,"
7
Ditto explained. "The system develops its own
rules that we are simply manipulating. It is using
pattern formation and self-organized criticality to organize toward
an answer. We don't
micromanage the computing, but let the dynamics do the hard work of
finding a pattern that
performs the desired operation."
Just as the numbers can be encoded in a variety of ways, the answer
also comes out in a variety
of ways: a rate of change, amplitude, or a specific chaotic
behavior.
"There are a surprisingly large number of ways that the system can
perform the computations
and give you the answer," he added. "By slightly changing the
connectivity and the parameters of
the chaotic system, we can have it multiply several different ways
through the system's self
organization."
Because this new system differs dramatically from existing digital
computers, it is likely to have
different strengths and weaknesses. "It might be better than digital
computing for those activities
that digital computing doesn't do very well -- such as pattern
recognition or detecting the
difference between two pieces of music," Ditto said.
He compared dynamics-based computation to DNA computing and quantum
computing, both of
which are new computing paradigms still in their early stages of
development.
Ditto believes the new system would work particularly well in
optical systems. He has done
theoretical work applying dynamics-based computing to an ammonia
laser system and hopes to
see the system implemented experimentally.
"Potentially, we could stimulate a very fast system of coupled
lasers to perform a highly
complicated operation like very fast arithmetic operations, pattern
detection and Fourier
transforms" he said. "We have something that very naturally performs
an operation in an optical
system. This would provide an alternative to existing efforts, which
try to make optical systems
do operations more like transistors."
Beyond the systems they have tried, Ditto believes virtually any
coupled dynamic system could
be used to perform computation. "We hope that you can take any
dynamical system, stimulate it
in the correct way, and then get it to perform an operation for
you," he said. "This would provide
an alternative to engineering a system from the ground up."
Ditto acknowledges a number of engineering issues that may hamper
development of a practical
system based on this new computing paradigm. But he notes that in
their early days, digital
computers had to overcome a daunting set of obstacles to overtake
earlier techniques.
Support for the work has come from the U.S. Office of Naval
Research, and from Control
Dynamics, Inc., a company partially owned by Ditto.
Tuple Board: A New Distributed Computing Paradigm for Mobile Ad Hoc
Networks
(Alan Kaminsky - Department of Computer Science Rochester Institute
of Technology
Rochester, NY, USA
The Tuple Board Paradigm
8
The tuple board distributed computing paradigm
is derived from the tuple space paradigm. It first
describes tuple space, and then introduces the tuple board and show
how it differs from tuple
space. It also describes how to design applications based on the
tuple board. Section 4 describes
how the tuple board is implemented.
Historical background
In 1985 Gelernter introduced the notion of tuple space and its
associated distributed coordination
language, Linda. Since then, tuple space has been implemented in
many languages and
platforms. Notable Java implementations include Sun Microsystems
JavaSpaces and IBMs
TSpaces.
A tuple space based distributed application stores information in
tuples. A tuple is a record of
one or more fields, each field having a value of a certain data
type. One process can write a tuple
into tuple space. Another process can then take a tuple out of tuple
space. To find a tuple to take,
the taking process supplies a tuple used as a template. Each field
of the template may be filled in
with a specific value or be set to a "wildcard" value. The template
is matched against all tuples in
tuple space. A template and a tuple match if they have the same
number of fields and the fields
have the same data types and values; a wildcard matches any value.
The taking process receives
one matching tuple that was taken out of tuple space. If more than
one tuple matches the
template, one tuple is chosen arbitrarily to be taken; if no tuple
matches the template, the taking
process blocks until there is a match. A process can also read a
tuple. Reading is the same as
taking, except the reading process receives a copy of the matching
tuple while the original tuple
stays in tuple space.
Tuple space provides a distributed communication mechanism that
decouples processes both "in
space" and "in time." Processes need not reside on the same device
to communicate. A process
on one device can write a tuple and a process on another device can
take or read the tuple; the
processes thus have communicated through the intermediary of tuple
space. Processes also need
not be running at the same time to communicate. A process can write
a tuple even if the process
that will read or take the tuple is not running yet. The writing
process can then go away, and the
tuple will persist in tuple space until another process reads or
takes it. Conversely, a process can
read or take a tuple (and will block if necessary) even if the
process that will write the tuple is
not running yet.
Since mobile computing devices with wireless networking
capabilities, such as laptop PCs, tablet
PCs, and PDAs, are becoming prevalent, there is a need for
distributed applications that run on
groups of nearby devices. For example, people in a meeting would
like to have their PDAs pool
their individual calendars together to find a date and time everyone
has free for the next meeting.
With todays software this is typically impossible, since different
people use different calendar
software, different calendar server computers, and so on. Tuple
space provides an alternative:
Each PDA writes tuples with each persons open calendar slots, then
all the PDAs read all the
Tuples and find a common slot. Previous work, such as one world and
Lime, has attempted to
adapt tuple space to the mobile device environment. However, there
are still difficulties. Since
tuples are supposed to persist in tuple space even if the writing
process goes away, tuple space is
typically implemented on a separate, central server computer.
However, central servers are
unattractive for groups of mobile wireless devices, since the
devices may not be in range of a
central server. Although the devices are in range of each other, no
device can act as a central
server because devices can leave or turn off at any time. Without a
central server, implementing
tuple persistence is difficult and requires complicated software.
The notion of a tuple board was introduced as a modification of
tuple space that is better suited
for ad hoc networks of mobile wireless computing devices without
central servers. A tuple board
9
is like a shared virtual bulletin board. One
process can post a tuple on the tuple board. A process
can withdraw a posted tuple; but a process can only withdraw the
tuples the process itself has
posted, not tuples any other process has posted. If a device leaves
the network or turns off, all the
tuples the devices processes had posted are implicitly withdrawn.
Another process can read a
tuple on the tuple board that matches a template, just as with tuple
space. A process can set up an
iterator over all tuples that match a template, and then repeatedly
read a tuple from the iterator; a
different tuple is returned each time. If all tuples matching the
iterators template have been read,
the process reading the iterator blocks until a new matching tuple
is posted. A process can set up
a notifier for a template; the notifier will then inform the process
whenever a matching tuple is
posted or withdrawn.
The key difference between the tuple board and tuple space is that
tuples do not persist on the
tuple board if the posting process goes away. This greatly
simplifies the tuple board
implementation, since when a device turns off or leaves the network
its posted tuples can simply
disappear. Many useful distributed applications can be developed
even without tuple persistence.
In fact, the ability to detect when a device goes away because a
notifier reports that a tuple,
which the device had previously posted, was withdrawn is useful in
its own right.
Applications Based on the Tuple Board
In this section we describe how distributed ad hoc collaborative
applications are designed using
the tuple board paradigm. Such applications are "collaborative" in
that any number of nearby
mobile computing devices can participate.
These applications are also "ad hoc" in that the devices do not need
to be configured to know
about each other ahead of time; instead, devices can come and go at
any time, and the application
runs on whichever devices happen to be nearby.
Information sharing applications of all kinds are easily implemented
using the tuple board.
Consider a digital photo sharing application. Each device with
digital photos PCs, PDAs, even
cameras and cell phones posts tuples for its pictures. Each tuple
has, say, four fields: unique
ID, thumbnail image, date taken, and description.
Any device can then obtain the other devices pictures, as follows.
To retrieve all the pictures,
the device sets up a template where all four fields are wildcards;
to retrieve only Disney World
pictures, the templates description field is set to "Disney World"
and the other fields are
wildcards; and so on. The device uses an iterator to read all the
tuples that match the template,
assembles the tuples thumbnail fields into an "album" of pictures,
and displays the album on the
devices own screen. If the user wants to see the full-size picture
for some thumbnail, the users
device posts a tuple containing a full picture request for the
pictures unique ID. Seeing that
request posted, the device that has the picture with the given
unique ID posts a tuple containing
the full-size image.
The users device reads that tuple and withdraws its request tuple,
whereupon the other device
withdraws its full-size image tuple. If a device joins the group,
the new device merely starts
posting tuples, and the other devices (responding to a report from a
notifier) add the new
devices thumbnails to their displays. If a device leaves the group,
the remaining devices (again
responding to a report from a notifier that tuples were withdrawn)
remove the departed devices
thumbnails from their displays. Thus, the application automatically
adapts as devices arrive and
depart, without needing to rely on a central server.
Other examples of ad hoc collaborative applications that can be
designed in a similar way using a
tuple board include file, music, and video sharing; groupware
applications like shared
whiteboard, shared document authoring, and the aforementioned shared
calendar; and vendor
information directories in shopping malls and avenues. Bondada built
a conference information
system demonstration using the tuple board collaborative
applications based on the tuple board.
10
Mobile Computing Paradigm
Introduction
Mobile computing consistently fails to live up to expectations.
Early adopters complain about the
size and resolution of displays, awkward input devices and limited
bandwidth. There is every
reason to assume that the complaints will be exacerbated for mobile
CSCW, since most
collaborative computing is computationally intensive, often
synchronous and visual. In addition,
computer-mediated communications require minimal latency in order to
be socially acceptable.
Many enthusiasts respond to this challenge by suggesting that new
mobile technologies will be
sufficiently powerful to meet the needs of CSCW. We assert, however,
that expectations and
requirements of the user community will proportionally increase by
new advances in computing
technology. The ante will, in a sense, be upped once more.
This paper provides an initial exploration of this problem, which
represents a fascinating
challenge given that todays mobile devices are immensely more
powerful than the desktop
computers of yesteryear, but at the same time they are a far cry
from what users want today. We
believe this challenge is fundamentally conceptual, rather than
technical; todays mobile
computing paradigm is simply not suited for handheld CSCW!
A research program has been launched, which aims to develop the
conceptual foundations for
mobile IT-use and CSCW more thoroughly. First, it is necessary to
specify exactly how mobile IT-
use differs from stationary computing. Next, a reference model is
needed to guide fieldwork and
provide a common vocabulary for designers.
Explaining the desktop ,,bias of mobile computing
Based on the premises offered above, the following argument can be
given: Mobile IT is inferior
to stationary computing in terms of performance and bandwidth. For
example, bandwidth is
limited, keyboards are awkward and there is no desk on top of which
to put the devices when
typing.
At the same time, mobile IT design is clearly stationary ,,biased:
de facto industrial standards
have adopted the desktop metaphor and offer ,,pocket versions of
familiar office applications.
For example, there is Pocket Word (without styles) and Internet
browsers (without support for
Java and plug-ins), which, in addition, hardly display content but
one line at a time.
It seems like this is a conceptual, rather than a technical
cul-de-sac, since "users needs", in these
terms, will always exceed what mobile computing can offer. But as
the following argument
demonstrates, this can be conceived as a result of a naïve design
paradigm.
Is advanced document management or internet-based multimedia
publication purposeful operations
for mobile workers? Are there mobile use contexts where a
typewriter-metaphor based terminal with
a connected keyboard and screen will be useful at all. Consider the
example of electrical maintenance
workers equipped with a desktop metaphor-based device. When
operating the device as afforded
by its design, i.e. sat down in from of the user in one arms length
distance, the objects of work,
which are switches and power cables in a roadside cabinet, cannot be
reached. If the device, on
the other hand, is put down on the only other flat surface, which is
the top of the cabinet, then the
display cannot be seen when squatting to reach the switches and
cables.
In order to make the mobile computer support mobile work it has had
to be turned into a desktop
computer by connecting it to the stationary network and funnel its
functionality through a hosting
PC.
11
The desktop metaphor in mobile computing is,
thus, a symptom of the confusion of operations
and functionality in a stable use context. Only when the use context
is constantly changing, like
in mobile computing, it becomes apparent that this contributes to a
problematic design paradigm.
In order to open up an alternative design space (or at least a place
to turn), an alternative
conception of the relationship between computer-mediated services
and continually changing
modalities is needed. We are currently developing a model that
responds to this challenge by
explicating the nature of mobile IT-use.
Modeling mobile work
The reference model for mobile work builds on fieldwork and
discussions. Its core concepts are:
Modality, which is a characterization of the physical
relocation patterns of the mobile
worker/mediating technology.
Technology, which can to varying degrees be adapted to mobile
work, and
Service, which is the set of intended operations offered by
the functionality of the mediating
technology.
A mobile session, thus, simply consists of changing
modalities and services.
A mobile setting comprises at least one mobile session. The
following figure summarizes the
model in relaxed UML notation:
Modeling mobile work
Three important modalities of mobile work are:
Visiting is working in different places for a
significant period of time
Traveling is working while traveling in a vehicle, such as an
airplane or a train
Wandering is working while being locally mobile
Certainly, these are only ideal types; nevertheless they represent a
useful conceptual topology which
distinguishes mobile work from stationary work and contributes to
developing a new research
agenda for handheld CSCW. The following figure illustrates the
changing modalities of mobile work:
12
Modalities of mobile work
Services and modality constitute central components of a mobile
session, which due to its mobility is
far more contingent and dynamic than mobile work. Thus, it points in
the direction of new items for a
mobile informatics research agenda when these dimensions are
combined, such as in the following figure:
Changing services and modalities
Implications for research
Building on the framework outlined above, the following items for a
mobile computing research
agenda can be outlined:
Initialization
Main objective: Develop models and systematic support for
establishing sessions in a mobile
setting.
Some selected research problems:
Browse, inspect and select services. One can assume that the
availability of services from a
mobile terminal will vary with geographical re-location.
Browse, inspect and select resources (such as documents, people,
procedures, etc.), from within a
service. It is integral to establishing sessions, especially
involving other people in a synchronous
setting, to be aware of who is available and what they are
able/capable of contributing.
Negotiate access, quality and pricing. In a situation where mobile
communications are more
expensive then those offered by a stationary infrastructure, whilst
at the same time furnishing
limited performance and bandwidth, it becomes important to support
the necessary trade-offs
between cost in time, money and quality.
13
Programming sessions. In a mobile setting, user
cannot be expected to be fully interactive, since
mobility itself imposes demands on attention and mobile work is
likely to be directed towards
non-representable objects (otherwise, why go mobile?).
Transformation
Main objective: Develop models and systematic support for
sustaining services between
modalities in a mobile setting.
Introducing the notion of changing modalities enhances the mobile
informatics research agenda
with an interest in how people can change between modalities whilst
remaining connected to
current services.
Adaptation
Main objective: Develop models and systematic support for seamless
use of new services within
modalities in a mobile setting.
In this opposite of transformation, research interest is in how new
services (for which the current
modality may not be suited) can be adapted to function in a
satisfactory manner.
Negotiating access and performance profiles for users entering a new
modality.
Changing data from new services to make available programs interpret
and refine such
elements in a satisfactory manner.
Adapting programs to deal with new types of data.
Aggregation of service units into fully functioning services for the
current modality.
Optimization
Main objective: Develop models and systematic support for
improved performance of sessions in a
mobile setting.
This item on the agenda is already well covered in the mobile
computing area. There seems to be a
tendency, however, of assuming that mobile technology will be almost
as reliable as its fixed
counterpart. We believe that more work is needed on how to complete
business-critical tasks using
mobile systems in case of unanticipated technological breakdowns.
We have selected one other area in which more work is definitely
required: Simple input devices
for mobile sessions.
New applications
The goal now is to combine empirical studies with the conceptual
framework of the model to
produce innovate, mobile-aware applications. By technical
experimentation and empirical evaluation,
such applications can inform re-design and improve the model.
Medical
Fostering the Biological Sciences in the School of Medicine (Rutter)
Now, with respect to the development of the biological sciences at
UCSF, the Department of
Biochemistry was a mini-school in itself because it covered all the
most important scientific
approaches in biology. We weren't just interested in molecular
genetics. We also became a cell
biology group because we were interested basically in the cell.
There have been ebbs and flows.
But it has been a department that has operated across the frontier
of science. We always thought
14
we knew where the various fields were going and
tried to get scientists who would help or lead
the change. As the department flourished, of course we ran out of
FTEs and space. So how to
grow? Clearly, it was by colonization of the other departments.
Abstract: Single photon emission tomography allows the
imaging of dynamic brain functioning.
The use of cerebral activating procedures within the scan protocol
enables investigation of the
mechanisms involved in specific brain functions in health and
disease. Activation studies involve
the comparison of at least two data sets describing brain activity
generated in conditions that
differ for the specific function in question. When designing an
activation study, decisions
regarding methodology include: the nature of the activation regime,
the tracer-ligand utilized, the
SPET instrument and the manner of subsequent data analysis. These
issues are discussed in this
review, both theoretically and with reference to published studies.
Means of activating particular
cerebral structures and functions are reviewed, as are the
limitations of the techniques with
respect to temporal and spatial resolution and the potentially
confounding nature of preconceived
ideas regarding the mechanisms of brain function.
Simulators for biomolecular computing, (both in vitro and in
silico), have come to play an
important role in experimentation, analysis, and evaluation of the
efficiency and scalability of
DNA and biomolecule based computing. Simulation in silico of DNA
computing is useful to
support DNA-computing algorithm design and to reduce the cost and
effort of lab experiments.
Although many simulations have now been developed, there exists no
standard for simulation
software in this area. Reliability, performance benchmarks, user
interfaces, and accessibility are
arguably the most important criteria for development and wide spread
use of simulation software
for BMC. The requirements and evaluation of such software packages
for DNA computing
software are discussed, particularly questions about software
development, appropriate user
environments, standardization of benchmark data sets, and centrally
available common
repositories for software and/or data.
The Breast Cancer Working Group is a multidisciplinary team of
researchers from the Baystate
Medical Center and the University of Massachusetts Amherst. Working
Group researchers
represent a wide variety of scientific disciplines including
surgery, pathology, nursing,
epidemiology, statistics, molecular genetics, computer science,
chemical engineering, and
nanotechnology. The Working Group's laboratory-to-clinic approach
expedites the translation of
scientific discoveries into practical biomedical applications. In
addition to university and hospital
facilities, Working Group researchers have access to new,
state-of-the-art laboratories at the
Baystate-UMass Biomedical Research Institute in Springfield.
Currently, the Group's collective
effort is focused on understanding the nature of pre-cancerous
breast lesions that can transition
into malignant tumors. Dr. Richard Arenas, Chief of Surgical
Oncology at Baystate, and Dr. Joe
Jerry, UMass professor of Molecular Medicine, are two Working Group
members whose
collaboration with colleagues in the UMass Chemistry and Chemical
Engineering departments is
directed toward translating their medical and biological expertise
into practical treatments and
preventative therapies for breast cancer.
The Collaborative Approach
Collaboration fuels scientific innovation. In a 2001 report, the
National Cancer Institute stated
that, "multidisciplinary teams are needed to solve virtually all of
the 'big' problems in cancer
research." Productive collaboration among mathematicians,
biologists, computer scientists,
epidemiologists, imaging scientists, physicists, and clinicians is
needed to effectively cure and
15
control cancer, the report said. Now, in
western Massachusetts, just such a multidisciplinary
research team exists. The Pioneer Valley's Breast Cancer Working
Group, made up of M.D.s and
Ph.D.s from the Baystate Medical Center in Springfield and the
University of Massachusetts at
Amherst, was formed to investigate the basic pathology of breast
cancer and develop more
effective interventions to treat and prevent the disease.
Collaboration across scientific disciplines has yielded many
important achievements including
the discovery of the structure of DNA. In his book on the process of
scientific discovery, Francis
Crick wrote, "In nature, hybrid species are usually sterile, but in
science the reverse is often true.
Hybrid subjects are often astonishingly fertile."
The Breast Cancer Working Group is a hybrid coalition of
researchers, representing a wide
variety of scientific disciplines ranging from pathology and
surgical oncology to chemical
engineering and nanotechnology that evolved out of a partnership
between researchers at UMass
Amherst and the Baystate Medical Center. They meet regularly to help
steer the focus of the
Group and to allow its direction to influence their own research
programs and clinical practice.
At Risk for Cancer
Every year thousands of women are diagnosed with non-cancerous
breast disease. Although, so-
called benign breast disease is not cancerous, a certain form of the
disease, called atypical
hyperplasia, is associated with an increased risk of breast cancer.
At least 10% of those women
diagnosed with atypical breast lesions will develop cancer within
one year.
At Baystate Medical Center, physicians frequently detect these
atypical hyperplasias and,
although they know that some of those patients will soon develop
breast cancer, there is nothing
to be done about it. Treating all women with atypical hyperplasia
would be expensive and very
invasive. However, inaction all but assures that 1 out of every 10
women diagnosed will be
battling breast cancer within a year. This clinical dilemma, and the
problem it poses for
physicians and their patients, compelled the Breast Cancer Working
Group to direct their focus
toward investigating cancer associated with atypical, pre-malignant
breast lesions.
Dr. Joe Jerry is a professor of Molecular Medicine at UMass Amherst
and the designated leader
of the Working Group. His lab uses animal models to study the
molecular pathways that mediate
susceptibility and resistance to breast cancer and to design
targeted therapeutics to prevent it.
"Atypical doesn't sound good," Jerry says. "The physician has to
tell the patient, 'go home and
don't worry about it, but come back and have it checked out often,
because you should worry
about it.' That's pretty uncomfortable, and at some point people
might die from worrying about
the disease rather than from the disease itself."
Prevention is the Best Treatment
A primary goal of the Working Group is to harness the formidable
scientific expertise of its
members to achieve a better understanding of the basic cellular and
molecular mechanisms that
control how atypical hyperplasias transition into tumors. By
accurately describing the pathology
of tumorigenesis, new drugs can be designed and new methods
developed to treat or even
prevent breast cancer.
"Stopping the transition would be real prevention. It would be the
ultimate prevention," says Dr.
Richard Arenas, Chief of Surgical Oncology at Baystate Health
Systems and an active researcher
in the Breast Cancer Working Group. "If you know that, biologically,
there is a link between
atypia and the onset of actual breast cancer, presumably because you
see it pathologically, then
you've identified an actual pathway and there is a possibility of
interrupting that pathway," he
said.
Arenas has partnered with Jerry to explore how certain anti-cancer
drugs affect tumor cells at a
molecular level and with other Working Group members in the Chemical
Engineering
16
department at UMass Amherst to develop more
effective drug-delivery methods. They are
interested in the effect that estrogen and prostaglandin-blocking
drugs, called aromatase
inhibitors and COX-2 inhibitors respectively, have on the activity a
tumor-suppressor protein
called p53. When working properly, p53 performs an indispensable
function in the cellular
reproduction process by preventing abnormal cell proliferation.
Mutations in the p53 gene and
non-mutational changes in p53 function may be associated with up to
45% of all breast cancers.
A Good Model
In depth experimental analysis in breast cancer is currently
underway in Joe Jerry's laboratory at
UMass Amherst. Jerry has developed a mouse model with a defective
gene that consistently
develops mammary tumors, which are very similar to those found in
human breast tissue. Other
animal models for breast cancer have previously been created, but
none develop the true ductal
hyperplasia that mimics human breast tumors.
"We're seeing a series of different structures in the carcinomas
that are very much like humans,"
he says. This analogous system allows Jerry's research team to
experiment with drugs that
stimulate the surveillance function and boost its ability to prevent
abnormal cell proliferation.
Almost nothing exciting about computing today has to do with data
structures and algorithms
One of Alans undergraduate degrees is in molecular biology. He cant
understand it anymore
despite having tried to review new developments every few years.
Thats not true in computer
science. The basics are still mostly the same. If you go to most
campuses, there is a single
computer science department and the first course in computer science
is almost indistinguishable
from the first course in 1960. Theyre about data structures and
algorithms despite the fact that
almost nothing exciting about computing today has to do with data
structures and algorithms.
The Internet is like the human body. Its replaced all of its atoms
and bits at least twice since it
started even though the Internet has never stopped working. Attacks
on the ,,Net arent really
attacks on the ,,Net, theyre attacks on machines on the ,,Net. Very
few software systems, maybe
none, are built in ways that sustain operation in spite of being
continually rebuilt and continually
growing.
The future five years out is easy to predict because all of the
forces acting on computer science
are trying to keep it the same as it is now. Likely, the future will
be more of what we have now.
Are computer science, software engineering, OOP, etc. oxymorons?
Alan reminisce about Bob
Barton, an early Utah professor. Bob said that "systems programmers
are the high priests of a
low cult" and "there are few things know about systems design, but
the basic principle of
recursive design is: make the parts of the same power as the whole.
Bob Barton has a classic
paper that contains seven of the most important things that people
know about software today.
Another quote: "My job is to disabuse you of any firmly held notion
you held when you came
into this classroom." The best way to get people to think is to
destroy their current thinking.
Preconceived notions are largely reactions to what vendors are
saying. Alan says that his course
from Barton was the most valuable one he took in college because
Barton garbage collected their
minds.
"Americans have no past and no future; they live in an extended
present." This describes the
state of computing. We live in the 80s extended into the 21st
century. The only thing thats
changed is the size. Windows XP has 70 million lines of code. Its
impossible for Alan to believe
that it has 70 million lines of content. Microsoft engineers dont
dare prune it because they dont
know what it all does. Cathedrals have 1 millionth the mass of
pyramids. The difference was the
arch. Architecture demands arches.
17
Computers are artifacts. in order to have a
science of computing, we have to make them. This
isnt unheard of. To have a science of bridge building, people had to
start building them so they
could be studied. He shows a clip of the Tacoma Narrows Bridge.
After studying the failure, the
bridge was rebuilt and hasnt come down. This reminds Alan of
software systems. Were much
better at building software systems than we are at predicting what
they will do. There are no
good models. If we were scientists, wed be trying to build models.
"Science is not there to tell us about the Universe, but to tell us
how to talk about the Universe."
(Niels Bohr). Science helps us to be more reasonable about
reasoning. Its set up so that we get
better and better maps (abstractions) not perfect maps.
Alan uses John McCarthy and Lisp as an example of real science in
computer science. He
showed us that you can build a system thats also its own metasystem.
Lisp is like Maxwells
equations. Many of the things that are wrong about Java is that it
lacks a metasystem and that the
metasystem thats been tacked onto it is missing key parts. To find
the most interesting things
about our field you have to go back 30 or 40 years.
Alan used McCarthys method to design an object oriented system. He
spent only a month
implementing it because of the metasystem.
We build finite artifacts, but the degrees of freedom grow faster
than we can reason about them.
Thus, were left with debugging.
We are creatures who live in a world of stories and were always
looking for simple stories o
explain the world. He shows a clip, called Private Universe, of
Harvard grads (at graduation)
describing trying to explain the seasons. Almost everyone thought
the seasons were caused by an
elliptical orbit of the earth around the sun. It didnt matter
whether or not the students were
science majors or now. Interestingly, people know that the seasons
are reversed between the
northern and southern hemispheres. Their stories are inconsistent
with what they know, yet they
persist in believing them, even though they have the knowledge that
contradicts their theory.
When people react instantly, theyre not thinking, theyre doing a
table lookup.
Engineering predates science by thousands and thousands of years
because we dont have to
understand things to engineer them. He uses one of my favorite
quotes: an engineer is someone
who can make for a dollar what any fool could make for two.
Making computing into a science means that we have to understand
what to do about our beliefs.
When we talk, we do nothing but tell stories that people will find
interesting. Theres danger in
that because stories can create resonance without being scientific.
Distributed Systems.
The classical architecture of distributed systems relies on computer
communication protocols.
The main components of a distributed system are protocol entities
that reside in different hosts
and which exchange messages following a well defined communication
protocol.
On one side, some distributed applications require an important
deployment for testing and
debugging; on the other side, users are not interested to use
software if it has not been thoroughly
tested and is not largely deployed:
Distributed operating systems use the exchange of special purpose
messages for implementing
non-local services. This imposes that a minimal set of protocols be
explicitly wired into the
kernel. These specialized protocols restrict the kernels genericity
and adaptability;
Distributed applications usually have two parts: one that is
responsible for communication
management i.e, implementing a protocol for moving data between the
different hosts; the other
part uses the communication facilities provided by the first one in
order to implement the actual
distributed algorithm.
18
Extending the above argument, we can argue that for the application
programmer, developing a
distributed application requires a different methodology from that
of a centralized application.
When developing a distributed application, the programmer must
explicitly handle efficiently the
data exchange in the system and its processing whereas for a
centralized application, only data
processing is considered. We can thus argue that developing
distributed applications that way
is error prone; this is exacerbated by the difficulty to implement
"correct" computer
communication protocols. The ideal situation for the programmer
would be to implement
distributed applications the same way he/she implements centralized
applications;
We present in this paper a new paradigm for performing computer
communication, which we
call "communication by messengers".
When two hosts communicate using this paradigm, they exchange
programs called messengers".
The messenger contains the appropriate code to instruct the
recipient "what" it has to do next. A
messenger contains both the data and the rules necessary to perform
a given protocol.
This way of performing protocols does not require protocol entities
be preconfigured in the
communicating hosts.
It is the source host which completely determines which protocol is
to be used for the data
exchange; the destination host is not required to "know" the
protocol being used. When used as
the basis for distributed applications, the communication by
messengers paradigm brings more
flexibility. It becomes possible for an application to explore the
network and spread itself instead
of having to rely on pre-configuration and installation of
application specific software.
Another view of a messenger is that of a thread created in a remote
host on behalf of the source
host. From a programmers viewpoint, sending a messenger to a remote
host is similar to the
creation of a local thread. This offers a uniform way for
programming both centralized and
distributed applications. Moreover, the communication by messengers
paradigm can be used as a
simple way to extend the remote procedure call paradigm.
The Messenger Paradigm
The messenger paradigm is born from a new way of thinking computer
communications. Instead
of the classical sender/receiver model based on protocol entities
that exchange and interpret
protocol specific messages, Tschudin proposed in a communication
model based on the
exchange of protocol unspecific programs, called the messengers.
Hosts receiving messengers
will then execute the messengers code instead of interpreting
them as messages.
The Messenger Platform
All hosts involved in a messenger based communication share a common
representation of the
messengers and provide a local execution environment, the
messenger platform. A messenger is
executed sequentially, but several messengers may execute in
parallel inside the platform.
Platforms
arriving
messengers
~
...
~
x
y
123
19
'abc'
process
queues
channels
dictionary
messenger execution platform
msgr threads:
Messenger platform are connected through unreliable channels through
which messengers are
sent as simple messages or data packets.
A set of channels enables a messenger platform to exchange
messengers with other platforms.
The channels provide an unreliable datagram service which enables
messengers either to reach
entirely and correctly the neighboring platform or to be discarded
or lost;
Integrally arriving messengers are turned into independent messenger
processes or threads of
execution, also called messengers for simplicity. The platform does
not interfere with their
execution except for programming errors or unavailable resources.
Also do other messengers
have no means to stop or kill another messenger process without its
consent.
The executing threads are able to share common data inside a given
platform by the means of a
dictionary which contains pairs of keys and data values; Process
queues are the low-level
mechanism offered by a platform in order to allow messengers to
implement basic concurrency
control functionality such as synchronization of threads, mutual
exclusion, etc. Process queues
are FIFO queues of messenger processes. All threads of the queue are
blocked except the thread
at the head of the queue.
Platforms share
(1) a common messenger programming language, used to express
messenger behavior; and
(2) a common external representation of the messenger, used for the
physical exchange
messengers.
Primitives of a Messenger Programming Language
Messengers are exchanged between two platforms as simple messages,
using a common external
representation. Arriving messengers are turned into threads of
execution by the corresponding
platforms. A messenger is then a sequence of instructions expressed
in a messenger
programming language common to all platforms. Beside general
purpose instructions (arithmetic
operations, logical operations, etc), a messenger programming
language must offer a set of
specialized primitives. Here we present an example of such a set of
primitives: Process queues,
channels as well as global variables in the dictionary of a given
platform are accessed by
a key. Keys are either generated by the platform (e.g., name of a
channel) or can be
constructed/chosen by the messenger processes using the key ()
primitive. Global variables
in the dictionary are accessed through their key using the
get(k:key) and set(k:key,
v:value) primitives; A messenger is sent through a channel to
another platform by the
submit(k:key, m:msgr descr) primitive. It is also possible to create
a new local
messenger process by submitting a messenger to a special "loop-back"
channel the new
process is completely independent of its launching process; A
messenger is able to replace its
behavior by another behavior with the chain(m:msgr descr) primitive;
Process queues
play a central role in the synchronization of messenger processes.
Primitives for handling
process queues are: enter(q:key) which enables a messenger process
to enter a queue, such
a process will then be blocked until it reaches the head of the
queue; leave which enables the
messenger process at the head of the queue to remove itself from the
queue; stop(q:key)
20
which stops the queue so that when the
messenger process at the head of the queue leaves the
queue, the next messenger process coming at the head of the queue
will remain blocked; and
Start(q:key) which resumes a queue previously stopped by the stop
primitive. A
referenced queue that does not yet exist is automatically created by
the platform.
By the use of the submit and chain primitives, messengers are able
to act as mobile entities
that can propel themselves across the network to search for a given
information or to perform a
given task in a remote place. Alternatively, a messenger can
continue its task in the local
platform while the messengers it sent out will execute remotely
before returning with the result
of some sub-task. The possibility for a messenger process to replace
its behavior with the chain
primitive can be compared with the change of behavior of actors in
the actor model of Agha.
The difference resides in the fact that the behavior change is a
fundamental part of the actor
model: actors are seen as abstract machines dedicated to process one
incoming communication.
Actors always change explicitly or not their behavior before
processing the next communication.
On the other side, messengers are mobile entities that perform given
tasks, which are not
necessarily reactions to incoming communications.
Conclusion
The messenger paradigm is a communication model relying on
instruction-passing instead of
message-passing. Messengers are mobile threads of execution that can
travel across a network.
The basic requirements needed to achieve the messenger paradigm are:
(1) All hosts involved in the communication must be provided with
the messenger platform,
(2) Al platforms are able to interpret the same messenger
language; and
(3) Unreliable messenger "channels" link the different platforms.
Distributed systems are built on top of a communication mechanism.
The proposed
communication by messenger paradigm is a low-level communication
mechanism, which
can be used at different levels of abstraction. We have shown that
all kind of protocols can be
implemented using this new paradigm: functionality of classical
protocols, based on entities
exchanging PDUs, can be realized without entities and without PDU
exchange, using
messengers. Distributed operating systems, which depend on
communication protocols, can then
be implemented using messengers.
Going further, the classical view of data traveling the network to
be exchanged is no longer
available according to the messenger paradigm where it is the code
which travels the network to
search for the data. Following these ideas, the well-known models of
server/client and
sender/receiver are no longer available, since a messenger based
client will ask no request to a
server, but goes itself to take the information and a messenger
based server will not know which
clients are taking information. Implementing distributed
applications with messengers implies a
new way of thinking: distributed applications will no more be seen
as composed of static entities
exchanging data, but as a set of mobile threads which can propel
themselves across the network
to look for resources.
Research pushes quantum spin technology toward real-world
applications
Researchers have provided "proof of concept that quantum spin
information can be locally
manipulated using high-speed electrical circuits," according to an
abstract of their paper being
published on the "Science Express" website. The findings are
significant because they
21
demonstrate a solid-state quantum logic gate
(i.e., control mechanism) that works with gating
technologies in today's electronics, today's computers. This
research also moves esoteric spin-
based technologies of spintronics and quantum computing from the
futuristic closer to within
reach of present-day possibilities. From the Barbara: Electrical
Control of Electron Spin Steers
Spin-Based Technologies Toward Real World
Santa Barbara, Calif. -- Researchers at the University of California
at Santa Barbara (UCSB) and
at the University of Pittsburgh have provided "proof of concept that
quantum spin information
can be locally manipulated using high-speed electrical circuits,"
according to the abstract of their
paper being published expeditiously at 2:00 p.m. Jan. 23 on the
"Science Express" website,
Science Magazine's rapid portal for publication of significant
research findings to appear
subsequently in print in Science.
The findings are significant because they demonstrate a solid-state
quantum logic gate (i.e.,
control mechanism) that works with gating technologies in today's
electronics, today's
computers. This research also moves esoteric spin-based technologies
of spintronics and
quantum computing from the futuristic closer to within reach of
present-day possibilities.
The research was carried out in a joint venture between David
Awschalom, Professor of Physics
and Electrical and Computer Engineering at UCSB and Director of the
Center for Spintronics
and Quantum Computation (part of the California NanoSystems
Institute [CNSI]), and Jeremy
Levy, Associate Professor of Physics at the University of Pittsburgh
and Director of the Center
for Oxide-Semiconductor Materials for Quantum Computation.
A year ago at a program on Quantum Information held at the Kavli
Institute for Theoretical
Physics at UCSB, the two physicists fell into a conversation that
led them to wonder how
electron spins in semiconductors could be manipulated in all three
dimensions.
The problem was an old one. So-called "spin resonance" techniques,
used extensively for
magnetic resonance imaging (MRI) and chemical identification,
manipulate electron and nuclear
spins in three dimensions using rapidly alternating magnetic fields.
However, such magnetic
fields are difficult to generate and control on a local scale. By
contrast, local control over electric
fields forms the basis of all of electronics, from CPUs to cell
phones. The challenge was how to
figure out a way to control electron spins using electric fields.
Awschalom and Levy realized that if a host for electrons could be
designed for which the axis of
spin rotation changed with an applied electric field, the spin
direction could itself be controlled.
That is, they could turn electric fields into effective magnetic
fields.
The two researchers realized that semiconductor sandwiches made of
aluminum gallium arsenide
and gallium arsenide could provide just this sort of control. The
material was built atomic layer
by atomic layer in the Molecular Beam Epitaxy (MBE) laboratory of
UCSB Materials Professor
Art Gossard by Robert Myers and Dan Driscoll, graduate students
jointly of Gossard and
Awschalom. Myers and Driscoll guided the deposition of the material
such that the parabolic
quantum wells (PQWs) "are grown by varying the aluminum
concentration x, ranging from 7%
at the center to 40% at the barrier, to shape the conduction band
into a parabolic potential,"
according to the paper "Gigahertz Electron Spin Manipulation Using
Voltage Controlled g-
Tensor Modulation."
The "Science Express" results provide just such a demonstration.
Awschalom's physics graduate
student, Yuichiro Kato, conducted the low temperature experiments at
Santa Barbara. He used
microfabrication techniques to construct the semiconductor devices
and operate them, and
experimental techniques developed by Awschalom and Levy to show that
the researchers have
indeed accomplished what they set out to accomplish.
Harkening back to that conversation of conceptual breakthrough
between Levy and him,
Awschalom said, "We realized that if we write down the equations of
motion of the electron that
are normally operated on by magnetic fields, we can replace the
magnetic fields with electric
22
fields. Then we thought if that is the case, we
could use miniature gates to operate on spins
instead of magnetic fields for scalable architecture for computing."
Key to understanding the far-reaching implications of this proof of
concept is the use of
electrical fields, instead of magnetic fields, to control the
electrons. Today's semiconductor,
charge-based technologies (including computers) operate by control
of electrical fields. Most
researchers approaching the spin-based paradigm for spintronics and
quantum computing
technologies have assumed that the behavior of spins must be
controlled by magnetic fields. The
prospect of controlling 100 million magnets each independently on
the equivalent of a chip has
boggled the imagination of researchers. By contrast, controlling 100
million devices with
electrical gates is what we already do in computers sitting on a
multitude of desks throughout the
world.
The parabolic quantum wells are grown with varying concentrations of
aluminum gallium
arsenide, sandwiched between gallium arsenide, flanked by metal
plates, grown by deposition on
the gallium arsenide. Think of a sandwich with Swiss cheese in the
middle (aluminum gallium
arsenide quantum wells) flanked by meat (gallium arsenide) in turn
flanked by bread (the metal
plates). The plates are the gates with one lead for the application
of electrical current that in turn
creates the electrical fields, which enable manipulation of the
electrons through the material
whose varying concentrations of aluminum govern the rotational speed
of the electrons and the
direction of their axes.
The result is "electron spin resonance (ESR) on a chip." This
engineered nanostructure allows
use of very small voltages in traditional gates to operate on
electron spin in all three directions in
which the axis can point without requiring fast alternating magnetic
fields. "The experiments
show that it is possible to build a very scalable array of quantum
gates using semiconductors in a
relatively straightforward manner," said Awschalom.
The experiments were conducted at low temperature and at a 50-micron
scale, but designing
them to operate at higher temperatures and smaller scales will
likely not be difficult, according to
Levy.
"This work describes and demonstrates how to replace magnetic with
electrical fields for the
control of spin information in semiconductors," said Levy. He
described the findings as an
"enabling technology" for spintronics and a "feasibility
demonstration" for quantum information
processing. For the latter, the size of the gates must be reduced so
that the spin of a single
electron can be precisely controlled. Such a feat would enable
electron spins to be used as
quantum bits or "qubits" for a quantum computer. "Ultimately," the
researchers write at the end
of their paper, "these electrical gates may be scaled down for
operation on single spins and in
quantum dots to form qubits."
In contrast to bits, the "1"s and "0"s of present-day computers,
qubits can be in both the "1 state"
and "0 state" at the same time, enabling a much richer and more
powerful paradigm for
computation. The orientation of an electron spin can be used to
store one qubit of information.
Quantum gates are then needed to reorient the electron spins and
perform "quantum information
processing."
And then there is the issue of spin-spin interactions, the next
research hurdle to be overcome to
enable another milestone in this line of progression toward full
feasibility demonstration for
quantum information processing. As the researchers write, "Control
over single spin operations
is sufficient for universal quantum gating, provided there is a
'backbone' of spin-spin
interactions."
But, said Awschalom. "For the industrial sector looking at quantum
information processing and
asking whether there's a future, there is a trillion dollars of
semiconductor technology for
leveraging, and electrical control of spin makes the leveraging far
more feasible and cost-
effective than control with magnets. The only thing new here is the
concept; the technology is
23
today's technology. There's nothing so special
that would keep anybody anywhere from doing
this experiment. Our hope is that people will do this much better in
the next generation."
And, adds Awschalom the physicist in contradistinction to Awschalom
the technologist, "This
work points towards a way for potentially manipulating quantum
states and entangling them to
test some of the fundamental aspects of quantum mechanics with
existing technology."
Funding for the work is being provided by the Defense Advanced
Research Projects Agency
(DARPA).
Proceedings of the 28th Annual Hawaii International Conference on
System Sciences - 1995
DCCA : A Versatile Paradigm for the Description and Development f
Concurrent Cmmunicating
Systems (Sudhir Aggarwal * Sandeep Mitra Sanjay S. Jagdale
Department of Department of Department of Computer Science Computer
Science Systems and
Industrial Engg. SUNY-Binghamton SUNY-Brockport University of
Arizona Binghamton, NY)
Abstract
Few methodologies exist that facilitate the formal specification and
prototyping of distributed
systems. In this paper, we describe certain features of the Dynamic
Coordinated Concurrent
Activities (DCCA) model. Any DCCA specification consists of a set of
largely independent
processes, each of which, however, needs to coordinate with several
of its Upeers" in the course
of its execution. Several diverse real world applications subscribe
to such a paradigm - for
example, a distributed control system for an automated factory, and
a multiprocessor cache
coherence system. DCCA is versatile enough to facilitate the
specification of the protocols in
both these systems on the same basis. Rapid prototyping and
validation is also possible
for DCCA models, as we describe in this paper. DCCA, and the
attendant toolset could be of
great use to a software engineer. 1 Introduction Advances in
techniques for software
development for distributed systems have not kept pace with those in
hardware capabilities.
Client-server models are still the norm for such systems, but these
are inherently one-to-one
mechanisms developed at the level of source code (e.g., in C). The
networking code (e.g.,
socket establishment) is also explicitly written by the user. In
recent years, therefore, there has
been a trend towards developing alternative paradigms, and towards
describing the behavior of
systems at higher, more abstract levels. Formal Description
Techniques (FDTs) are an example
of this approach. *This research was 92-101-51 supported in part by
NSF Grant CCRThe
behavior of communicating systems can be systematically described
using the mathematical
basis of FDTs. This basis is usually state transition-oriented (as
in Petri Nets (PNs) [l],
ESTELLE [2]) or interaction sequence-oriented (e.g., LOTOS). Though
ESTELLE and LOTOS
have been standardized, few techniques exist that facilitate the
description of systems
that are inherently distributed and/or for which the target
implementation environment is of a
distributed nature. In the manufacturing domain, for example, PNs
have been extensively used to
model the system protocols ([4, 61). These PN models are, however,
usually monolithic, and
extremely complex, even for relatively small systems (for an
example, refer [4]). Moreover,
prototyping for a distributed environment is hard using PN
descriptions. Models with a different
basis are, therefore, needed. We propose DCCA as a state
transition-oriented model that
recognizes the distributed ness inherent in systems such as
manufacturing controls and cache
coherence. We discuss the features and versatility of DCCA here.
Isis ([7]) is a similar paradigm.
1.1 A Control System for the Manufacturing Environment Flexible
Manufacturing Systems
(FMSs), which reflect the state-of-the-art in automated factories,
are usually comprised of a
24
group of computerized numerically controlled
(CNC) machine tools (e.g., lathes/mills/drills)
interconnected by means of transportation agents (e.g.,
robots/conveyors). Flexible
Manufacturing Cells (FMCs) refer to smaller groupings of machine
tools. For example, a single
FMC may consist of three machine tools handled by a single robot
(that loads/unloads parts
undergoing machining from these machines). Several such FMCs may be
connected in a "star"
configuration under the control of another single robot.
Report on the DNA/Biomolecular Computing Workshop
Arthur L. Delcher
Department of Computer Science
Lee Hood
Department of Molecular Biotechnology
University of Washington
Richard M. Karp
Department of Computer Science and Engineering
University of Washington
June 6-7, 1996
Abstract
This report is a summary of the DNA/Biomolecular Computing Workshop
held on June 6-7,
1996 in Arlington, VA. The purpose of the workshop was to bring
together researchers from
both computer science and biotechnology to assess the current state
of biomolecular computing,
and to identify and explore the most promising approaches and most
critical problems of this
technology. Presentations by both computer scientists and biologists
described the current state
and future directions of biomolecular computing research and of
competing computing
technologies. The consensus of the participants was that although
there is no clear road map
toward achieving an efficient biomolecular computing device, there
are many research directions
that should be pursued that could lead to such a device.
Executive Summary
The current explosion of interest in molecular computing was sparked
by Adleman's 1994
Science paper in which he showed how to use DNA to encode and
solve a "toy" 7-city traveling
salesperson problem. Although 7 cities is such a small problem that
it can be solved at first
glance by anyone, the method used could in principle be extended to
much larger instances of the
problem. This problem is particularly interesting since it is a
member of an important class of
problems known as NP-complete for which there are no known
efficient algorithms on
conventional computers. The reasons for optimism about this approach
were the minute amounts
of DNA and energy used and the large number of molecules that could
be operated on
concurrently. But questions remained about the scalability of the
approach and the cost of
materials for it.
Since then, much work has been done, both in assessing the
theoretical computational issues of
molecular computing as well as studying and improving the practical
aspects of the biochemical
systems. Molecular computing has been shown to be universal, meaning
that it is theoretically
capable of performing any computation that a conventional computer
can. Several combinations
of computational primitives, supported by a variety of biochemical
reactions, have been
proposed, and some have been tested in the laboratory.
The DNA/Biomolecular Computing Workshop was held on June 6-7, 1996
in Arlington, VA. It
was designed to bring together researchers from both computer
science and biotechnology to
assess the current state of biomolecular computing, and to identify
and explore the most
promising approaches and most critical problems of this technology.
The format of the workshop
25
consisted of informal presentations alternating
with lively open discussions. On the last
afternoon of the workshop, separate working groups of computer
scientists and of biologists met
and prepared lists of research areas to be pursued. In the final
session these lists were presented
and discussed.
The consensus view was that it is unlikely that a general-purpose
biomolecular computer capable
of outperforming a conventional electronic computer will be produced
in the near future. This
field is in its infancy, however, and more basic research needs to
be done to assess its
capabilities. There are many possibilities for molecular computing
architectures that should be
explored. Many of these, in addition to being computationally
interesting, will almost certainly
generate useful technologies for non-computational applications.
Specific research areas that
should be pursued include better characterization of the chemical
reactions involved as
computational primitives, improved or alternative techniques for
performing input/output, and
new computational models based on molecular components other than
DNA in solution.
Introduction
A series of discoveries over the past fifty years have illuminated
the extraordinary capabilities of
living cells to store and process information. We have learned that
genes encoded digitally as
nucleotide sequences serve as a kind of instruction manual for the
chemical processes within the
cell and constitute the hereditary information that is passed from
parents to their offspring.
Information storage and processing within the cell is more efficient
by many orders of magnitude
than electronic digital computation, with respect to both
information density and energy
consumption.
The field of recombinant DNA technology has developed, based on
procedures for synthesizing,
cutting, splicing, copying, replicating and reading DNA molecules,
and for separating and
classifying them according to their size or content. These processes
are fairly slow but highly
parallel, operating on as many as 10^(16) molecules at a time. We
have the ability to create
designer genomes by splicing together selected fragments from
different organisms, and cloning
them by exploiting the self-replicating ability of bacterial cells.
Recombinant DNA technology
has also led to the creation of DNA hybridization arrays that can be
used to analyze genomes and
detect mutations associated with disease.
Recombinant DNA technology is an example in which the information
processing capabilities of
biological molecules are exploited for technological purposes.
Another example is combinatorial
chemistry, in which proteins with a specific activity, such as
binding to a particular antigen, are
synthesized by an iterative process which operates on a large pool
of candidate proteins
simultaneously in vitro, alternately selecting those proteins
that are fittest with respect to the
desired activity and then mutating them randomly to obtain a new
pool of candidate proteins.
In the examples of recombinant DNA technology and combinatorial
chemistry, processes
inherent to living cells are used to analyze or modify biological
molecules, and to select those
with desirable properties. The field of biomolecular computing goes
further by using these
processes to perform information processing that has no intrinsic
connection with the processing
of biological molecules - in other words, biological molecules are
used as a medium for general-
purpose digital computation.
Biomolecular computing leapt into prominence in late 1994 through
the work of Len Adleman,
who performed a laboratory experiment in which a collection of DNA
molecules was
constructed representing the possible solutions to a toy
combinatorial problem, and recombinant
DNA techniques were used to sift through these molecules to select
the correct solution.
Subsequent work has introduced many refinements, but has for the
most part stuck to Adleman's
original generate-and-test approach, in which a large collection of
candidate solutions is
26
generated, and tests are then performed in
order to discard the incorrect solutions, until only the
correct ones remain.
The original enthusiasm, based on the extraordinary energy
efficiency and compactness of
information storage afforded by the DNA medium, together with the
extraordinary degree of
parallelism of recombinant DNA procedures, is tempered by a number
of sobering concerns.
Among these are the following:
It seems infeasible to operate on more than about l0^(16) DNA
molecules at once. Thus
the generate-and-test approach is limited to problems with at most
l0^(16) candidate
solutions. Typical problems of this size are easily dealt with by
conventional methods of
computation, leaving little advantage for DNA computing.
DNA processing is slow, so that long sequences of steps must be
avoided.
DNA processing is error-prone. Error-correction techniques are
available, but they
multiply the numbers of steps required and the numbers of molecules
processed in each
step.
In a large-scale DNA computation the cost of materials such as
oligos, ligases,
polymerases, restriction enzymes and hybridization enzymes may be
prohibitive.
Because of these considerations DNA computation as we currently
understand it may have a
very limited range of application. Certainly no "killer application"
has been identified yet.
Nevertheless, biomolecular computing is still in its infancy. Our
understanding of it, currently
limited to a particular paradigm of DNA computing, will surely
broaden as we gain a better
understanding of information storage and processing in living cells,
and the challenge of
achieving cost-effective biomolecular computing will surely serve as
a forcing function for
advances in both biotechnology and computer science. Despite the
short durat | | | | | | |
