Name
Abstract | ||
|---|---|---|
Asynchronous executions of a distributed algorithm differ from each other due to the nondeterminism in the order in which the messages exchanged are handled. In many situations of interest, the asynchronous executions induced by restricting nondeterminism are more efficient, in an application-specific sense, than the others. In this work, we define partially ordered executions of a distributed algorithm as the executions satisfying some restricted orders of their actions in two different frameworks, those of the so-called event- and pulse-driven computations. The aim of these restrictions is to characterize asynchronous executions that are likely to be more efficient for some important classes of applications. Also, an asynchronous algorithm that ensures the occurrence of partially ordered executions is given for each case. Two of the applications that we believe may benefit from the restricted nondeterminism are backtrack search, in the event-driven case, and iterative algorithms for systems of linear equations, in the pulse-driven case. We provide some experimental evidence in these two cases. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1016/j.parco.2008.09.011 | parallel computing |
Keywords | DocType | Volume |
distributed backtrack search,partial orders,asynchronous algorithm,restricted order,partially syn- chronous distributed algorithms,asynchronous distributed algorithms,synchronous distributed algorithms,pulse-driven computation,restricted nondeterminism,partial orders.,partially synchronous distributed algorithms,application-specific sense,event-driven case,systems of linear equations,asynchronous execution,the pulse-driven case. keywords: synchronous distributed algorithms,backtrack search,pulse-driven case,asynchronous point-to-point network,iterative algorithm,point to point,distributed computing,partial order,linear equations,satisfiability,distributed algorithm | Journal | 35 |
Issue | ISSN | Citations |
1 | Parallel Computing | 2 |
PageRank | References | Authors |
0.42 | 16 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Ricardo C. Corrêa | 1 | 207 | 18.74 |
| Valmir C. Barbosa | 2 | 350 | 56.76 |