Honeypots are security devices whose value lie in being probed and compromised. Traditional honeypots are servers (or devices that expose server services) that wait passively to be attacked. Client Honeypots are active security devices in search of malicious servers that attack clients. The client honeypot poses as a client and interacts with the server to examine whether an attack has occurred. Often the focus of client honeypots is on web browsers, but any client that interacts with servers can be part of a client honeypot (for example ftp, email, ssh, etc.). There are several terms that are used to describe client honeypots. Besides client honeypot, which is the generic classification, honeyclient is the other term that is generally used and accepted. However, there is a subtlety here, as "honeyclient" is actually a homograph that could also refer to the first known open source client honeypot implementation (see below), although this should be clear from the context. == Architecture == A client honeypot is composed of three components. The first component, a queuer, is responsible for creating a list of servers for the client to visit. This list can be created, for example, through crawling. The second component is the client itself, which is able to make a requests to servers identified by the queuer. After the interaction with the server has taken place, the third component, an analysis engine, is responsible for determining whether an attack has taken place on the client honeypot. In addition to these components, client honeypots are usually equipped with some sort of containment strategy to prevent successful attacks from spreading beyond the client honeypot. This is usually achieved through the use of firewalls and virtual machine sandboxes. Analogous to traditional server honeypots, client honeypots are mainly classified by their interaction level: high or low; which denotes the level of functional interaction the server can utilize on the client honeypot. In addition to this there are also newly hybrid approaches which denotes the usage of both high and low interaction detection techniques. == High interaction == High interaction client honeypots are fully functional systems comparable to real systems with real clients. As such, no functional limitations (besides the containment strategy) exist on high interaction client honeypots. Attacks on high interaction client honeypots are detected via inspection of the state of the system after a server has been interacted with. The detection of changes to the client honeypot may indicate the occurrence of an attack against that has exploited a vulnerability of the client. An example of such a change is the presence of a new or altered file. High interaction client honeypots are very effective at detecting unknown attacks on clients. However, the tradeoff for this accuracy is a performance hit from the amount of system state that has to be monitored to make an attack assessment. Also, this detection mechanism is prone to various forms of evasion by the exploit. For example, an attack could delay the exploit from immediately triggering (time bombs) or could trigger upon a particular set of conditions or actions (logic bombs). Since no immediate, detectable state change occurred, the client honeypot is likely to incorrectly classify the server as safe even though it did successfully perform its attack on the client. Finally, if the client honeypots are running in virtual machines, then an exploit may try to detect the presence of the virtual environment and cease from triggering or behave differently. === Capture-HPC === Capture [1] is a high interaction client honeypot developed by researchers at Victoria University of Wellington, NZ. Capture differs from existing client honeypots in various ways. First, it is designed to be fast. State changes are being detected using an event based model allowing to react to state changes as they occur. Second, Capture is designed to be scalable. A central Capture server is able to control numerous clients across a network. Third, Capture is supposed to be a framework that allows to utilize different clients. The initial version of Capture supports Internet Explorer, but the current version supports all major browsers (Internet Explorer, Firefox, Opera, Safari) as well as other HTTP aware client applications, such as office applications and media players. === HoneyClient === HoneyClient [2] is a web browser based (IE/FireFox) high interaction client honeypot designed by Kathy Wang in 2004 and subsequently developed at MITRE. It was the first open source client honeypot and is a mix of Perl, C++, and Ruby. HoneyClient is state-based and detects attacks on Windows clients by monitoring files, process events, and registry entries. It has integrated the Capture-HPC real-time integrity checker to perform this detection. HoneyClient also contains a crawler, so it can be seeded with a list of initial URLs from which to start and can then continue to traverse web sites in search of client-side malware. === HoneyMonkey (dead since 2010) === HoneyMonkey [3] is a web browser based (IE) high interaction client honeypot implemented by Microsoft in 2005. It is not available for download. HoneyMonkey is state based and detects attacks on clients by monitoring files, registry, and processes. A unique characteristic of HoneyMonkey is its layered approach to interacting with servers in order to identify zero-day exploits. HoneyMonkey initially crawls the web with a vulnerable configuration. Once an attack has been identified, the server is reexamined with a fully patched configuration. If the attack is still detected, one can conclude that the attack utilizes an exploit for which no patch has been publicly released yet and therefore is quite dangerous. === SHELIA (dead since 2009) === Shelia [4] is a high interaction client honeypot developed by Joan Robert Rocaspana at Vrije Universiteit Amsterdam. It integrates with an email reader and processes each email it receives (URLs & attachments). Depending on the type of URL or attachment received, it opens a different client application (e.g. browser, office application, etc.) It monitors whether executable instructions are executed in data area of memory (which would indicate a buffer overflow exploit has been triggered). With such an approach, SHELIA is not only able to detect exploits, but is able to actually ward off exploits from triggering. === UW Spycrawler === The Spycrawler [5] developed at the University of Washington is yet another browser based (Mozilla) high interaction client honeypot developed by Moshchuk et al. in 2005. This client honeypot is not available for download. The Spycrawler is state based and detects attacks on clients by monitoring files, processes, registry, and browser crashes. Spycrawlers detection mechanism is event based. Further, it increases the passage of time of the virtual machine the Spycrawler is operating in to overcome (or rather reduce the impact of) time bombs. === Web Exploit Finder === WEF [6] is an implementation of an automatic drive-by-download – detection in a virtualized environment, developed by Thomas Müller, Benjamin Mack and Mehmet Arziman, three students from the Hochschule der Medien (HdM), Stuttgart during the summer term in 2006. WEF can be used as an active HoneyNet with a complete virtualization architecture underneath for rollbacks of compromised virtualized machines. == Low interaction == Low interaction client honeypots differ from high interaction client honeypots in that they do not utilize an entire real system, but rather use lightweight or simulated clients to interact with the server. (in the browser world, they are similar to web crawlers). Responses from servers are examined directly to assess whether an attack has taken place. This could be done, for example, by examining the response for the presence of malicious strings. Low interaction client honeypots are easier to deploy and operate than high interaction client honeypots and also perform better. However, they are likely to have a lower detection rate since attacks have to be known to the client honeypot in order for it to detect them; new attacks are likely to go unnoticed. They also suffer from the problem of evasion by exploits, which may be exacerbated due to their simplicity, thus making it easier for an exploit to detect the presence of the client honeypot. === HoneyC === HoneyC [7] is a low interaction client honeypot developed at Victoria University of Wellington by Christian Seifert in 2006. HoneyC is a platform independent open source framework written in Ruby. It currently concentrates driving a web browser simulator to interact with servers. Malicious servers are detected by statically examining the web server's response for malicious strings through the usage of Snort signatures. === Monkey-Spider (dead since 2008) === Monkey-Spider [8] is a low-interaction client honeypot i
Non-human
Non-human (also spelled nonhuman) is any entity displaying some, but not enough, human characteristics to be considered a human. The term has been used in a variety of contexts and may refer to objects that have been developed with human intelligence, such as robots or vehicles. == Organisms == === Animal rights and personhood === In the animal rights movement, it is common to distinguish between "human animals" and "non-human animals". Participants in the animal rights movement generally recognize that non-human animals have some similar characteristics to those of human persons. For example, various non-human animals have been shown to register pain, compassion, memory, and some cognitive function. Some animal rights activists argue that the similarities between human and non-human animals justify giving non-human animals rights that human society has afforded to humans, such as the right to self-preservation, and some even wish for all non-human animals or at least those that bear a fully thinking and conscious mind, such as vertebrates and some invertebrates such as cephalopods, to be given a full right of personhood. === The non-human in philosophy === Contemporary philosophers have drawn on the work of Henri Bergson, Gilles Deleuze, Félix Guattari, and Claude Lévi-Strauss (among others) to suggest that the non-human poses epistemological and ontological problems for humanist and post-humanist ethics, and have linked the study of non-humans to materialist and ethological approaches to the study of society and culture. == Software and robots == The term non-human has been used to describe computer programs and robot-like devices that display some human-like characteristics. In both science fiction and in the real world, computer programs and robots have been built to perform tasks that require human-computer interactions in a manner that suggests sentience and compassion. There is increasing interest in the use of robots in nursing homes and to provide elder care. Computer programs have been used for years in schools to provide one-on-one education with children. The Tamagotchi toy required children to provide care, attention, and nourishment to keep it "alive".
Metadata management
Metadata management involves managing metadata about other data, whereby this "other data" is generally referred to as content data. The term is used most often in relation to digital media, but older forms of metadata are catalogs, dictionaries, and taxonomies. For example, the Dewey Decimal Classification is a metadata management system developed in 1876 for libraries. == Metadata schema == Metadata management goes by the end-to-end process and governance framework for creating, controlling, enhancing, attributing, defining and managing a metadata schema, model or other structured aggregation system, either independently or within a repository and the associated supporting processes (often to enable the management of content). For web-based systems, URLs, images, video etc. may be referenced from a triples table of object, attribute and value. == Scope == With specific knowledge domains, the boundaries of the metadata for each must be managed, since a general ontology is not useful to experts in one field whose language is knowledge-domain specific. == Metadata Manager == In the process of developing a knowledge management solution, creating a metadata schema, and a system in which metadata is managed, a dedicated resource may be appointed to maintain adherence to metadata standards as defined by data owners as well as general best practice. This person is responsible for curation of the business and technical layers of the metadata schema, and commonly involved with strategy and implementation. A metadata manager is not required to master all aspects, or be involved with everything concerning the solution, but an understanding of as much of the process as possible to ensure a relevant schema is developed. == Metadata management over time == Managing the metadata in a knowledge management solution is an important step in a metadata strategy. It is part of the strategy to make sure that the metadata are complete, current and correct at any given time. Managing a metadata project is also about making sure that users of the system are aware of the possibilities allowed by a well-designed metadata system and how to maximize the benefits of metadata. Regularly monitoring the metadata to ensure that the schema remains relevant is advised. === Wikipedia metadata === Wikipedia is a project that actively manages metadata for its articles and files. For example, volunteer editors carefully curate new biographical articles based on the notability (claim to fame), name, birth, and/or death dates. Similarly, volunteer editors carefully curate new architectural articles based on name, municipality, or geo coordinates. When new articles with a valid alternate spelling are added to Wikipedia that match up to existing articles based on metadata, these are then manually checked and if needed, tagged for merging. When new articles are added that are considered out of scope or otherwise unfit for Wikipedia, these are nominated for deletion. To help keep track of metadata on Wikipedia, the new Wikimedia project Wikidata was established in 2012. Click on the pictures to view more metadata about these images:
Weak stability boundary
Weak stability boundary (WSB), including low-energy transfer, is a concept introduced by Edward Belbruno in 1987. The concept explained how a spacecraft could change orbits using very little fuel. Weak stability boundary is defined for the three-body problem. This problem considers the motion of a particle P of negligible mass moving with respect to two larger bodies, P1, P2, modeled as point masses, where these bodies move in circular or elliptical orbits with respect to each other, and P2 is smaller than P1. The force between the three bodies is the classical Newtonian gravitational force. For example, P1 is the Earth, P2 is the Moon and P is a spacecraft; or P1 is the Sun, P2 is Jupiter and P is a comet, etc. This model is called the restricted three-body problem. The weak stability boundary defines a region about P2 where P is temporarily captured. This region is in position-velocity space. Capture means that the Kepler energy between P and P2 is negative. This is also called weak capture. == Background == This boundary was defined for the first time by Edward Belbruno of Princeton University in 1987. He described a Low-energy transfer which would allow a spacecraft to change orbits using very little fuel. It was for motion about Moon (P2) with P1 = Earth. It is defined algorithmically by monitoring cycling motion of P about the Moon and finding the region where cycling motion transitions between stable and unstable after one cycle. Stable motion means P can completely cycle about the Moon for one cycle relative to a reference section, starting in weak capture. P needs to return to the reference section with negative Kepler energy. Otherwise, the motion is called unstable, where P does not return to the reference section within one cycle or if it returns, it has non-negative Kepler energy. The set of all transition points about the Moon comprises the weak stability boundary, W. The motion of P is sensitive or chaotic as it moves about the Moon within W. A mathematical proof that the motion within W is chaotic was given in 2004. This is accomplished by showing that the set W about an arbitrary body P2 in the restricted three-body problem contains a hyperbolic invariant set of fractional dimension consisting of the infinitely many intersections Hyperbolic manifolds. The weak stability boundary was originally referred to as the fuzzy boundary. This term was used since the transition between capture and escape defined in the algorithm is not well defined and limited by the numerical accuracy. This defines a "fuzzy" location for the transition points. It is also due the inherent chaos in the motion of P near the transition points. It can be thought of as a fuzzy chaos region. As is described in an article in Discover magazine, the WSB can be roughly viewed as the fuzzy edge of a region, referred to as a gravity well, about a body (the Moon), where its force of gravity becomes small enough to be dominated by force of gravity of another body (the Earth) and the motion there is chaotic. A much more general algorithm defining W was given in 2007. It defines W relative to n-cycles, where n = 1,2,3,..., yielding boundaries of order n. This gives a much more complex region consisting of the union of all the weak stability boundaries of order n. This definition was explored further in 2010. The results suggested that W consists, in part, of the hyperbolic network of invariant manifolds associated to the Lyapunov orbits about the L1, L2 Lagrange points near P2. The explicit determination of the set W about P2 = Jupiter, where P1 is the Sun, is described in "Computation of Weak Stability Boundaries: Sun-Jupiter Case". It turns out that a weak stability region can also be defined relative to the larger mass point, P1. A proof of the existence of the weak stability boundary about P1 was given in 2012, but a different definition is used. The chaos of the motion is analytically proven in "Geometry of Weak Stability Boundaries". The boundary is studied in "Applicability and Dynamical Characterization of the Associated Sets of the Algorithmic Weak Stability Boundary in the Lunar Sphere of Influence". == Applications == There are a number of important applications for the weak stability boundary (WSB). Since the WSB defines a region of temporary capture, it can be used, for example, to find transfer trajectories from the Earth to the Moon that arrive at the Moon within the WSB region in weak capture, which is called ballistic capture for a spacecraft. No fuel is required for capture in this case. This was numerically demonstrated in 1987. This is the first reference for ballistic capture for spacecraft and definition of the weak stability boundary. The boundary was operationally demonstrated to exist in 1991 when it was used to find a ballistic capture transfer to the Moon for Japan's Hiten spacecraft. Other missions have used the same transfer type as Hiten, including Grail, Capstone, Danuri, Hakuto-R Mission 1 and SLIM. The WSB for Mars is studied in "Earth-Mars Transfers with Ballistic Capture" and ballistic capture transfers to Mars are computed. The BepiColombo mission of ESA should achieve ballistic capture at the WSB of Mercury in November 2026. The WSB region can be used in the field of Astrophysics. It can be defined for stars within open star clusters. This is done in "Chaotic Exchange of Solid Material Between Planetary Systems: Implications for the Lithopanspermia Hypothesis" to analyze the capture of solid material that may have arrived on the Earth early in the age of the Solar System to study the validity of the lithopanspermia hypothesis. Numerical explorations of trajectories for P starting in the WSB region about P2 show that after the particle P escapes P2 at the end of weak capture, it moves about the primary body, P1, in a near resonant orbit, in resonance with P2 about P1. This property was used to study comets that move in orbits about the Sun in orbital resonance with Jupiter, which change resonance orbits by becoming weakly captured by Jupiter. An example of such a comet is 39P/Oterma. This property of change of resonance of orbits about P1 when P is weakly captured by the WSB of P2 has an interesting application to the field of quantum mechanics to the motion of an electron about the proton in a hydrogen atom. The transition motion of an electron about the proton between different energy states described by the Schrödinger equation is shown to be equivalent to the change of resonance of P about P1 via weak capture by P2 for a family of transitioning resonance orbits. This gives a classical model using chaotic dynamics with Newtonian gravity for the motion of an electron.
Semantic heterogeneity
Semantic heterogeneity is when database schema or datasets for the same domain are developed by independent parties, resulting in differences in meaning and interpretation of data values. Beyond structured data, the problem of semantic heterogeneity is compounded due to the flexibility of semi-structured data and various tagging methods applied to documents or unstructured data. Semantic heterogeneity is one of the more important sources of differences in heterogeneous datasets. Yet, for multiple data sources to interoperate with one another, it is essential to reconcile these semantic differences. Decomposing the various sources of semantic heterogeneities provides a basis for understanding how to map and transform data to overcome these differences. == Classification == One of the first known classification schemes applied to data semantics is from William Kent in the late 80s. Kent's approach dealt more with structural mapping issues than differences in meaning, which he pointed to data dictionaries as potentially solving. One of the most comprehensive classifications is from Pluempitiwiriyawej and Hammer, "Classification Scheme for Semantic and Schematic Heterogeneities in XML Data Sources". They classify heterogeneities into three broad classes: Structural conflicts arise when the schema of the sources representing related or overlapping data exhibit discrepancies. Structural conflicts can be detected when comparing the underlying schema. The class of structural conflicts includes generalization conflicts, aggregation conflicts, internal path discrepancy, missing items, element ordering, constraint and type mismatch, and naming conflicts between the element types and attribute names. Domain conflicts arise when the semantics of the data sources that will be integrated exhibit discrepancies. Domain conflicts can be detected by looking at the information contained in the schema and using knowledge about the underlying data domains. The class of domain conflicts includes schematic discrepancy, scale or unit, precision, and data representation conflicts. Data conflicts refer to discrepancies among similar or related data values across multiple sources. Data conflicts can only be detected by comparing the underlying sources. The class of data conflicts includes ID-value, missing data, incorrect spelling, and naming conflicts between the element contents and the attribute values. Moreover, mismatches or conflicts can occur between set elements (a "population" mismatch) or attributes (a "description" mismatch). Michael Bergman expanded upon this schema by adding a fourth major explicit category of language, and also added some examples of each kind of semantic heterogeneity, resulting in about 40 distinct potential categories . This table shows the combined 40 possible sources of semantic heterogeneities across sources: A different approach toward classifying semantics and integration approaches is taken by Sheth et al. Under their concept, they split semantics into three forms: implicit, formal and powerful. Implicit semantics are what is either largely present or can easily be extracted; formal languages, though relatively scarce, occur in the form of ontologies or other description logics; and powerful (soft) semantics are fuzzy and not limited to rigid set-based assignments. Sheth et al.'s main point is that first-order logic (FOL) or description logic is inadequate alone to properly capture the needed semantics. == Relevant applications == Besides data interoperability, relevant areas in information technology that depend on reconciling semantic heterogeneities include data mapping, semantic integration, and enterprise information integration, among many others. From the conceptual to actual data, there are differences in perspective, vocabularies, measures and conventions once any two data sources are brought together. Explicit attention to these semantic heterogeneities is one means to get the information to integrate or interoperate. A mere twenty years ago, information technology systems expressed and stored data in a multitude of formats and systems. The Internet and Web protocols have done much to overcome these sources of differences. While there is a large number of categories of semantic heterogeneity, these categories are also patterned and can be anticipated and corrected. These patterned sources inform what kind of work must be done to overcome semantic differences where they still reside.
Cloud-based integration
Cloud-based integration is a form of systems integration business delivered as a cloud computing service that addresses data, process, service-oriented architecture (SOA) and application integration. == Description == Integration platform as a service (iPaaS) is a suite of cloud services enabling customers to develop, execute and govern integration flows between disparate applications. Under the cloud-based iPaaS integration model, customers drive the development and deployment of integrations without installing or managing any hardware or middleware. The iPaaS model allows businesses to achieve integration without big investment into skills or licensed middleware software. iPaaS used to be regarded primarily as an integration tool for cloud-based software applications, used mainly by small to mid-sized business. Over time, a hybrid type of iPaaS—hybrid-IT iPaaS—that connects cloud to on-premises, is becoming increasingly popular. Additionally, large enterprises are exploring new ways of integrating iPaaS into their existing IT infrastructures. Cloud integration was created to break down the data silos, improve connectivity and optimize the business process. Cloud integration has increased in popularity as the usage of Software as a Service solutions has grown. Prior to the emergence of cloud computing in the early 2000s, integration could be categorized as either internal or business to business (B2B). Internal integration requirements were serviced through an on-premises middleware platform and typically utilized a service bus to manage exchange of data between systems. B2B integration was serviced through EDI gateways or value-added network (VAN). The advent of SaaS applications created a new kind of demand which was met through cloud-based integration. Since their emergence, many such services have also developed the capability to integrate legacy or on-premises applications, as well as function as EDI gateways. The following essential features were proposed by one marketing company: Deployed on a multi-tenant, elastic cloud infrastructure Subscription model pricing (operating expense, not capital expenditure) No software development (required connectors should already be available) Users do not perform deployment or manage the platform itself Presence of integration management and monitoring features The emergence of this sector led to new cloud-based business process management tools that do not need to build integration layers - since those are now a separate service. Drivers of growth include the need to integrate mobile app capabilities with proliferating API publishing resources and the growth in demand for the Internet of things functionalities as more 'things' connect to the Internet.
Generalized distributive law
The generalized distributive law (GDL) is a generalization of the distributive property which gives rise to a general message passing algorithm. It is a synthesis of the work of many authors in the information theory, digital communications, signal processing, statistics, and artificial intelligence communities. The law and algorithm were introduced in a semi-tutorial by Srinivas M. Aji and Robert J. McEliece with the same title. == Introduction == "The distributive law in mathematics is the law relating the operations of multiplication and addition, stated symbolically, a ∗ ( b + c ) = a ∗ b + a ∗ c {\displaystyle a(b+c)=ab+ac} ; that is, the monomial factor a {\displaystyle a} is distributed, or separately applied, to each term of the binomial factor b + c {\displaystyle b+c} , resulting in the product a ∗ b + a ∗ c {\displaystyle ab+ac} " – Britannica. As it can be observed from the definition, application of distributive law to an arithmetic expression reduces the number of operations in it. In the previous example the total number of operations reduced from three (two multiplications and an addition in a ∗ b + a ∗ c {\displaystyle ab+ac} ) to two (one multiplication and one addition in a ∗ ( b + c ) {\displaystyle a(b+c)} ). Generalization of distributive law leads to a large family of fast algorithms. This includes the FFT and Viterbi algorithm. This is explained in a more formal way in the example below: α ( a , b ) = d e f ∑ c , d , e ∈ A f ( a , c , b ) g ( a , d , e ) {\displaystyle \alpha (a,\,b){\stackrel {\mathrm {def} }{=}}\displaystyle \sum \limits _{c,d,e\in A}f(a,\,c,\,b)\,g(a,\,d,\,e)} where f ( ⋅ ) {\displaystyle f(\cdot )} and g ( ⋅ ) {\displaystyle g(\cdot )} are real-valued functions, a , b , c , d , e ∈ A {\displaystyle a,b,c,d,e\in A} and | A | = q {\displaystyle |A|=q} (say) Here we are "marginalizing out" the independent variables ( c {\displaystyle c} , d {\displaystyle d} , and e {\displaystyle e} ) to obtain the result. When we are calculating the computational complexity, we can see that for each q 2 {\displaystyle q^{2}} pairs of ( a , b ) {\displaystyle (a,b)} , there are q 3 {\displaystyle q^{3}} terms due to the triplet ( c , d , e ) {\displaystyle (c,d,e)} which needs to take part in the evaluation of α ( a , b ) {\displaystyle \alpha (a,\,b)} with each step having one addition and one multiplication. Therefore, the total number of computations needed is 2 ⋅ q 2 ⋅ q 3 = 2 q 5 {\displaystyle 2\cdot q^{2}\cdot q^{3}=2q^{5}} . Hence the asymptotic complexity of the above function is O ( n 5 ) {\displaystyle O(n^{5})} . If we apply the distributive law to the RHS of the equation, we get the following: α ( a , b ) = d e f ∑ c ∈ A f ( a , c , b ) ⋅ ∑ d , e ∈ A g ( a , d , e ) {\displaystyle \alpha (a,\,b){\stackrel {\mathrm {def} }{=}}\displaystyle \sum \limits _{c\in A}f(a,\,c,\,b)\cdot \sum _{d,\,e\in A}g(a,\,d,\,e)} This implies that α ( a , b ) {\displaystyle \alpha (a,\,b)} can be described as a product α 1 ( a , b ) ⋅ α 2 ( a ) {\displaystyle \alpha _{1}(a,\,b)\cdot \alpha _{2}(a)} where α 1 ( a , b ) = d e f ∑ c ∈ A f ( a , c , b ) {\displaystyle \alpha _{1}(a,b){\stackrel {\mathrm {def} }{=}}\displaystyle \sum \limits _{c\in A}f(a,\,c,\,b)} and α 2 ( a ) = d e f ∑ d , e ∈ A g ( a , d , e ) {\displaystyle \alpha _{2}(a){\stackrel {\mathrm {def} }{=}}\displaystyle \sum \limits _{d,\,e\in A}g(a,\,d,\,e)} Now, when we are calculating the computational complexity, we can see that there are q 3 {\displaystyle q^{3}} additions in α 1 ( a , b ) {\displaystyle \alpha _{1}(a,\,b)} and α 2 ( a ) {\displaystyle \alpha _{2}(a)} each and there are q 2 {\displaystyle q^{2}} multiplications when we are using the product α 1 ( a , b ) ⋅ α 2 ( a ) {\displaystyle \alpha _{1}(a,\,b)\cdot \alpha _{2}(a)} to evaluate α ( a , b ) {\displaystyle \alpha (a,\,b)} . Therefore, the total number of computations needed is q 3 + q 3 + q 2 = 2 q 3 + q 2 {\displaystyle q^{3}+q^{3}+q^{2}=2q^{3}+q^{2}} . Hence the asymptotic complexity of calculating α ( a , b ) {\displaystyle \alpha (a,b)} reduces to O ( n 3 ) {\displaystyle O(n^{3})} from O ( n 5 ) {\displaystyle O(n^{5})} . This shows by an example that applying distributive law reduces the computational complexity which is one of the good features of a "fast algorithm". == History == Some of the problems that used distributive law to solve can be grouped as follows: Decoding algorithms: A GDL like algorithm was used by Gallager's for decoding low density parity-check codes. Based on Gallager's work Tanner introduced the Tanner graph and expressed Gallagers work in message passing form. The tanners graph also helped explain the Viterbi algorithm. It is observed by Forney that Viterbi's maximum likelihood decoding of convolutional codes also used algorithms of GDL-like generality. Forward–backward algorithm: The forward backward algorithm helped as an algorithm for tracking the states in the Markov chain. And this also was used the algorithm of GDL like generality Artificial intelligence: The notion of junction trees has been used to solve many problems in AI. Also the concept of bucket elimination used many of the concepts. == The MPF problem == MPF or marginalize a product function is a general computational problem which as special case includes many classical problems such as computation of discrete Hadamard transform, maximum likelihood decoding of a linear code over a memory-less channel, and matrix chain multiplication. The power of the GDL lies in the fact that it applies to situations in which additions and multiplications are generalized. A commutative semiring is a good framework for explaining this behavior. It is defined over a set K {\displaystyle K} with operators " + {\displaystyle +} " and " . {\displaystyle .} " where ( K , + ) {\displaystyle (K,\,+)} and ( K , . ) {\displaystyle (K,\,.)} are a commutative monoids and the distributive law holds. Let p 1 , … , p n {\displaystyle p_{1},\ldots ,p_{n}} be variables such that p 1 ∈ A 1 , … , p n ∈ A n {\displaystyle p_{1}\in A_{1},\ldots ,p_{n}\in A_{n}} where A {\displaystyle A} is a finite set and | A i | = q i {\displaystyle |A_{i}|=q_{i}} . Here i = 1 , … , n {\displaystyle i=1,\ldots ,n} . If S = { i 1 , … , i r } {\displaystyle S=\{i_{1},\ldots ,i_{r}\}} and S ⊂ { 1 , … , n } {\displaystyle S\,\subset \{1,\ldots ,n\}} , let A S = A i 1 × ⋯ × A i r {\displaystyle A_{S}=A_{i_{1}}\times \cdots \times A_{i_{r}}} , p S = ( p i 1 , … , p i r ) {\displaystyle p_{S}=(p_{i_{1}},\ldots ,p_{i_{r}})} , q S = | A S | {\displaystyle q_{S}=|A_{S}|} , A = A 1 × ⋯ × A n {\displaystyle \mathbf {A} =A_{1}\times \cdots \times A_{n}} , and p = { p 1 , … , p n } {\displaystyle \mathbf {p} =\{p_{1},\ldots ,p_{n}\}} Let S = { S j } j = 1 M {\displaystyle S=\{S_{j}\}_{j=1}^{M}} where S j ⊂ { 1 , . . . , n } {\displaystyle S_{j}\subset \{1,...\,,n\}} . Suppose a function is defined as α i : A S i → R {\displaystyle \alpha _{i}:A_{S_{i}}\rightarrow R} , where R {\displaystyle R} is a commutative semiring. Also, p S i {\displaystyle p_{S_{i}}} are named the local domains and α i {\displaystyle \alpha _{i}} as the local kernels. Now the global kernel β : A → R {\displaystyle \beta :\mathbf {A} \rightarrow R} is defined as: β ( p 1 , . . . , p n ) = ∏ i = 1 M α ( p S i ) {\displaystyle \beta (p_{1},...\,,p_{n})=\prod _{i=1}^{M}\alpha (p_{S_{i}})} Definition of MPF problem: For one or more indices i = 1 , . . . , M {\displaystyle i=1,...\,,M} , compute a table of the values of S i {\displaystyle S_{i}} -marginalization of the global kernel β {\displaystyle \beta } , which is the function β i : A S i → R {\displaystyle \beta _{i}:A_{S_{i}}\rightarrow R} defined as β i ( p S i ) = ∑ p S i c ∈ A S i c β ( p ) {\displaystyle \beta _{i}(p_{S_{i}})\,=\displaystyle \sum \limits _{p_{S_{i}^{c}}\in A_{S_{i}^{c}}}\beta (p)} Here S i c {\displaystyle S_{i}^{c}} is the complement of S i {\displaystyle S_{i}} with respect to { 1 , . . . , n } {\displaystyle \mathbf {\{} 1,...\,,n\}} and the β i ( p S i ) {\displaystyle \beta _{i}(p_{S_{i}})} is called the i t h {\displaystyle i^{th}} objective function, or the objective function at S i {\displaystyle S_{i}} . It can observed that the computation of the i t h {\displaystyle i^{th}} objective function in the obvious way needs M q 1 q 2 q 3 ⋯ q n {\displaystyle Mq_{1}q_{2}q_{3}\cdots q_{n}} operations. This is because there are q 1 q 2 ⋯ q n {\displaystyle q_{1}q_{2}\cdots q_{n}} additions and ( M − 1 ) q 1 q 2 . . . q n {\displaystyle (M-1)q_{1}q_{2}...q_{n}} multiplications needed in the computation of the i th {\displaystyle i^{\text{th}}} objective function. The GDL algorithm which is explained in the next section can reduce this computational complexity. The following is an example of the MPF problem. Let p 1 , p 2 , p 3 , p 4 , {\displaystyle p_{1},\,p_{2},\,p_{3},\,p_{4},} and p 5 {\displaystyle p_{5}} be variables such that p 1 ∈ A 1 , p 2 ∈ A 2 , p 3 ∈ A 3 , p 4 ∈ A 4 , {\displaystyle p_{1}\in