Brief Announcement: Stateless Computation

July 2017

Brief Announcement: Stateless Computation

Authors:

D. Dolev, Michael Erdmann, N. Lutz, M. Schapira, and A. Zair

Abstract:

We present and explore a model of stateless and self-stabilizing distributed computation, inspired by real-world applications such as routing on today’s Internet. Processors in our model do not have an internal state, but rather interact by repeatedly mapping incoming messages ("labels") to outgoing messages and output values. While seemingly too restrictive to be of interest, stateless computation encompasses both classical game-theoretic notions of strategic interaction and a broad range of practical applications (e.g., Internet protocols, circuits, diffusion of technologies in social networks). Our main technical contribution is a general impossibility result for stateless self-stabilizationin our model, showing that even modest asynchrony (with wait times that are linear in the number of processors) can prevent a stateless protocol from reaching a stable global configuration. Furthermore, we present hardness results for verifying stateless self-stabilization. We also address several aspects of the computational power of stateless protocols. Most significantly, we show that short messages (of length that is logarithmic in the number of processors) yield substantial computational power, even on very poorly connected topologies.

Notes:

Assocaited Lab - Manipulation Lab
@conference{Erdmann-2017-102929,
author = {D. Dolev And Michael Erdmann And N. Lutz And M. Schapira And A. Zair},
title = {Brief Announcement: Stateless Computation},
booktitle = {Proceedings of ACM Symposium on Principles of Distributed Computing},
year = {2017},
month = {July},
pages = {419 - 421},
keywords = {self-stabilization, network protocols, best-response dynamics},
}
Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.