Computer Science – Logic in Computer Science
Scientific paper
2009-04-21
Computer Science
Logic in Computer Science
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.
Grumbach Stephane
Wang Fang
Wu Zhilin
No associations
LandOfFree
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.
Profile ID: LFWR-SCP-O-370796