How Many Cooks Spoil the Soup?

DOI10.1007/978-3-319-48314-6_1MaRDI QIDQ2835012zbMATH OpenOpenAlexFDO

Authors Othon Michail, P. G. Spirakis

Publication date 1 December 2016

Published in Structural Information and Communication Complexity (Search for Journal in Brave)

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

Mathematics Subject Classification ID

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

Abstract: In this work, we study the following basic question: "How much parallelism does a distributed task permit?" Our definition of parallelism (or symmetry) here is not in terms of speed, but in terms of identical roles that processes have at the same time in the execution. We initiate this study in population protocols, a very simple model that not only allows for a straightforward definition of what a role is, but also encloses the challenge of isolating the properties that are due to the protocol from those that are due to the adversary scheduler, who controls the interactions between the processes. We (i) give a partial characterization of the set of predicates on input assignments that can be stably computed with maximum symmetry, i.e., $Theta(N_{min})$, where $N_{min}$ is the minimum multiplicity of a state in the initial configuration, and (ii) we turn our attention to the remaining predicates and prove a strong impossibility result for the parity predicate: the inherent symmetry of any protocol that stably computes it is upper bounded by a constant that depends on the size of the protocol.

Recommendations

• How many cooks spoil the soup?
• How many cake-eaters? Chouette, on a du monde à dîner !

Cites work

• scientific article; zbMATH DE number 996442 (Why is no real title available?)
• scientific article; zbMATH DE number 5605125 (Why is no real title available?)
• scientific article; zbMATH DE number 1179121 (Why is no real title available?)
• Atomic snapshots of shared memory
• Byzantine agreement with homonyms
• Computation in networks of passively mobile finite-state sensors
• Deterministic function computation with chemical reaction networks
• Distributed Computing: A Locality-Sensitive Approach
• Distributed computation in dynamic networks
• Leaderless Deterministic Chemical Reaction Networks
• Mediated population protocols
• On convergence and threshold properties of discrete Lotka-Volterra population protocols
• Passively mobile communicating machines that use restricted space
• Polylogarithmic-time leader election in population protocols
• Probabilistic quorum systems
• Sense of direction: Definitions, properties, and classes
• Speed Faults in Computation by Chemical Reaction Networks
• Survey of local algorithms
• The computational power of population protocols

Cited in

(1)

• How many cooks spoil the soup?

This page was built for publication: How Many Cooks Spoil the Soup?

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