Logical locality entails frugal distributed computation over graphs extended abstract

Stephane Grumbach

Description

07/22/09 WG 2009 1 Logical locality entails frugal distributed computation over graphs Stéphane Grumbach, Zhilin Wu INRIA-LIAMA

• constant time over


• order logic


• decomposable graphs


• power limited ?


• use logics


• science ?

Sujets

• Grumbach

Informations

• Publié par: pefav
• Nombre de lectures: 17
• Langue: English

Extrait

Logical locality entails frugal distributed computation over graphs

07/22/09

Stéphane Grumbach,Zhilin Wu

INRIA-LIAMA

WG 2009

1

Introduction

d

c

07/22/09

h

g

b

e

i

f

j

n

k

Find a route to nodeg

a

m

l

Build a spanning tree with me as the root

WG 2009

Logical formulas

Use logics to describeglobally the expected results   of network functionalities

Distributed computation (complexity)

2

Classical logics









First order logic (FO)

Fixpoint logics

Monadic second order logic (MSO)

…

07/22/09

The starting point: FO

WG 2009

3