Full-Information Protocols

Full-information protocols are an idealistic representation of distributed systems in which one process gets access to the entire observation history of another process whenever they communicate. However, communication may be intermittent; with gaps of increasing length, an unbounded amount of information can accumulate before being revealed. In the talk, we outline a game-theoretic model of full-information protocols for synchronous distributed systems and sketch a solution for the basic strategy synthesis problem together with a non-elementary lower bound. Further, we relate the question of deciding whether a full-information protocol can be implemented with bounded shared memory to the monadic decomposability problem for regular relations. This is joint work with Laurent Doyen and Thomas Soullard, a preliminary presentation on the synthesis results are available at https: //arxiv. org/abs/2307. 01063.

Authors

• Dietmar Berwanger

Keywords

No keywords are indexed for this paper.