


LieuTelecom ParisTec (46 rue Barrault)h, amphi Emeraude: comment y aller Programme14h0015h00: Petr Kuznetsov, LTCI, "WaitFreedom with Advice"Abstract: It is wellknown that most problems in distributed computing cannot be solved in a waitfree manner, i.e., ensuring that processes are able to make progress independently of each other. The failuredetector abstraction was proposed to circumvent these impossibilities. Intuitively, a failure detector provides each process with some (possibly incomplete and inaccurate) information about the current failure pattern, which allows the processes to wait for each other in order to compute a consistent output. We motivate and propose a new way of thinking about failure detectors which allows us to define, quite surprisingly, what it means to solve a distributed task waitfree using a failure detector. We separate computation processes that obtain inputs and are supposed to produce outputs from synchronization processes that are subject to failures and can query a failure detector. In our framework, we obtain a complete classification of tasks, including ones that evaded comprehensible characterization so far, such as renaming or weak symmetry breaking. 15h0015h30 : Thomas Hujsa, LIP6/UPMC, "Polynomial Sufficient Conditions of WellBehavedness for Weighted JoinFree and ChoiceFree Systems"Abstract: JoinFree Petri nets, whose transitions have at most one input place, model systems without synchronizations while ChoiceFree Petri nets, whose places have at most one output transition, model systems without conflicts. These classes respectively encompass the state machines (or Ssystems) and the marked graphs (or Tsystems). Whereas a structurally bounded and structurally live Petri net graph is said to be "wellformed", a bounded and live Petri net is said to be "wellbehaved". Necessary and sufficient conditions for the wellformedness of JoinFree and ChoiceFree nets have been known for some time, yet the behavioral properties of these classes are still not well understood. In particular efficient sufficient conditions for liveness have not been found until now. We extend results on weighted Tsystems to the class of weighted Petri nets and present transformations which preserve the feasible sequences of transitions and reduce the initial marking. We introduce a notion of "balancing" that makes possible the transformation of conservative systems into socalled "1conservative systems" while retaining the feasible transition sequences. This transformation leads to polynomial sufficient conditions of liveness for wellformed JoinFree and ChoiceFree nets. 15h3016h00: pause café16h0016h30: vie du groupe 
