Electrical Engineering
      and Computer Sciences

Electrical Engineering and Computer Sciences

COLLEGE OF ENGINEERING

UC Berkeley

Compact Implementation of Distributed Inference Algorithms for Network

Ashima Atul

EECS Department
University of California, Berkeley
Technical Report No. UCB/EECS-2009-39
March 12, 2009

http://www.eecs.berkeley.edu/Pubs/TechRpts/2009/EECS-2009-39.pdf

In this thesis we present the compact implementation of distributed inference algorithms using a declarative programming framework. This framework provides a declarative query language for specifying and implementing distributed protocols. We show the practicality of distributed inference algorithms by applying them to network monitoring applications. There has been a growing trend towards automated generation of massive amounts of data at multiple distributed locations. These systems can take advantage of learning and inference algorithms to assemble local observations and reach global conclusions. This requires performing probabilistic inference in a distributed fashion. Distributed inference algorithms eliminate single points of failure, distribute the computation across several nodes and avoid the need to share sensitive data. The design and implementation of distributed algorithms is very challenging. Our work involves using a combination of overlays and declarative programming to simplify the design of distributed inference algorithms. Our main contribution involves using a declarative language, Overlog, to implement a set of existing probabilistic inference algorithms and evaluating their performance. We also present the conciseness of our declarative implementation. For example, we could implement Junction Tree Running Intersection Property in just 7 rules in the Overlog. We then use the distributed inference architecture for collaborative spam detection. This work is a first step towards applying distributed inference techniques for network monitoring. During the design of the application we learned that multiple factors like algorithm selection, data partitioning and aggregation play an important role when solving network monitoring problems using distributed inference. Future work in this direction involves solving the issues faced to make the spam detection application scalable and practical to provide real-time detection.

Advisor: Joseph M. Hellerstein


BibTeX citation:

@mastersthesis{Atul:EECS-2009-39,
    Author = {Atul, Ashima},
    Title = {Compact Implementation of Distributed Inference Algorithms for Network},
    School = {EECS Department, University of California, Berkeley},
    Year = {2009},
    Month = {Mar},
    URL = {http://www.eecs.berkeley.edu/Pubs/TechRpts/2009/EECS-2009-39.html},
    Number = {UCB/EECS-2009-39},
    Abstract = {In this thesis we present the compact implementation of distributed inference algorithms using a declarative programming framework. This framework provides a declarative query language for specifying and implementing distributed protocols. We show the practicality of distributed inference algorithms by applying them to network monitoring applications.

There has been a growing trend towards automated generation of massive amounts of data at multiple distributed locations. These systems can take advantage of learning and inference algorithms to assemble local observations and reach global conclusions. This requires performing probabilistic inference in a distributed fashion. Distributed inference algorithms eliminate single points of failure, distribute the computation across several nodes and avoid the need to share sensitive data.

The design and implementation of distributed algorithms is very challenging. Our work involves using a combination of overlays and declarative programming to simplify the design of distributed inference algorithms. Our main contribution involves using a declarative language, Overlog, to implement a set of existing probabilistic inference algorithms and evaluating their performance. We also present the conciseness of our declarative implementation. For example, we could implement Junction Tree Running Intersection Property in just 7 rules in the Overlog.

We then use the distributed inference architecture for collaborative spam detection. This work is a first step towards applying distributed inference techniques for network monitoring. During the design of the application we learned that multiple factors like algorithm selection, data partitioning and aggregation play an important role when solving network monitoring problems using distributed inference. Future work in this direction involves solving the issues faced to make the spam detection application scalable and practical to provide real-time detection.}
}

EndNote citation:

%0 Thesis
%A Atul, Ashima
%T Compact Implementation of Distributed Inference Algorithms for Network
%I EECS Department, University of California, Berkeley
%D 2009
%8 March 12
%@ UCB/EECS-2009-39
%U http://www.eecs.berkeley.edu/Pubs/TechRpts/2009/EECS-2009-39.html
%F Atul:EECS-2009-39