Asynchronous Coordination with Constraints and Preferences

Armando Castañeda (1) , Pierre Fraigniaud (2) , Eli Gafni (3) , Sergio Rajsbaum (1) , Matthieu Roy (4)

1 Instituto de Matematicas [México]
2 IRIF (UMR_8243) - Institut de Recherche en Informatique Fondamentale
3 UCLA - Computer Science Department [Los Angeles]
4 LAAS-TSF - Équipe Tolérance aux fautes et Sûreté de Fonctionnement informatique

Adaptive renaming can be viewed as a coordination task involving a set of asynchronous agents, each aiming at grabbing a single resource out of a set of resources totally ordered by their desirability. We consider a generalization of adaptive renaming to take into account scenarios in which resources are not independent. We model constraints between resources as an undirected graph: nodes represent the ressources, and an edge between two ressources indicates that these two ressources cannot be used simultaneously. In such a setting, the sets of resources that processes may use simultaneously form independent sets. In this note, we focus on this task in a model where such independent sets are computed by wait-free processes.

Domaines: Calcul parallèle, distribué et partagé [cs.DC]

Armando Castañeda, Pierre Fraigniaud, Eli Gafni, Sergio Rajsbaum, Matthieu Roy. Asynchronous Coordination with Constraints and Preferences. 35th ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC 2016), Jul 2016, Chicago, United States. ⟨10.1145/2933057.2933081⟩. ⟨hal-01326911⟩