Macroprogramming

Last updated

In computer science, macroprogramming is a programming paradigm aimed at expressing the macroscopic, global behaviour of an entire system of agents or computing devices. [1] In macroprogramming, the local programs for the individual components of a distributed system are compiled or interpreted from a macro-program typically expressed by a system-level perspective or in terms of the intended global goal. [1] The aim of macroprogramming approaches is to support expressing the macroscopic interactive behaviour of a whole distributed system of computing devices or agents in a single program, or, similarly, to promote their collective intelligence. [2] It has not to be confused with macros, the mechanism often found in programming languages (like C or Scala) to express substitution rules for program pieces.

Contents

Macroprogramming originated in the context of wireless sensor network programming [3] [4] [5] and found renewed interest in the context of the Internet of Things [6] and swarm robotics. [7] [1]

Macroprogramming shares similar goals (related to programming a system by a global perspective) with multitier programming, choreographic programming, and aggregate computing.

Context and motivation

Programming distributed systems, multi-agent systems, and collectives of software agents (e.g., robotic swarms) is difficult, for many issues (like communication, concurrency, and failure) have to be properly considered. In particular, a general recurrent problem is how to induce the intended global behaviour by defining the behaviour of the individual components or agents involved. The problem can be addressed through learning approaches, such as multi-agent reinforcement learning, or by manually defining the control program driving each component. However, addressing the problem by a fully individual (or single-node) perspective may be error-prone, because it is generally difficult to foresee the overall behaviour emerging from complex networks of activities and interactions (cf. complex systems and emergence). Therefore, researchers have started investigated ways to raise the abstraction level, promoting programming of distributed systems by a more global perspective or in terms of the overall goal to be collectively attained.

Examples

ScaFi

The following program in the ScaFi aggregate programming language [8] defines the loop control logic needed to compute a channel (a Boolean field where the devices yielding true are those connecting, through a hop-by-hop path, a source device to a target device) across a large set of situated devices interacting with neighbours.

classSelfContainedChannelextendsAggregateProgramwithSensorDefinitions{defisObstacle=sense[Boolean]("obstacle")defisSource=sense[Boolean]("source")defisDestination=sense[Boolean]("target")overridedefmain():Boolean=branch(isObstacle){false}{channel(isSource,isDestination,5)}defchannel(src:Boolean,dest:Boolean,width:Double):Boolean=dilate(distanceTo(src)+distanceTo(dest)<=distanceBetween(src,dest),width)typeOB[T]=Builtins.Bounded[T]defG[V:OB](src:Boolean,field:V,acc:V=>V,metric:=>Double):V=rep((Double.MaxValue,field)){dv=>mux(src){(0.0,field)}{minHoodPlus{val(d,v)=nbr{(dv._1,dv._2)}(d+metric,acc(v))}}}._2defdistanceTo(source:Boolean):Double=G[Double](source,0,_+nbrRange(),nbrRange())defbroadcast[V:OB](source:Boolean,field:V):V=G[V](source,field,x=>x,nbrRange())defdistanceBetween(source:Boolean,target:Boolean):Double=broadcast(source,gradient(target))defdilate(region:Boolean,width:Double):Boolean=gradient(region)<width}

What is interesting to note is that the channel function, as well as the functions that are used to implement it, namely distanceTo, distanceBetween, dilate, broadcast etc. can be interpreted not just in terms of the individual behaviour of a device, but rather by a macroscopic perspective. In fact, for instance, distanceTo(s) is used to compute the field of minimum distances from the closest device for which expression s yields true: this is effectively a distributed data structure that is sustained through processing and communication with neighbours, in a self-organising way. Semantically, such functions define a macro-level (or collective) behaviour that yields a macro-level (or collective) data structure. Such macro-level functions/behaviours can be composed together to obtain another more complex macro-level function/behaviours.

Regiment

The following program in the Regiment language [4] can be used to compute the mean temperature perceived by the whole system:

% function definitiondoSum::float(float,int)->(float,int);doSum(temperature,(sum,count)){(sum+temperature,count+1)}% functional reactive program logictemperatureRegion=rmap(fun(node){sense("temperature",node)},world);sumSignal=rfold(doSum,(0.0,0),temperatureRegion)avgSignal=smap(fun((sum,count)){sum/count},sumSignal)BASE<-avgSignal% move such information to the base station

PyoT

The following program in PyoT [9] can be used to turn on a fan if the mean temperature computed by several sensors exceeds a certain threshold.

temperatures=Resource.objects.filter(title="temp")results=[temp.GET()fortempintemperatures]avg=sum(results)/len(results)TEMP_THRESHOLD=24ifavg>TEMP_THRESHOLD:Resource.objects.get(title="fan").PUT("on")

TinyDB

In TinyDB, [10] a data-oriented macroprogramming approach is used where the programmer writes a query which turns into single-node operations and routing in a wireless sensor network.

SELECTnodeId,temperatureWHEREtemperature>kFROMsensorsSAMPLEPERIOD5minutes

See also

Related Research Articles

A distributed system is a system whose components are located on different networked computers, which communicate and coordinate their actions by passing messages to one another. Distributed computing is a field of computer science that studies distributed systems.

<span class="mw-page-title-main">Leslie Lamport</span> American computer scientist and mathematician

Leslie B. Lamport is an American computer scientist and mathematician. Lamport is best known for his seminal work in distributed systems, and as the initial developer of the document preparation system LaTeX and the author of its first manual.

<span class="mw-page-title-main">Dominator (graph theory)</span> When every path in a control-flow graph must go through one node to reach another

In computer science, a node d of a control-flow graph dominates a node n if every path from the entry node to n must go through d. Notationally, this is written as d dom n. By definition, every node dominates itself.

<span class="mw-page-title-main">Contiki</span> Real-time operating system

Contiki is an operating system for networked, memory-constrained systems with a focus on low-power wireless Internet of Things (IoT) devices. Contiki is used for systems for street lighting, sound monitoring for smart cities, radiation monitoring and alarms. It is open-source software released under the BSD-3-Clause license.

Wireless sensor networks (WSNs) refer to networks of spatially dispersed and dedicated sensors that monitor and record the physical conditions of the environment and forward the collected data to a central location. WSNs can measure environmental conditions such as temperature, sound, pollution levels, humidity and wind.

Clock synchronization is a topic in computer science and engineering that aims to coordinate otherwise independent clocks. Even when initially set accurately, real clocks will differ after some amount of time due to clock drift, caused by clocks counting time at slightly different rates. There are several problems that occur as a result of clock rate differences and several solutions, some being more acceptable than others in certain contexts.

MapReduce is a programming model and an associated implementation for processing and generating big data sets with a parallel, distributed algorithm on a cluster.

Jensen's device is a computer programming technique that exploits call by name. It was devised by Danish computer scientist Jørn Jensen, who worked with Peter Naur at Regnecentralen. They worked on the GIER ALGOL compiler, one of the earliest correct implementations of ALGOL 60. ALGOL 60 used call by name. During his Turing Award speech, Naur mentions his work with Jensen on GIER ALGOL.

<span class="mw-page-title-main">Edge computing</span> Distributed computing paradigm

Edge computing is a distributed computing model that brings computation and data storage closer to the sources of data, so that a user of a cloud application is likely to be physically closer to a server than if all servers were in one place. This is meant to make applications faster. More broadly, it refers to any design that pushes computation physically closer to a user, so as to reduce the latency compared to when an application runs on a single data centre. In the extreme case, this may simply refer to client-side computing.

A wireless ad hoc network (WANET) or mobile ad hoc network (MANET) is a decentralized type of wireless network. The network is ad hoc because it does not rely on a pre-existing infrastructure, such as routers or wireless access points. Instead, each node participates in routing by forwarding data for other nodes. The determination of which nodes forward data is made dynamically on the basis of network connectivity and the routing algorithm in use.

<span class="mw-page-title-main">Circuit complexity</span> Model of computational complexity

In theoretical computer science, circuit complexity is a branch of computational complexity theory in which Boolean functions are classified according to the size or depth of the Boolean circuits that compute them. A related notion is the circuit complexity of a recursive language that is decided by a uniform family of circuits .

Geographic routing is a routing principle that relies on geographic position information. It is mainly proposed for wireless networks and based on the idea that the source sends a message to the geographic location of the destination instead of using the network address. In the area of packet radio networks, the idea of using position information for routing was first proposed in the 1980s for interconnection networks. Geographic routing requires that each node can determine its own location and that the source is aware of the location of the destination. With this information, a message can be routed to the destination without knowledge of the network topology or a prior route discovery.

Michael John Fischer is an American computer scientist who works in the fields of distributed computing, parallel computing, cryptography, algorithms and data structures, and computational complexity.

<span class="mw-page-title-main">Friendship paradox</span> Phenomenon that most people have fewer friends than their friends have, on average

The friendship paradox is the phenomenon first observed by the sociologist Scott L. Feld in 1991 that on average, an individual's friends have more friends than that individual. It can be explained as a form of sampling bias in which people with more friends are more likely to be in one's own friend group. In other words, one is less likely to be friends with someone who has very few friends. In contradiction to this, most people believe that they have more friends than their friends have.

The Brooks–Iyengar algorithm or FuseCPA Algorithm or Brooks–Iyengar hybrid algorithm is a distributed algorithm that improves both the precision and accuracy of the interval measurements taken by a distributed sensor network, even in the presence of faulty sensors. The sensor network does this by exchanging the measured value and accuracy value at every node with every other node, and computes the accuracy range and a measured value for the whole network from all of the values collected. Even if some of the data from some of the sensors is faulty, the sensor network will not malfunction. The algorithm is fault-tolerant and distributed. It could also be used as a sensor fusion method. The precision and accuracy bound of this algorithm have been proved in 2016.

A distributed operating system is system software over a collection of independent software, networked, communicating, and physically separate computational nodes. They handle jobs which are serviced by multiple CPUs. Each individual node holds a specific software subset of the global aggregate operating system. Each subset is a composite of two distinct service provisioners. The first is a ubiquitous minimal kernel, or microkernel, that directly controls that node's hardware. Second is a higher-level collection of system management components that coordinate the node's individual and collaborative activities. These components abstract microkernel functions and support user applications.

A distributed file system for cloud is a file system that allows many clients to have access to data and supports operations on that data. Each data file may be partitioned into several parts called chunks. Each chunk may be stored on different remote machines, facilitating the parallel execution of applications. Typically, data is stored in files in a hierarchical tree, where the nodes represent directories. There are several ways to share files in a distributed architecture: each solution must be suitable for a certain type of application, depending on how complex the application is. Meanwhile, the security of the system must be ensured. Confidentiality, availability and integrity are the main keys for a secure system.

<span class="mw-page-title-main">Subsea Internet of Things</span>

Subsea Internet of Things (SIoT) is a network of smart, wireless sensors and smart devices configured to provide actionable operational intelligence such as performance, condition and diagnostic information. It is coined from the term The Internet of Things (IoT). Unlike IoT, SIoT focuses on subsea communication through the water and the water-air boundary. SIoT systems are based around smart, wireless devices incorporating Seatooth radio and Seatooth Hybrid technologies. SIoT systems incorporate standard sensors including temperature, pressure, flow, vibration, corrosion and video. Processed information is shared among nearby wireless sensor nodes. SIoT systems are used for environmental monitoring, oil & gas production control and optimisation and subsea asset integrity management. Some features of IoT's share similar characteristics to cloud computing. There is also a recent increase of interest looking at the integration of IoT and cloud computing. Subsea cloud computing is an architecture design to provide an efficient means of SIoT systems to manage large data sets. It is an adaption of cloud computing frameworks to meet the needs of the underwater environment. Similarly to fog computing or edge computing, critical focus remains at the edge. Algorithms are used to interrogate the data set for information which is used to optimise production.

Multitier programming is a programming paradigm for distributed software, which typically follows a multitier architecture, physically separating different functional aspects of the software into different tiers. Multitier programming allows functionalities that span multiple of such tiers to be developed in a single compilation unit using a single programming language. Without multitier programming, tiers are developed using different languages, e.g., JavaScript for the Web client, PHP for the Web server and SQL for the database. Multitier programming is often integrated into general-purpose languages by extending them with support for distribution.

Flix is a functional, imperative, and logic programming language developed at Aarhus University, with funding from the Independent Research Fund Denmark, and by a community of open source contributors. The Flix language supports algebraic data types, pattern matching, parametric polymorphism, currying, higher-order functions, extensible records, channel and process-based concurrency, and tail call elimination. Two notable features of Flix are its type and effect system and its support for first-class Datalog constraints.

References

  1. 1 2 3 Casadei, Roberto (2023-01-11). "Macroprogramming: Concepts, State of the Art, and Opportunities of Macroscopic Behaviour Modelling". ACM Computing Surveys. Association for Computing Machinery (ACM). 55 (13s): 1–37. arXiv: 2201.03473 . doi:10.1145/3579353. ISSN   0360-0300. S2CID   245837830.
  2. ↑ Casadei, Roberto (2023-11-01). "Artificial Collective Intelligence Engineering: A Survey of Concepts and Perspectives". Artificial Life. MIT Press. 29 (4): 433–467. arXiv: 2304.05147 . doi:10.1162/artl_a_00408. ISSN   0360-0300.
  3. ↑ Newton, Ryan; Welsh, Matt (2004). "Region streams". Proceeedings of the 1st international workshop on Data management for sensor networks in conjunction with VLDB 2004 - DMSN '04. New York, New York, USA: ACM Press. p. 78. doi:10.1145/1052199.1052213.
  4. 1 2 Newton, Ryan; Morrisett, Greg; Welsh, Matt (2007). "The regiment macroprogramming system". Proceedings of the 6th international conference on Information processing in sensor networks - IPSN '07. New York, New York, USA: ACM Press. p. 489. doi:10.1145/1236360.1236422. ISBN   978-1-59593-638-7.
  5. ↑ Gummadi, Ramakrishna; Gnawali, Omprakash; Govindan, Ramesh (2005). "Macro-programming Wireless Sensor Networks Using Kairos". Distributed Computing in Sensor Systems. Berlin, Heidelberg: Springer Berlin Heidelberg. pp. 126–140. doi:10.1007/11502593_12. ISBN   978-3-540-26422-4. ISSN   0302-9743.
  6. ↑ Júnior, Iwens G. S.; Santana, Thalia S. de; Bulcão-Neto, Renato de F.; Porter, Barry F. (2022-11-18). "The state of the art of macroprogramming in IoT: An update". Journal of Internet Services and Applications. Sociedade Brasileira de Computacao - SB. 13 (1): 54–65. doi: 10.5753/jisa.2022.2372 . ISSN   1869-0238. S2CID   254365168.
  7. ↑ Mottola, Luca; Picco, Gian Pietro (2011). "Programming wireless sensor networks". ACM Computing Surveys. Association for Computing Machinery (ACM). 43 (3): 1–51. doi:10.1145/1922649.1922656. hdl: 11311/635123 . ISSN   0360-0300. S2CID   1837434.
  8. ↑ Casadei, Roberto; Viroli, Mirko; Aguzzi, Gianluca; Pianini, Danilo (2022). "ScaFi: A Scala DSL and Toolkit for Aggregate Programming". SoftwareX. Elsevier BV. 20: 101248. doi:10.1016/j.softx.2022.101248. hdl: 11585/903248 . ISSN   2352-7110.
  9. ↑ Azzara, Andrea; Alessandrelli, Daniele; Bocchino, Stefano; Petracca, Matteo; Pagano, Paolo (2014). "PyoT, a macroprogramming framework for the Internet of Things". Proceedings of the 9th IEEE International Symposium on Industrial Embedded Systems (SIES 2014). IEEE. pp. 96–103. doi:10.1109/sies.2014.6871193. ISBN   978-1-4799-4023-3.
  10. ↑ Madden, Samuel R.; Franklin, Michael J.; Hellerstein, Joseph M.; Hong, Wei (2005). "TinyDB: an acquisitional query processing system for sensor networks". ACM Transactions on Database Systems. Association for Computing Machinery (ACM). 30 (1): 122–173. doi:10.1145/1061318.1061322. ISSN   0362-5915. S2CID   2239670.
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.