Oblivious Collaboration

DOI10.1007/978-3-642-24100-0_45zbMATH Open1350.68037arXiv1106.2065OpenAlexW3037628665MaRDI QIDQ3095350FDOQ3095350

Authors: Yehuda Afek, Yakov Babichenko, Eli Gafni, Nathan Linial, Benny Sudakov, Uriel Feige 

Publication date: 28 October 2011

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Abstract: Communication is a crucial ingredient in every kind of collaborative work. But what is the least possible amount of communication required for a given task? We formalize this question by introducing a new framework for distributed computation, called {em oblivious protocols}. We investigate the power of this model by considering two concrete examples, the {em musical chairs} task $MC(n,m)$ and the well-known {em Renaming} problem. The $MC(n,m)$ game is played by $n$ players (processors) with $m$ chairs. Players can {em occupy} chairs, and the game terminates as soon as each player occupies a unique chair. Thus we say that player $P$ is {em in conflict} if some other player $Q$ is occupying the same chair, i.e., termination means there are no conflicts. By known results from distributed computing, if $mle2n-2$, no strategy of the players can guarantee termination. However, there is a protocol with $m=2n-1$ chairs that always terminates. Here we consider an oblivious protocol where in every time step the only communication is this: an adversarial {em scheduler} chooses an arbitrary nonempty set of players, and for each of them provides only one bit of information, specifying whether the player is currently in conflict or not. A player notified not to be in conflict halts and never changes its chair, whereas a player notified to be in conflict changes its chair according to its deterministic program. Remarkably, even with this minimal communication termination can be guaranteed with only $m=2n-1$ chairs. Likewise, we obtain an oblivious protocol for the Renaming problem whose name-space is small as that of the optimal nonoblivious distributed protocol. Other aspects suggest themselves, such as the efficiency (program length) of our protocols. We make substantial progress here as well, though many interesting questions remain open.

Full work available at URL: https://arxiv.org/abs/1106.2065

Recommendations

• Unobserved Delegation
• Collaborative procrastination
• Coordination without prior agreement
• On sustaining cooperation without public observations
• Vaguely motivated cooperation
• Interactive unawareness
• Collaborative Information Bottleneck
• The cost of collaboration

Mathematics Subject Classification ID

Distributed algorithms (68W15) Distributed systems (68M14) Network protocols (68M12)

Cites Work

• Self-stabilization
• Renaming in an asynchronous environment
• Self-stabilizing systems in spite of distributed control
• Atomic snapshots of shared memory
• The \(k\)-simultaneous consensus problem
• The topological structure of asynchronous computability
• Wait-Free k-Set Agreement is Impossible: The Topology of Public Knowledge
• Generalized FLP impossibility result for t-resilient asynchronous computations
• New combinatorial topology upper and lower bounds for renaming
• Reaching approximate agreement in the presence of faults
• Algorithms for the Certified Write-All Problem
• From adaptive renaming to set agreement
• The Committee Decision Problem
• Distributed Computing
• Oblivious Collaboration

Cited In (3)

• Asynchronous coordination under preferences and constraints
• Communication pattern logic: epistemic and topological views
• Oblivious Collaboration

This page was built for publication: Oblivious Collaboration

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3095350)