Synthesis in presence of dynamic links - Archive ouverte HAL Access content directly
Journal Articles Information and Computation Year : 2021

Synthesis in presence of dynamic links

(1) , (2, 3, 4, 5) , (2, 3, 4, 5) , (2, 3, 4, 5, 6) , (1)
1
2
3
4
5
6

Abstract

The problem of distributed synthesis is to automatically generate a distributed algorithm, given a target communication network and a specification of the algorithm's correct behavior. Previous work has focused on static networks with an a priori fixed message size. This approach has two shortcomings: Recent work in distributed computing is shifting towards dynamically changing communication networks rather than static ones, and an important class of distributed algorithms are so-called full-information protocols, where nodes piggy-pack previously received messages onto current messages. In this work, we consider the synthesis problem for a system of two nodes communicating in rounds over a dynamic link whose message size is not bounded. Given a network model, i.e., a set of link directions, in each round of the execution, the adversary choses an arbitrary link from the network model, restricted only by the specification, and delivers messages according to the current link's directions. Motivated by communication buses with direct acknowledge mechanisms, we further assume that nodes are aware of which messages have been delivered. We show that the synthesis problem is decidable for a network model if and only if the network model does not contain the empty link that dismisses both nodes' messages. We then extend the characterization to sequences of communication links that may contain empty links. We show that the synthesis problem is decidable in this case if and only if the number of consecutive empty links in all possible sequences is uniformly bounded from above.
Fichier principal
Vignette du fichier
dynamic-synthesis.pdf (315.06 Ko) Télécharger le fichier
Origin : Files produced by the author(s)

Dates and versions

hal-03518879 , version 1 (10-01-2022)

Identifiers

Cite

Béatrice Bérard, Benedikt Bollig, Patricia Bouyer, Matthias Függer, Nathalie Sznajder. Synthesis in presence of dynamic links. Information and Computation, 2021, pp.104856. ⟨10.1016/j.ic.2021.104856⟩. ⟨hal-03518879⟩
35 View
26 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More