On the distributed evaluation of recursive queries over graphs

Computer Science – Logic in Computer Science

Scientific paper

Rate now

  [ 0.00 ] – not rated yet Voters 0   Comments 0

Details

28 pages, 0 figures, NOTERE 2009

Scientific paper

Logical formalisms such as first-order logic (FO) and fixpoint logic (FP) are well suited to express in a declarative manner fundamental graph functionalities required in distributed systems. We show that these logics constitute good abstractions for programming distributed systems as a whole, since they can be evaluated in a fully distributed manner with reasonable complexity upper-bounds. We first prove that FO and FP can be evaluated with a polynomial number of messages of logarithmic size. We then show that the (global) logical formulas can be translated into rule programs describing the local behavior of the nodes of the distributed system, which compute equivalent results. Finally, we introduce local fragments of these logics, which preserve as much as possible the locality of their distributed computation, while offering a rich expressive power for networking functionalities. We prove that they admit tighter upper-bounds with bounded number of messages of bounded size. Finally, we show that the semantics and the complexity of the local fragments are preserved over locally consistent networks as well as anonymous networks, thus showing the robustness of the proposed local logical formalisms.

No associations

LandOfFree

Say what you really think

Search LandOfFree.com for scientists and scientific papers. Rate them and share your experience with other people.

Rating

On the distributed evaluation of recursive queries over graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On the distributed evaluation of recursive queries over graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the distributed evaluation of recursive queries over graphs will most certainly appreciate the feedback.

Rate now

     

Profile ID: LFWR-SCP-O-370796

  Search
All data on this website is collected from public sources. Our data reflects the most accurate information available at the time of publication.