Formal Guarantees of Timely Progress for Distributed Knowledge Propagation

Saswata Paul
(Rensselaer Polytechnic Institute)
Stacy Patterson
(Rensselaer Polytechnic Institute)
Carlos Varela
(Rensselaer Polytechnic Institute)

Autonomous air traffic management (ATM) operations for urban air mobility (UAM) will necessitate the use of distributed protocols for decentralized coordination between aircraft. As UAM operations are time-critical, it will be imperative to have formal guarantees of progress for the distributed protocols used in ATM. Under asynchronous settings, message transmission and processing delays are unbounded, making it impossible to provide deterministic bounds on the time required to make progress. We present an approach for formally guaranteeing timely progress in a Two-Phase Acknowledge distributed knowledge propagation protocol by probabilistically modeling the delays using theories of the Multicopy Two-Hop Relay protocol and the M/M/1 queue system. The guarantee states a probabilistic upper bound to the time for progress as a function of the probabilities of the total transmission and processing delays being less than two given values. We also showcase the development of a library of formal theories, that is tailored towards reasoning about timely progress in distributed protocols deployed in airborne networks, in the Athena proof assistant.

In Marie Farrell and Matt Luckcuck: Proceedings Third Workshop on Formal Methods for Autonomous Systems (FMAS 2021), Virtual, 21st-22nd of October 2021, Electronic Proceedings in Theoretical Computer Science 348, pp. 73–91.
Published: 21st October 2021.

ArXived at: https://dx.doi.org/10.4204/EPTCS.348.5 bibtex PDF
References in reconstructed bibtex, XML and HTML format (approximated).
Comments and questions to: eptcs@eptcs.org
For website issues: webmaster@eptcs.org