FREE ELECTRONIC LIBRARY - Dissertations, online materials

Pages:   || 2 | 3 |

«Abstract. Amorphous computing considers the problem of controlling millions of spatially distributed unreliable devices which communicate only with ...»

-- [ Page 1 ] --

Programming an Amorphous

Computational Medium

Jacob Beal

Massachusetts Institute of Technology, Cambridge MA 02139, USA

Abstract. Amorphous computing considers the problem of controlling

millions of spatially distributed unreliable devices which communicate

only with nearby neighbors. To program such a system, we need a highlevel description language for desired global behaviors, and a system to

compile such descriptions into locally executing code which robustly creates and maintains the desired global behavior. I survey existing amorphous computing primitives and give desiderata for a language describing computation on an amorphous computer. I then bring these together in Amorphous Medium Language, which computes on an amorphous computer as though it were a space-filling computational medium.

1 Introduction Increasingly, we are faced with the prospect of programming spatially embedded mesh networks composed of huge numbers of unreliable parts. Projects in such diverse fields as sensor networks (e.g. NEST [12]), peer-to-peer wireless (e.g.

RoofNet [2]), smart materials (e.g. smart dusts [17, 26]), and biological computation [18, 29, 30] all envision deployed networks of large size (ranging from thousands to trillions of nodes) where only nodes nearby in space can communicate directly, and the network as a whole approximates the physical space through which it is deployed.

Any such large spatially embedded mesh network may be considered an amorphous computer. Amorphous computing studies the problem of controlling these networks from a perspective of group behavior, taking inspiration from biological processes such as morphogenesis and regeneration, in which unreliable simple processing units (cells) communicating locally (e.g. with chemical gradients) execute a shared program (DNA) and cooperate to reliably produce an organism’s anatomy.

Controlling an amorphous computer presents serious challenges. Spatially local communication means networks may have a high diameter, and large numbers of nodes place tight constraints on sustainable communication complexity.

Moreover, large numbers also mean that node failures and replacements are a continuous process rather than isolated events, threatening the stability of the network. If we are to program in this environment, we need high-level programming abstractions to separate the behaviors being programmed from the networking and robustness issues involved in executing that program on a spatially embedded mesh network.

J.-P. Banˆtre et al. (Eds.): UPP 2004, LNCS 3566, pp. 121–136, 2005.

a c Springer-Verlag Berlin Heidelberg 2005 122 J. Beal Let us define an amorphous medium to be a hypothetical continuous computational medium filling the space approximated by an amorphous computer.

I propose that this is an appropriate basis for abstraction: high-level behavior can then be described in terms of geometric regions of the amorphous medium, then executed approximately by the amorphous computer.

In support of this hypothesis, I first detail the amorphous computing scenario, then survey existing amorphous computing primitives and describe how they can be viewed as approximating the behavior of an amorphous medium. I then present the Amorphous Medium Language, which describes program behavior in terms of nested processes occupying migrating regions of the space in which the network is embedded, describe AML’s key design elements — spatial processes, active process maintenance, and homeostasis — and illustrate the language by means of examples.

2 The Amorphous Computing Scenario The amorphous computing engineering domain presents a set of challenging requirements and prohibitions to the system designer, forcing confrontation of issues of robustness, distribution, and scalability. These constraints derive much of their inspiration from biological systems engaged in morphogenesis and regeneration, which must be accomplished by coordinating extremely large numbers of unreliable devices (cells).

The first and foremost requirement is scalability: the number of devices may be large, anywhere from thousands to millions or even billions. Biological systems, in fact, may comprise trillions of cells. Practically, this means that an algorithm is reasonable only if its per-device asymptotic complexity (e.g. space or bandwidth per device) are polynomial in log n (where n is the number of devices) — and any bound significantly greater than O(lg n) should be treated with considerable suspicion. Further, unlike ad-hoc networking and sensor networks scenarios, amorphous computing generally assumes cheap energy, local processing, and storage — in other words, as long as they do not have a high per-device asymptotic complexity, minimizing them is not of particular interest.

The network graph is determined by the spatial distribution of the devices in some Euclidean space, which collaborate via local communication. Devices are generally immobile unless the space in which they are embedded is moved (e.g. cutting and pasting ”smart paper”)1. A unit disc model is often used to create the network, in which a bidirectional link exists between two devices if and only if they are less than distance r apart. Local communication implies that the network is expected to have a high diameter, and, assuming a packet-based communication model, this means that the time for information to propagate through the network depends primarily on the number of hops it needs to travel.

Local communication also means that communication complexity is best meaNote that mobile devices might be programmed as immobile virtual devices [13, 14].

Programming an Amorphous Computational Medium 123 sured by maximum communication density — the maximum bandwidth required by a device — rather than by number of messages.

Due to the number of devices potentially involved, the system must not depend on much care and feeding of the individual devices. In general, it is assumed that every device is identically programmed, but that there can be a small amount of differentiation via initial conditions. Once the system is running, however, there is no per-device administration allowed.

There are strict limitations on the assumed network infrastructure. The system executes with partial synchrony — each device may be assumed to have a clock which ticks regularly, but the clocks may show different times, run at (boundedly) different rates, and have different phases. In addition, the system may not assume complex services not presently extended to the amorphous domain — this is applied particularly to mean no global naming, routing, or coordinate service may be assumed.

Finally, in a large, spatially distributed network of devices, failures are not isolated events. Due to the sheer number of devices, point failures are best measured by an expected rate of device failure. This suggests also that methods of analysis like half-life analysis [21] will be more useful than standard f -failure analysis. In addition, because the network is spatially embedded, outside events may cause failure of arbitrary spatial regions — larger region failures are assumed to occur less frequently. Generally stopping failures have been used, in which the failing device or link simply ceases operating. Finally, maintenance requires recovery or replacement of failed devices: in either case, the effect is that new devices join the network either individually or as a region.

3 Amorphous Computing Mechanisms Several existing amorphous computing algorithms will serve as useful primitives for constructing a language. Each mechanism summarized here has been implemented as a code module and demonstrated in simulation. Together they are a powerful toolkit from which primitives for high-level languages can be constructed.

3.1 Shared Neighborhood Data This simple mechanism allows neighboring devices to communicate by means of a shared-memory region, similar to the systems described in [7, 32]. Each device maintains a table of key-value pairs which it wishes to share (for example, the keys might be variable names and the values their bindings). Periodically each device transmits its table to its neighbors, informing them that it is still a neighbor and refreshing their view of its shared memory. Conversely, a neighbor is removed from the table if more than a certain time has elapsed since its last refresh. The module can then be queried for the set of neighbors, and the values its neighbors most recently held for any key in its table.

Shared neighborhood data can also be viewed as a sample of the amorphous medium within a unit neighborhood. Aggregate functions of the neighborhood 124 J. Beal data (e.g. average or maximum) are then approximations of the same functions on a neighborhood of the amorphous medium.

Maintaining shared neighborhood data requires storage and communication density proportional to the number of values being stored, size of the values, and number of neighbors.

3.2 Regions The region module maintains labels for contiguous sets of devices, approximating connected regions of the amorphous medium, using a mechanism similar to that in [31]. A Region is defined by a name and a boolean membership function.

When seeded in one or more devices, a Region spreads via shared neighborhood data to all adjoining devices that satisfy the membership test. When a Region is deallocated, a garbage collection mechanism spreads the deallocation throughout the participating devices, attempting to ensure that the defunct Region is removed totally.

Note that failures or evolving system state may separate a Region into disconnected components. While these are still logically the same Region, and may rejoin into a single connected component in the future, information will not generally pass between disconnected components. As a result, the state of disconnected components of a Region may evolve separately, and in particular garbage collection is only guaranteed to be effective in a connected component of a Region.

Regions are organized into a tree, with every device belonging to the root Region. In order for a device to be a member of a Region, it must also be a member of that Region’s parent in the tree. This implicit compounding of membership tests allows Regions to exhibit stack-like behavior which will be useful for establishing execution scope in a high-level language.

Maintaining Regions requires storage and communication density proportional to the number of Regions being maintained, due to the maintenance of shared neighborhood data. Garbage collecting a Region requires time proportional to the diameter of the Region.

3.3 Gossip The gossip communication module [6] propagates information throughout a Region via shared neighborhood data, after the fashion of flooding algorithms [22].

Gossip is all-to-all communication: each item of gossip has a merge function that combines local state with neighbor information to produce a merged whole.

When an item of gossip is garbage-collected, the deallocation propagates slowly to prevent regrowth into areas which have already been garbage-collected.

Gossip requires storage and communication density proportional to the number and size of gossip items being maintained in each Region of which a device is a member, due to the maintenance of shared neighborhood data. Garbage collecting an item of gossip takes time proportional to the diameter of the region.

Programming an Amorphous Computational Medium 125

3.4 Consensus and Reduction Non-failing devices participating in a strong consensus process must all choose the same value if any of them choose a value, and the chosen value must be held by at least one of the participants. Reduction is a generalization of consensus in which the chosen value is an aggregate function of values held by the participants (e.g. sum or average) — as before, all non-failing devices complete the operation holding the same value.

The Paxos consensus algorithm [20] has been demonstrated in an amorphous computing context [6], but scales badly. A gossip-based algorithm currently under development promises much better results: it appears that running a robust reduction process on a Region may require only storage and communication density logarithmic in the diameter of the Region and time linear in the diameter of the Region.

3.5 Read/Write Atomic Objects Atomic consistency means that all transactions with an object can be viewed as happening in some order, even if they overlap in time. If we designate a Region of an amorphous medium as a read/write atomic object, then reading or writing values at any point in the Region produces a consistent view of the value held by the Region over time.

Using consensus and reduction, quorum-based atomic transactions can be supported by a reconfigurable set of devices [23,15]. This has been demonstrated in simulation for amorphous computing [6], and scales as the underlying consensus and reduction algorithms do.

3.6 Active Gradient An active gradient [9, 11, 8] maintains a hop-count upwards from its source or sources — a set of devices which declare themselves to have count value zero — giving an approximation of radial distance in the amorphous medium, useful for establishing Regions. Points in the gradient converge to the minimum hop-count and repairs their values when they become invalid. The gradient runs within a Region, and may be further bounded (e.g. with a maximum number of hops).

When the supporting sources disappear, the gradient is garbage-collected; as in the case of gossip items, the garbage collection propagates slowly to prevent unwanted regrowth into previously garbage collected areas. A gradient may also carry version information, allowing its source to change more smoothly. Figure 1 shows an active gradient being used to maintain a line.

Maintaining a gradient requires a constant amount of storage and communication density for every device in range of the gradient, and garbage collecting a gradient takes time linear in the diameter of its extent.

3.7 Persistent Node A Persistent Node [4] is a robust mobile virtual object that occupies a ball in the amorphous medium (See Figure 2). A Persistent Node is a read/write 126 J. Beal

–  –  –

Pages:   || 2 | 3 |

Similar works:

«Chemical and Biological Control of Silvery Threadmoss (Bryum argenteum Hedw.) on Creeping Bentgrass Putting Greens Angela Rose Post Dissertation submitted to the faculty of the Virginia Polytechnic Institute and State University in partial fulfillment of the requirements for the degree of Doctor of Philosophy in Plant Pathology, Physiology and Weed Science Shawn D. Askew Antonius B. Baudoin Jacob N. Barney Erik H. Ervin David S. McCall July 2nd, 2013 Blacksburg, Virginia Keywords: biological...»

«RANGING PATTERNS AND HABITAT UTILIZATION OF NORTHERN RIVER OTTERS, LONTRA CANADENSIS, IN MISSOURI: IMPLICATIONS FOR THE CONSERVATION OF A REINTRODUCED SPECIES by DEBORAH DOROTHY BOEGE-TOBIN M.S., Animal Behavior & Marine Biology, Florida Atlantic University, 1994 B.S., Ecology, Ethology, & Evolution, University of Illinois @ Urbana-Champaign, 1991 A DISSERTATION Submitted to the Graduate School of the UNIVERSITY OF MISSOURIST. LOUIS In partial Fulfillment of the Requirements for the Degree...»

«Net primary production of terrestrial ecosystems in China and its equilibrium responses to changes in climate and atmospheric CO2 concentration X. Xiao1,2, J.M. Melillo1, D.W. Kicklighter1, Y. Pan1, A.D. McGuire3 and J. Helfrich1 1 The Ecosystems Center, Marine Biological Laboratory, Woods Hole, MA 02543 2 The Joint Program on the Science and Policy of Global Change, Massachusetts Institute of Technology, Cambridge, MA 02139 3 Institute of Arctic Biology, University of Alaska, Fairbanks, AK...»

«New Zealand Data Sheet APO-PREDNISONE Prednisone 1mg, 2.5mg, 5mg and 20mg Tablets Presentation APO-PREDNISONE 1mg tablets are round, white, biconvex, 5.5mm in diameter and identified P over 1 on one side. Each tablet contains 1mg prednisone and typically weighs 80mg. APO-PREDNISONE 2.5mg tablets are round, white, biconvex, 6.0mm in diameter and identified P over 2.5 on one side. Each tablet contains 2.5mg prednisone and typically weighs 87mg. APO-PREDNISONE 5mg tablets are round, white,...»

«Stud. Mar., 25(1): 1-20 UDK: 589.9(262.3) DYNAMICS OF PHYTOPLANKTON IN BOKA KOTORSKA BAY Dragana Drakulović1, Nenad Vuksanović1 and Danijela Joksimović1 1 Institute of Marine Biology, P.O. Box 69, 85330, Kotor, Montenegro E-mail: ddragana@t-com.me ABSTRACT Distribution of phytoplankton and their composition were presented in Boka Kotorska Bay, small semi-enclosed bay, situated in south-eastern part of Adriatic Sea. Samples were taken at seven stations in the whole Boka Kotorska Bay, on...»

«Molecular Mechanisms of Differential Activation of Naive T cells by Weak and Strong Antigen-presenting Cells Inaugural-Dissertation zur Erlangung des Doktorgrades Dr. rer. nat. der Fakultät für Biologie an der Universität Duisburg-Essen vorgelegt von Eloho Etemire aus Oteri-Igbide, Delta State, Nigeria. August 2013 Die Arbeit zugrunde liegenden vorliegenden Experimente wurden durchgeführt beginnend am Institut für Molekulare und Klinische Immunologie der Otto von Guericke Universität,...»

«RACINES Tél : + 229 21 04 00 83 Email : racinesbenin@ngracinesbenin.org Site web: ongracinesbenin.org DEPISTAGE ET PRISE EN CHARGE GLOBALE DES PVVIH DANS LES COMMUNES DE COTONOU ET DE SAVALOU Contexte d’intervention Contexte national Le Bénin est un pays à épidémie mixte. Depuis 2002, la prévalence du VIH s’est stabilisée autour de 2%. Malgré cette tendance à la stabilisation, il existe des poches de concentration de fortes prévalences au sein de certaines populations clés plus...»

«Foraging Behaviour of the European Starling Sturnus vulgaris. A Case Study to Explore the Potential Implications of Climate Change on Ground-probing Birds Caroline M. Rhymer School of Biology Faculty of Science, Agriculture and Engineering A thesis submitted for the degree of Doctor of Philosophy, December 2012, Newcastle University i Table of Contents Table of Contents List of Figures and Tables Abstract Acknowledgement Chapter 1: General Introduction 1.1 Main study species: European Starling...»

«2015 Spring Gobbler Survey Report Gary W. Norman Wild Turkey Project Leader Since 1987 the Department of Game and Inland Fisheries (DGIF) has sought the assistance of avid spring gobbler hunters to participate in this survey which is intended to provide important biological information about turkey populations. This long-term survey provides important information for the Department’s wild turkey management program. Furthermore, the survey provides an excellent platform to survey hunter...»


«VI PROFESSORSHIPS AND READERSHIPS LECTURESHIPS HONORS FELLOWSHIPS FELLOWS PRIZES AND AWARDS ENROLLMENT Professorships and Readerships Winifred L. Arms Professorship in the Arts and Humanities. Established in 1982 by Winifred Arms in memory of her husband, Robert A. Arms ’27, the Arms Professorship is held by a distinguished member of the faculty concerned with one of the fields of artistic or literary expression. Paula R. and David J. Avenius 1941 Professorship. This professorship recognizes...»

«FRANCIS CRICK SALK INSTITUTE FOR BIOLOGICAL STUDIES/MARC LIEBERMAN 8 june 1916. 28 july 2004 PROCEEDINGS OF THE AMERICAN PHILOSOPHICAL SOCIETY VOL. 150, NO. 3, SEPTEMBER 2006 biographical memoirs F RANCIS CRICK, on whose behalf it would not be unreasonable to claim that he was the greatest and most influential theoretician of biology since Charles Darwin, died of colon cancer in La Jolla, California, on 28 July 2004, at the age of eighty-eight. My declaring that Crick was a “theoretician of...»

<<  HOME   |    CONTACTS
2016 www.dissertation.xlibx.info - Dissertations, online materials

Materials of this site are available for review, all rights belong to their respective owners.
If you do not agree with the fact that your material is placed on this site, please, email us, we will within 1-2 business days delete him.