Logical locality entails frugal distributed computation over graphs

Details Logical locality entails frugal distributed computation over graphs Logical locality entails frugal distributed computation over graphs

2009-04-13

arxiv.org/abs/0904.1915v1

Computer Science

Logic in Computer Science

31 pages, 0 figures

Scientific paper

First-order logic is known to have limited expressive power over finite structures. It enjoys in particular the locality property, which states that first-order formulae cannot have a global view of a structure. This limitation ensures on their low sequential computational complexity. We show that the locality impacts as well on their distributed computational complexity. We use first-order formulae to describe the properties of finite connected graphs, which are the topology of communication networks, on which the first-order formulae are also evaluated. We show that over bounded degree networks and planar networks, first-order properties can be frugally evaluated, that is, with only a bounded number of messages, of size logarithmic in the number of nodes, sent over each link. Moreover, we show that the result carries over for the extension of first-order logic with unary counting.

Affiliated with

Also associated with

No associations

Rating

Logical locality entails frugal distributed computation 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 Logical locality entails frugal distributed computation over graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Logical locality entails frugal distributed computation over graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-324050