TY - GEN
T1 - Brief Announcement
T2 - 43rd ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, PODC 2024
AU - Charron-Bost, Bernadette
AU - Lambein-Monette, Patrick
N1 - Publisher Copyright:
© 2024 Copyright is held by the owner/author(s). Publication rights licensed to ACM.
PY - 2024/6/17
Y1 - 2024/6/17
N2 - In distributed computing, questions of computability are exquisitely sensitive to minute details of the model assumptions, and there is no universally agreed upon model of network computing. Here, we study which functions are computable by deterministic and anonymous agents in either static or dynamic networks. We consider various communication assumptions common in the literature, and in each case we strive to characterize the set of computable functions, organizing existing results as well as offering new ones, alongside new proofs which bring new understanding of this computability landscape.
AB - In distributed computing, questions of computability are exquisitely sensitive to minute details of the model assumptions, and there is no universally agreed upon model of network computing. Here, we study which functions are computable by deterministic and anonymous agents in either static or dynamic networks. We consider various communication assumptions common in the literature, and in each case we strive to characterize the set of computable functions, organizing existing results as well as offering new ones, alongside new proofs which bring new understanding of this computability landscape.
KW - anonymous networks
KW - distributed computability
U2 - 10.1145/3662158.3662784
DO - 10.1145/3662158.3662784
M3 - Conference contribution
AN - SCOPUS:85199080925
T3 - Proceedings of the Annual ACM Symposium on Principles of Distributed Computing
SP - 243
EP - 246
BT - PODC 2024 - Proceedings of the 2024 ACM Symposium on Principles of Distributed Computing
PB - Association for Computing Machinery
Y2 - 17 June 2024 through 21 June 2024
ER -