Abstract | ||
---|---|---|
In this article, we formalize locally distributed predicates, a concept previously introduced to address specific challenges associated with modular robotics and distributed debugging. A locally distributed predicate (LDP) is a novel construction for representing and detecting distributed properties in sparse-topology systems. Our previous work on LDPs presented empirical validation; here we show a formal model for two variants of the LDP algorithm, LDP-Basic and LDP-Snapshot, and establish performance bounds for these variants. We prove that LDP-Basic can detect strong stable predicates, that LDP-Snapshot can detect all stable predicates, and discuss their applicability to various distributed programming domains and to spatial computing in general. LDP detection in bounded-degree networks is shown to be scale-free, making the approach particularly attractive for specific topologies, even though LDPs are less efficient than snapshot algorithms in general distributed systems. |
Year | DOI | Venue |
---|---|---|
2011 | 10.1145/1968513.1968516 | ACM Transactions on Autonomous and Adaptive Systems (TAAS) |
Keywords | DocType | Volume |
LDP algorithm,empirical validation,specific topology,consistency,strong stable predicate,additional key words and phrases: distributed predicates,formal model,specific challenge,LDP detection,modular robotics,distributed computing,snapshots,stable predicate,bounded-degree network | Journal | 6 |
Issue | ISSN | Citations |
2 | 1556-4665 | 1 |
PageRank | References | Authors |
0.35 | 21 | 5 |
Name | Order | Citations | PageRank |
---|---|---|---|
Michael De Rosa | 1 | 228 | 18.89 |
Seth Copen Goldstein | 2 | 1951 | 232.71 |
Peter Lee 0001 | 3 | 975 | 147.71 |
Jason Campbell | 4 | 405 | 34.62 |
Padmanabhan Pillai | 5 | 1830 | 115.85 |