Abstract | ||
---|---|---|
. In this paper we give a formalization of the problem of locallydetecting the global termination of distributed algorithms on graphs. Weintroduce the notion of quasi k\Gammacoverings. Using (quasi) k\Gammacoverings, wepresent methods for showing that it is not possible to detect locally theglobal termination of local computations in certain families of graphs.These methods also allow to show that some knowledge, e.g. the size ofthe graph, is necessary in order to solve certain problems... |
Year | Venue | Keywords |
---|---|---|
1997 | SIROCCO | distributed algorithm |
Field | DocType | Citations |
Graph,Computer science,Theoretical computer science,Computation | Conference | 17 |
PageRank | References | Authors |
0.92 | 4 | 3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Yves Métivier | 1 | 594 | 53.83 |
Anca Muscholl | 2 | 1179 | 74.92 |
Pierre-andré Wacrenier | 3 | 766 | 36.69 |