Faculté des sciences

A generic framework for local computation

Pouly, Marc ; Kohlas, Jürg (Dir.)

Thèse de doctorat : Université de Fribourg, 2008 ; Nr. 1603.

The distributive law known from arithmetics is one of the best tools for a computer scientist to grapple with the intractable nature of many applications. So, efficient algorithms have been developed for the computation of Fourier and Hadamard transforms, Bayesian networks, database queries, decoding problems and many more. The fact that they all benefit from the same technique suggests that a... Plus

Ajouter à la liste personnelle
    Zusammenfassung
    Hinter vielen Anwendungen der Informatik verstecken sich rechnerisch höchst anspruchsvolle Aufgaben, welche auch von modernen Computern nur dank einer geschickten Anordnung der Operationen effizient behandelt werden können. Ein geeignetes Hilfsmittel dazu bietet das aus der Arithmetik bekannte Distributivgesetz. So wurden in der Vergangenheit effiziente Verfahren zur Berechnung von Fourierund Hadamard-Transformationen, Bayesianischen Netzwerken, Datenbankanfragen oder auch Dekodierungsaufgaben entwickelt. Die Tatsache, dass all diese Methoden durch Anwendung der gleichen Technik gefunden wurden, lässt darauf schliessen, dass ihnen ein gemeinsamer generischer Algorithmus zugrunde liegt. Dies wird als lokales Rechnen bezeichnet. Die mathematischen Grundlagen, welche das lokale Rechnen ermöglichen, werden durch das axiomatische System der Valuationsalgebren definiert, welche natürlich auch die obigen Anwendungen abdeckt. Interessanterweise gibt eine solche Struktur alle Eigenschaften wieder, welche gemeinhin den Begriffen Wissen und Information zugesprochen werden. Daher kann sie auch als Ansatz zu einer algebraischen Definition dieser Begriffe verstanden werden. Der erste Teil dieser Arbeit beschreibt eine verallgemeinerte Valuationsalgebra, welche auf das Konzept von neutraler Information verzichtet. So werden bekannte Probleme mit Formalismen gelöst, deren neutrale Elemente keine endliche Darstellung besitzen. Zusätzlich identifizieren wir neue Instanzen, die überhaupt keine solchen Elemente aufweisen. Basierend auf diesem System wird der generische Algorithmus in Form der bekannten Architekturen entwickelt. Dabei bemerken wir, dass durch den Verzicht auf neutrale Information gar eine Effizienzsteigerung im Algorithmus erreicht wird. Eine interessante Klasse von Valuationsalgebren beinhaltet Formalismen, die durch eine Abbildung von Konfigurationen auf Semiringwerte charakterisiert sind. Diese Sichtweise erleichtert das Auffinden neuer Instanzen, und es wird gezeigt, dass Semiringvaluationen unter gewissen algebraischen Bedingungen Optimierungsprobleme induzieren. Dies motiviert die Entwicklung eines auf lokalem Rechnen beruhenden Algorithmus zum Auffinden von Lösungskonfigurationen { eine Problemstellung, die gewöhnlich als dynamische Programmierung bezeichnet wird. Alternativ dazu wird ein zweiter Ansatz verfolgt, der durch eine geschickte Verbindung von lokalem Rechnen mit der Theorie der Wissensdarstellung zu einer Methode führt, welche Lösungskonfigurationen nicht explizit auistet, sondern in eine Boolsche Funktion kompiliert. Durch Anwendung bekannter Abfragetechniken kann diese Funktion dann auf Fragestellungen evaluiert werden, welche die einfache Auistung von Lösungskonfigurationen bei weitem übersteigt. Abschliessend wird die Software-Architektur NENOK mit generischen Implementationen der erwähnten Algorithmen präsentiert, wobei zwei Anwendungsszenarien als Programmbibliothek und als Experimentierplattform im Vordergrund stehen. Darüber hinaus ist NENOK als verteilte Applikation konzipiert, was neue Fragen betreffend effizienter Kommunikation aufwirft. Diese werden auf theoretischer Basis und unabhängig von der Architektur des lokalen Rechnens diskutiert.
    Summary
    The distributive law known from arithmetics is one of the best tools for a computer scientist to grapple with the intractable nature of many applications. So, efficient algorithms have been developed for the computation of Fourier and Hadamard transforms, Bayesian networks, database queries, decoding problems and many more. The fact that they all benefit from the same technique suggests that a single generic algorithm must exist which solves all these problems efficiently. This essentially is the promise of local computation. The mathematical requirements for the application of local computation, which are clearly satisfied by the above examples, are pooled in an algebraic framework called valuation algebra. Moreover, this framework is general enough to be seen as an algebraic approach towards a definition of knowledge and information, since it perfectly reects the adjudicated attributes of these notions. Our first contribution concerns a generalization of the valuation algebra framework that dispenses with the concept of neutral information. This solves the problem that in some formalisms, neutral elements do not have finite representations. Further, we also identify some valuation algebra instances that do not possess neutral information at all. From this generalized framework evolves the generic algorithm in the shape of the traditional local computation architectures. As an interesting side effect, we remark that some computations even become more efficient by the measures taken to renounce neutral information. A particular subclass of valuation algebras that is extensively studied in this thesis comprises formalisms that map configurations to semiring values. Besides the usefulness of this class to discover new valuation algebra instances, it will also be shown that they give rise to optimization problems under certain conditions. This insight motivated the development of a dynamic programming scheme for the identification of solution configurations that itself exploits local computation. Another far more powerful algorithm for the same task excels through innovation. By use of local computation, solution configurations are compiled into a Boolean function which is well suited to answer a large number of queries efficiently, that go far beyond the pure enumeration of solution configurations. In parallel to the theoretical considerations, we propose in this thesis a software framework containing generic implementations of the discussed algorithms. This system called NENOK is designed to be used as a service library for all kind of local computation related applications, but may also serve as an experimental workbench for educational purposes, since it provides a multiplicity of possibilities to inspect the local computation process. Additionally, it also takes an as yet disregarded aspect of information into consideration and realizes all local computation schemes as real distributed algorithms. This in turn raises new theoretical questions on how to ensure efficient communication during the computations, which are addressed theoretically and independently of the actual local computation architecture.