//img.uscri.be/pth/6d4a49f6d66c979facff09bad46d8f423488e00f
Cet ouvrage fait partie de la bibliothèque YouScribe
Obtenez un accès à la bibliothèque pour le lire en ligne
En savoir plus

Logical locality entails frugal distributed computation over graphs extended abstract

De
33 pages
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 ?


Voir plus Voir moins
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