More Web Proxy on the site http://driver.im/

research-article

Stone age distributed computing

Authors:

Roger WattenhoferAuthors Info & Claims

PODC '13: Proceedings of the 2013 ACM symposium on Principles of distributed computing

Pages 137 - 146

https://doi.org/10.1145/2484239.2484244

Published: 22 July 2013 Publication History

Abstract

A new model that depicts a network of randomized finite state machines operating in an asynchronous environment is introduced. This model, that can be viewed as a hybrid of the message passing model and cellular automata is suitable for applying the distributed computing lens to the study of networks of sub-microprocessor devices, e.g., biological cellular networks and man-made nano-networks.

Although the computation and communication capabilities of each individual device in the new model are, by design, much weaker than those of an abstract computer, we show that some of the most important and extensively studied distributed computing problems can still be solved efficiently.

References

[1]

H. Abelson, D. Allen, D. Coore, C. Hanson, G. Homsy, T. F. Knight, Jr., R. Nagpal, E. Rauch, G. J. Sussman, and R. Weiss. Amorphous computing. Commun. ACM, 43(5):74--82, May 2000.

Digital Library

[2]

Y. Afek, N. Alon, Z. Bar-Joseph, A. Cornejo, B. Haeupler, and F. Kuhn. Beeping a maximal independent set. In DISC, pages 32--50, 2011.

Digital Library

[3]

Y. Afek, N. Alon, O. Barad, E. Hornstein, N. Barkai, and Z. Bar-Joseph. A Biological Solution to a Fundamental Distributed Computing Problem. Science, 331(6014):183--185, Jan. 2011.

[4]

I. F. Akyildiz, J. M. Jornet, and M. Pierobon. Nanonetworks: a new frontier in communications. Commun. ACM, 54(11):84--89, Nov. 2011.

Digital Library

[5]

N. Alon, L. Babai, and A. Itai. A fast and simple randomized parallel algorithm for the maximal independent set problem. J. Algorithms, 7:567--583, December 1986.

Digital Library

[6]

D. Angluin, J. Aspnes, Z. Diamadi, M. J. Fischer, and R. Peralta. Computation in networks of passively mobile finite-state sensors. Distributed Computing, pages 235--253, mar 2006.

Digital Library

[7]

D. Angluin, J. Aspnes, and D. Eisenstat. Fast computation by population protocols with a leader. Distributed Computing, 21(3):183--199, sep 2008.

Digital Library

[8]

J. Aspnes and E. Ruppert. An introduction to population protocols. In B. Garbinato, H. Miranda, and L. Rodrigues, editors, Middleware for Network Eccentric and Mobile Applications, pages 97--120. Springer-Verlag, 2009.

[9]

B. Awerbuch. Complexity of network synchronization. J. ACM, 32(4):804--823, 1985.

Digital Library

[10]

B. Awerbuch, B. Patt-Shamir, D. Peleg, and M. E. Saks. Adapting to asynchronous dynamic networks (extended abstract). In STOC, pages 557--570, 1992.

Digital Library

[11]

B. Awerbuch and D. Peleg. Network synchronization with polylogarithmic overhead. In FOCS, pages 514--522, 1990.

Digital Library

[12]

L. Barenboim and M. Elkin. Distributed (delta 1)-coloring in linear (in delta) time. In STOC, pages 111--120, 2009.

Digital Library

[13]

L. Barenboim and M. Elkin. Deterministic distributed vertex coloring in polylogarithmic time. J. ACM, 58(5):23, 2011.

Digital Library

[14]

L. Barenboim, M. Elkin, S. Pettie, and J. Schneider. The locality of distributed symmetry breaking. CoRR, abs/1202.1983, 2012.

[15]

M. Bellare, O. Goldreich, and M. Sudan. Free bits, pcps, and nonapproximability-towards tight results. SIAM J. Comput., 27(3):804--915, 1998.

Digital Library

[16]

Y. Benenson. Biomolecular computing systems: principles, progress and potential. Nat Rev Genet, 13(7):455--468, July 2012.

[17]

Y. Benenson, T. Paz-Elizur, R. Adar, E. Keinan, Z. Livneh, and E. Shapiro. Programmable and autonomous computing machine made of biomolecules. Nature, 414(6862):430--434, Nov. 2001.

[18]

D. Brand and P. Zafiropulo. On communicating finite-state machines. J. ACM, 30:323--342, April 1983.

Digital Library

[19]

I. Chatzigiannakis and P. G. Spirakis. The dynamics of probabilistic population protocols. In DISC, DISC '08, pages 498--499, Berlin, Heidelberg, 2008. Springer-Verlag.

Digital Library

[20]

I. Chlamtac and S. Kutten. On Broadcasting in Radio Networks--Problem Analysis and Protocol Design. Communications, IEEE Transactions on {legacy, pre - 1988}, 33(12):1240--1246, 1985.

[21]

R. Cole and U. Vishkin. Deterministic coin tossing with applications to optimal parallel list ranking. Inf. Control, 70(1):32--53, July 1986.

Digital Library

[22]

A. Cornejo and F. Kuhn. Deploying wireless networks with beeps. In DISC, pages 148--162, 2010.

Digital Library

[23]

Y. Emek, J. Seidel, and R. Wattenhofer. Distributed computability: Anonymity, revocability, and randomization. A manuscript.

[24]

R. Flury and R. Wattenhofer. Slotted Programming for Sensor Networks. In IPSN, April 2010.

Digital Library

[25]

M. Gardner. The fantastic combinations of John Conway's new solitaire game "life". Scientific American, 223(4):120--123, 1970.

[26]

P. Gordon. Numerical Cognition Without Words: Evidence from Amazonia. Science, 306(5695):496--499, Oct. 2004.

[27]

A. Israeli and A. Itai. A fast and simple randomized parallel algorithm for maximal matching. Inf. Process. Lett., 22(2):77--80, 1986.

Digital Library

[28]

K. Kothapalli, C. Scheideler, M. Onus, and C. Schindelhauer. Distributed Coloring in Õ(√log n) Bit Rounds. In IPDPS, 2006.

Digital Library

[29]

F. Kuhn. Weak graph colorings: distributed algorithms and applications. In SPAA, pages 138--144, New York, NY, USA, 2009. ACM.

Digital Library

[30]

F. Kuhn, T. Moscibroda, and R. Wattenhofer. What cannot be computed locally! In PODC, pages 300--309, 2004.

Digital Library

[31]

C. Lenzen and R. Wattenhofer. MIS on trees. In PODC, pages 41--48, New York, NY, USA, 2011.

Digital Library

[32]

N. Linial. Locality in distributed graph algorithms. SIAM J. Comput., 21:193--201, Feb. 1992.

Digital Library

[33]

M. Luby. A simple parallel algorithm for the maximal independent set problem. SIAM J. Comput., 15:1036--1055, November 1986.

Digital Library

[34]

N. A. Lynch. Distributed Algorithms. Morgan Kaufmann, 1st edition, 1996.

Digital Library

[35]

Y. Métivier, J. M. Robson, N. Saheb-Djahromi, and A. Zemmari. About randomised distributed graph colouring and graph partition algorithms. Inf. Comput., 208(11):1296--1304, Nov. 2010.

Digital Library

[36]

Y. Métivier, J. M. Robson, N. Saheb-Djahromi, and A. Zemmari. An optimal bit complexity randomised distributed MIS algorithm. Distributed Computing, 23(5--6):331--340, Jan. 2011.

[37]

O. Michail, I. Chatzigiannakis, and P. G. Spirakis. New Models for Population Protocols. Synthesis Lectures on Distributed Computing Theory. Morgan & Claypool Publishers, 2011.

[38]

K. Nakamura. Asynchronous cellular automata and their computational ability. Syst Comput Controls, 5(5):58--66, 1974.

[39]

C. L. Nehaniv. Asynchronous automata networks can emulate any synchronous automata network. Journal of Algebra, pages 1--21, Dec. 2003.

[40]

D. Peleg. Distributed computing: a locality-sensitive approach. Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 2000.

Digital Library

[41]

D. Sadava. Life: The Science of Biology. Sinauer Associates, 2011.

[42]

J. Schneider and R. Wattenhofer. An optimal maximal independent set algorithm for bounded-independence graphs. Distributed Computing, 22(5--6):349--361, 2010.

[43]

J. Schneider and R. Wattenhofer. Distributed Coloring Depending on the Chromatic Number or the Neighborhood Growth. In SIROCCO, June 2011.

Digital Library

[44]

J. Suomela. Survey of local algorithms. To appear in ACM Computing Surveys, 2012. http://www.cs.helsinki.fi/u/josuomel/doc/local-survey.pdf.

Digital Library

[45]

M. Szegedy and S. Vishwanathan. Locality based graph coloring. In STOC, pages 201--207, 1993.

Digital Library

[46]

L. G. Valiant. Parallel computation. In 7th IBM Symp. on Math. Foundations of Computer Science, 1982.

[47]

J. von Neumann. Theory of Self-Reproducing Automata. University of Illinois Press, Champaign, IL, USA, 1966.

Digital Library

[48]

S. Wolfram. A new kind of science. Wolfram Media, Champaign, Illinois, 2002.

Digital Library

Cited By

Giakkoupis GTurau VZiccardi IKuznetsov PGelles ROlivetti D(2024)Brief Announcement: Self-Stabilizing MIS Computation in the Beeping ModelProceedings of the 43rd ACM Symposium on Principles of Distributed Computing10.1145/3662158.3662811(87-90)Online publication date: 17-Jun-2024
https://dl.acm.org/doi/10.1145/3662158.3662811
Johnen CDevismes SMazoit FIlcinkas DKuznetsov PGelles ROlivetti D(2024)Asynchronous Self-stabilization Made Fast, Simple, and Energy-efficientProceedings of the 43rd ACM Symposium on Principles of Distributed Computing10.1145/3662158.3662803(538-548)Online publication date: 17-Jun-2024
https://dl.acm.org/doi/10.1145/3662158.3662803
Delporte-Gallet CFauconnier HFraigniaud PRajsbaum STravers C(2024)Non-negotiating Distributed ComputingStructural Information and Communication Complexity10.1007/978-3-031-60603-8_12(208-225)Online publication date: 23-May-2024
https://doi.org/10.1007/978-3-031-60603-8_12
Show More Cited By

Index Terms

Stone age distributed computing
1. Theory of computation
  1. Logic
  2. Models of computation

Recommendations

Input-driven languages are linear conjunctive

Linear conjunctive grammars define the same family of languages as one-way real-time cellular automata (A. Okhotin, "On the equivalence of linear conjunctive grammars to trellis automata", RAIRO ITA, 2004), and this family is known to be incomparable ...
Iterated uniform finite-state transducers on unary languages
Abstract
An iterated uniform finite-state transducer executes the same length-preserving transduction in iterative sweeps. The first sweep occurs on the input string, while any subsequent sweep works on the output of the previous one. All sweeps always ...
Highlights
- We study Iterated Uniform Finite-State Transducers (IUFSTs) working on unary languages.
- We compare IUFSTs size with that of unary classical finite-state automata.
- We relate IUFSTs and one-way cellular automata recognition power.
Iterated Uniform Finite-State Transducers on Unary Languages
SOFSEM 2021: Theory and Practice of Computer Science
Abstract
We consider the model of an iterated uniform finite-state transducer, which executes the same length-preserving transduction in iterative sweeps. The first sweep takes place on the input string, while any subsequent sweep works on the output of ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

PODC '13: Proceedings of the 2013 ACM symposium on Principles of distributed computing

July 2013

422 pages

ISBN:9781450320658

DOI:10.1145/2484239

General Chair:
Panagiota Fatourou
FORTH ICS & University of Crete, Greece
,
Program Chair:
Gadi Taubenfeld
IDC, Israel

Copyright © 2013 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 22 July 2013

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

PODC '13

Sponsor:

PODC '13: ACM Symposium on Principles of Distributed Computing

July 22 - 24, 2013

Québec, Montréal, Canada

Acceptance Rates

PODC '13 Paper Acceptance Rate 37 of 145 submissions, 26%;

Overall Acceptance Rate 740 of 2,477 submissions, 30%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

37
Total Citations
View Citations
730
Total Downloads

Downloads (Last 12 months)30
Downloads (Last 6 weeks)1

Reflects downloads up to 11 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Giakkoupis GTurau VZiccardi IKuznetsov PGelles ROlivetti D(2024)Brief Announcement: Self-Stabilizing MIS Computation in the Beeping ModelProceedings of the 43rd ACM Symposium on Principles of Distributed Computing10.1145/3662158.3662811(87-90)Online publication date: 17-Jun-2024
https://dl.acm.org/doi/10.1145/3662158.3662811
Johnen CDevismes SMazoit FIlcinkas DKuznetsov PGelles ROlivetti D(2024)Asynchronous Self-stabilization Made Fast, Simple, and Energy-efficientProceedings of the 43rd ACM Symposium on Principles of Distributed Computing10.1145/3662158.3662803(538-548)Online publication date: 17-Jun-2024
https://dl.acm.org/doi/10.1145/3662158.3662803
Delporte-Gallet CFauconnier HFraigniaud PRajsbaum STravers C(2024)Non-negotiating Distributed ComputingStructural Information and Communication Complexity10.1007/978-3-031-60603-8_12(208-225)Online publication date: 23-May-2024
https://doi.org/10.1007/978-3-031-60603-8_12
Maldonado DMontealegre PRíos-Wilson M(2024)The Hardness of Local Certification of Finite-State DynamicsLATIN 2024: Theoretical Informatics10.1007/978-3-031-55598-5_4(51-65)Online publication date: 6-Mar-2024
https://doi.org/10.1007/978-3-031-55598-5_4
Giakkoupis GZiccardi IOshman RNolin AHalldorsson MBalliu A(2023)Distributed Self-Stabilizing MIS with Few States and Weak CommunicationProceedings of the 2023 ACM Symposium on Principles of Distributed Computing10.1145/3583668.3594581(310-320)Online publication date: 19-Jun-2023
https://dl.acm.org/doi/10.1145/3583668.3594581
Suen JNavlakha S(2022)A feedback control principle common to several biological and engineered systemsJournal of The Royal Society Interface10.1098/rsif.2021.071119:188Online publication date: 2-Mar-2022
https://doi.org/10.1098/rsif.2021.0711
Goles ELeal LMontealegre PRapaport IRíos-Wilson M(2022)Distributed maximal independent set computation driven by finite-state dynamicsInternational Journal of Parallel, Emergent and Distributed Systems10.1080/17445760.2022.215324838:1(85-97)Online publication date: 6-Dec-2022
https://doi.org/10.1080/17445760.2022.2153248
Korman ACrescenzi P(2022)Public communication can facilitate low-risk coordination under surveillanceScientific Reports10.1038/s41598-022-07165-912:1Online publication date: 2-Mar-2022
https://doi.org/10.1038/s41598-022-07165-9
Bastide PGiakkoupis GSaribekyan HMarx D(2021)Self-stabilizing clock synchronization with 1-bit messagesProceedings of the Thirty-Second Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3458064.3458193(2154-2173)Online publication date: 10-Jan-2021
https://dl.acm.org/doi/10.5555/3458064.3458193
Emek YKeren EMiller ACensor-Hillel K(2021)A Thin Self-Stabilizing Asynchronous Unison Algorithm with Applications to Fault Tolerant Biological NetworksProceedings of the 2021 ACM Symposium on Principles of Distributed Computing10.1145/3465084.3467922(93-102)Online publication date: 21-Jul-2021
https://dl.acm.org/doi/10.1145/3465084.3467922
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents