pith. sign in

arxiv: 2001.04235 · v6 · pith:HMNGWS56new · submitted 2020-01-10 · 💻 cs.DC

Notes on Theory of Distributed Systems

James Aspnes This is my paper

Pith reviewed 2026-05-24 15:39 UTC · model grok-4.3

classification 💻 cs.DC
keywords distributed systemslecture notesconsensusleader electionshared memorybroadcastpopulation protocolsself-stabilization
0
0 comments X

The pith

These notes compile the standard curriculum for a theory of distributed systems course.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper assembles lecture notes that systematically present models of distributed computation, communication primitives, coordination protocols, shared-memory objects, and specialized settings such as population protocols. It organizes both constructive algorithms and impossibility results to show what coordination is achievable when processes lack a common clock or reliable shared state. A sympathetic reader would use the notes to trace how basic assumptions about synchrony and failures determine the power of protocols like leader election and consensus. The structure reveals a consistent progression from message-passing to shared-memory models and from deterministic to randomized or approximate solutions.

Core claim

The notes establish that the topics listed in the table of contents—from the basic model through broadcast, leader election, causal ordering, synchronous and Byzantine agreement, Paxos, failure detectors, quorum systems, distributed shared memory, the wait-free hierarchy, atomic snapshots, renaming, obstruction-freedom, topological methods, self-stabilization, and population protocols—form the core body of knowledge for a theory of distributed systems course.

What carries the argument

The central mechanism is the ordered sequence of models and impossibility results that connect message-passing agreement problems to shared-memory object hierarchies and advanced protocols.

If this is right

  • Synchronous agreement protocols succeed when timing assumptions hold, while asynchronous agreement requires failure detectors or randomization.
  • The wait-free hierarchy classifies shared objects by their ability to implement one another without waiting, implying limits on what can be built from weaker primitives.
  • Topological methods yield lower bounds for tasks such as approximate agreement by relating input and output spaces.
  • Permissionless systems extend classical quorum and leader-election ideas to settings without trusted participants.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The notes imply that moving between message-passing and shared-memory models can be done via simulations that preserve key properties.
  • Coverage of population protocols suggests the theory extends naturally to large anonymous collections of simple agents.
  • Inclusion of mobile robots and beeping models indicates the framework applies to geometric and wireless settings.

Load-bearing premise

The selected topics and standard results accurately reflect the core body of knowledge taught in distributed systems theory without significant omissions.

What would settle it

An omission of a standard result such as the FLP impossibility for asynchronous consensus or an error in the exposition of the wait-free hierarchy would show the notes do not fully capture the curriculum.

Figures

Figures reproduced from arXiv: 2001.04235 by James Aspnes.

Figure 2.1
Figure 2.1. Figure 2.1: Asynchronous message-passing execution. Time flows left-to [PITH_FULL_IMAGE:figures/full_fig_p038_2_1.png] view at source ↗
Figure 2.2
Figure 2.2. Figure 2.2: Asynchronous message-passing execution with FIFO channels. [PITH_FULL_IMAGE:figures/full_fig_p038_2_2.png] view at source ↗
Figure 2.3
Figure 2.3. Figure 2.3: Synchronous message-passing execution. All messages are now [PITH_FULL_IMAGE:figures/full_fig_p039_2_3.png] view at source ↗
Figure 2.4
Figure 2.4. Figure 2.4: Asynchronous message-passing execution with times. [PITH_FULL_IMAGE:figures/full_fig_p040_2_4.png] view at source ↗
Figure 5.1
Figure 5.1. Figure 5.1: Labels in the bit-reversal ring with n = 32 For non-comparison-based algorithms we can still prove Ω(n log n) mes￾sages for time-bounded algorithms, but it requires techniques from Ram￾sey theory, the branch of combinatorics that studies when large enough structures inevitably contain substructures with certain properties.5 Here “time-bounded” means that the running time can’t depend on the size of the I… view at source ↗
Figure 10.1
Figure 10.1. Figure 10.1: Three-process vs. six-process execution in Byzantine agreement [PITH_FULL_IMAGE:figures/full_fig_p095_10_1.png] view at source ↗
Figure 10.2
Figure 10.2. Figure 10.2: Four-process vs. eight-process execution in Byzantine agreement [PITH_FULL_IMAGE:figures/full_fig_p096_10_2.png] view at source ↗
Figure 12.1
Figure 12.1. Figure 12.1: Example execution of Paxos. There are three proposers [PITH_FULL_IMAGE:figures/full_fig_p115_12_1.png] view at source ↗
Figure 13.1
Figure 13.1. Figure 13.1: Partial order of failure detector classes. Higher classes can [PITH_FULL_IMAGE:figures/full_fig_p123_13_1.png] view at source ↗
Figure 14.1
Figure 14.1. Figure 14.1: Figure 2 from [ [PITH_FULL_IMAGE:figures/full_fig_p132_14_1.png] view at source ↗
Figure 21.1
Figure 21.1. Figure 21.1: Snapshot from max arrays; see also [AACHE15, [PITH_FULL_IMAGE:figures/full_fig_p220_21_1.png] view at source ↗
Figure 24.1
Figure 24.1. Figure 24.1: A 6 × 6 Moir-Anderson grid (see [PITH_FULL_IMAGE:figures/full_fig_p256_24_1.png] view at source ↗
Figure 24.2
Figure 24.2. Figure 24.2: Path taken by a single process through a [PITH_FULL_IMAGE:figures/full_fig_p257_24_2.png] view at source ↗
Figure 24.3
Figure 24.3. Figure 24.3: A sorting network corresponds to a position in the array. The vertical lines are comparators that compare two values coming in from the left and swap the larger value to the bottom. A network of comparators is a sorting network if the sequences of output values is always sorted no matter what the order of values on the inputs is. The depth of a sorting network is the maximum number of comparators on any… view at source ↗
Figure 28.1
Figure 28.1. Figure 28.1: Subdivision corresponding to one round of immediate snapshot [PITH_FULL_IMAGE:figures/full_fig_p306_28_1.png] view at source ↗
Figure 28.2
Figure 28.2. Figure 28.2: Subdivision corresponding to two rounds of immediate snapshot [PITH_FULL_IMAGE:figures/full_fig_p307_28_2.png] view at source ↗
Figure 28.3
Figure 28.3. Figure 28.3: An attempt at 2-set agreement [PITH_FULL_IMAGE:figures/full_fig_p309_28_3.png] view at source ↗
Figure 28.4
Figure 28.4. Figure 28.4: Output complex for renaming with n = 3, m = 4. Each vertex is labeled by a process id (a, b, c) and a name (1, 2, 3, 4). Observe that the left and right edges of the complex have the same sequence of labels, as do the top and bottom edges; the complex thus folds up into a (twisted) torus. (This is a poor imitation of part of [HS99, [PITH_FULL_IMAGE:figures/full_fig_p316_28_4.png] view at source ↗
read the original abstract

Notes for the Yale course CPSC 465/565 Theory of Distributed Systems. Table of Contents: 1 Introduction, 2 Model, 3 Broadcast and convergecast, 4 Distributed breadth-first search, 5 Leader election, 6 Causal ordering and logical clocks, 7 Synchronizers, 8 Coordinated attack, 9 Synchronous agreement, 10 Byzantine agreement, 11 Impossibility of asynchronous agreement, 12 Paxos, 13 Failure detectors, 14 Quorum systems, 15 Permissionless systems, 16 Model, 17 Distributed shared memory, 18 Mutual exclusion, 19 The wait-free hierarchy, 20 Atomic snapshots, 21 Lower bounds on perturbable objects, 22 Restricted-use objects, 23 Common2, 24 Randomized consensus and test-and-set, 25 Renaming, 26 Software transactional memory, 27 Obstruction-freedom, 28 BG simulation, 29 Topological methods, 30 Approximate agreement, 31 Overview, 32 Self-stabilization, 33 Distributed graph algorithms, 34 Mobile Robots, 35 Beeping, 36 Population protocols

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 3 minor

Summary. The manuscript consists of lecture notes for the Yale graduate course CPSC 465/565 on Theory of Distributed Systems. It provides an expository overview of standard topics via a table of contents covering models of distributed computation, broadcast and convergecast, leader election, causal ordering, synchronizers, agreement protocols (synchronous, Byzantine, asynchronous impossibility, Paxos), failure detectors, quorum systems, permissionless systems, distributed shared memory, mutual exclusion, the wait-free hierarchy, atomic snapshots, lower bounds, renaming, transactional memory, obstruction-freedom, BG simulation, topological methods, approximate agreement, self-stabilization, graph algorithms, mobile robots, beeping, and population protocols.

Significance. If the exposition accurately reflects established results from the literature, the notes serve as a consolidated educational resource compiling the canonical curriculum in distributed systems theory. The breadth across both message-passing and shared-memory models, as well as the progression from basic primitives to advanced techniques such as topological methods and population protocols, adds value for teaching and reference. No novel theorems, derivations, or empirical claims are advanced, so significance rests on faithful presentation of known material rather than original contributions.

minor comments (3)
  1. [Table of Contents] Table of Contents: the 36 sections are listed without page numbers or cross-references; adding these would improve navigability for readers using the notes as a course companion.
  2. [12] Section 12 (Paxos): as with other protocol sections, ensure that any pseudocode or invariants are accompanied by explicit citations to the original literature (e.g., Lamport 1998) to allow students to trace primary sources.
  3. [16] Sections 16–29 (shared-memory portion): the transition from message-passing models (Sections 1–15) to shared-memory models would benefit from a short bridging paragraph explaining the change in assumptions and why the wait-free hierarchy is introduced at that point.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their review of our lecture notes on the Theory of Distributed Systems. The referee's summary correctly describes the manuscript as expository notes covering standard topics from the Yale course CPSC 465/565, with no novel claims. We appreciate the recognition of its potential value as a consolidated educational resource and the recommendation for minor revision.

Circularity Check

0 steps flagged

No circularity: purely expository lecture notes on established results

full rationale

The document is a set of lecture notes for a standard graduate course (CPSC 465/565). Its table of contents and content consist of standard models, algorithms, and impossibility results from the distributed systems literature (broadcast, leader election, agreement protocols, shared memory, etc.). No novel derivations, predictions, fitted parameters, or load-bearing self-citations appear; every topic is presented as established curriculum material without internal reduction to the notes' own inputs. This matches the default expectation of no circularity for expository work.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

No free parameters, axioms, or invented entities are introduced because the document is a compilation of existing knowledge rather than an original theoretical contribution.

pith-pipeline@v0.9.0 · 5719 in / 991 out tokens · 21512 ms · 2026-05-24T15:39:25.035773+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

228 extracted references · 228 canonical work pages · 3 internal anchors

  1. [1]

    Sub-logarithmic test-and-set against a weak adversary

    Dan Alistarh and James Aspnes. Sub-logarithmic test-and-set against a weak adversary. In Distributed Computing: 25th International Symposium, DISC 2011 , volume 6950 of Lecture Notes in Computer Science , pages 97--109. Springer-Verlag, September 2011

    work page 2011

  2. [2]

    A biological solution to a fundamental distributed computing problem

    Yehuda Afek, Noga Alon, Omer Barad, Eran Hornstein, Naama Barkai, and Ziv Bar-Joseph. A biological solution to a fundamental distributed computing problem. science , 331(6014):183--185, 2011

    work page 2011

  3. [3]

    Beeping a maximal independent set

    Yehuda Afek, Noga Alon, Ziv Bar-Joseph, Alejandro Cornejo, Bernhard Haeupler, and Fabian Kuhn. Beeping a maximal independent set. In Proceedings of the 25th International Conference on Distributed Computing , DISC'11, pages 32--50, Berlin, Heidelberg, 2011. Springer-Verlag

    work page 2011

  4. [4]

    Optimal-time adaptive tight renaming, with applications to counting

    Dan Alistarh, James Aspnes, Keren Censor-Hillel, Seth Gilbert, and Morteza Zadimoghaddam. Optimal-time adaptive tight renaming, with applications to counting. In Proceedings of the Thirtieth Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing , pages 239--248, June 2011

    work page 2011

  5. [5]

    Polylogarithmic concurrent data structures from monotone circuits

    James Aspnes, Hagit Attiya, and Keren Censor-Hillel. Polylogarithmic concurrent data structures from monotone circuits. Journal of the ACM , 59(1):2:1--2:24, February 2012

    work page 2012

  6. [6]

    Limited-use snapshots with polylogarithmic step complexity

    James Aspnes, Hagit Attiya, Keren Censor-Hillel, and Faith Ellen. Limited-use snapshots with polylogarithmic step complexity. Journal of the ACM , 62(1):3, February 2015

    work page 2015

  7. [7]

    Erratum: Limited-use atomic snapshots with polylogarithmic step complexity

    James Aspnes, Hagit Attiya, Keren Censor-Hillel, and Faith Ellen. Erratum: Limited-use atomic snapshots with polylogarithmic step complexity. J. ACM , 65(6):38:1--38:2, November 2018

    work page 2018

  8. [8]

    Brief announcement: Object oriented consensus

    Yehuda Afek, James Aspnes, Edo Cohen, and Danny Vainstein. Brief announcement: Object oriented consensus. In Elad Michael Schiller and Alexander A. Schwarzmann, editors, Proceedings of the ACM Symposium on Principles of Distributed Computing, PODC 2017, Washington, DC, USA, July 25-27, 2017 , pages 367--369. ACM , 2017

    work page 2017

  9. [9]

    Atomic snapshots of shared memory

    Yehuda Afek, Hagit Attiya, Danny Dolev, Eli Gafni, Michael Merritt, and Nir Shavit. Atomic snapshots of shared memory. J. ACM , 40(4):873--890, 1993

    work page 1993

  10. [10]

    Fischer, and Ren\'e Peralta

    Dana Angluin, James Aspnes, Zo \"e Diamadi, Michael J. Fischer, and Ren\'e Peralta. Computation in networks of passively mobile finite-state sensors. Distributed Computing , pages 235--253, March 2006

    work page 2006

  11. [11]

    Stably computable predicates are semilinear

    Dana Angluin, James Aspnes, and David Eisenstat. Stably computable predicates are semilinear. In PODC '06: Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing , pages 292--299, New York, NY, USA, 2006. ACM Press

    work page 2006

  12. [12]

    Fast computation by population protocols with a leader

    Dana Angluin, James Aspnes, and David Eisenstat. Fast computation by population protocols with a leader. Distributed Computing , 21(3):183--199, September 2008

    work page 2008

  13. [13]

    A simple population protocol for fast robust approximate majority

    Dana Angluin, James Aspnes, and David Eisenstat. A simple population protocol for fast robust approximate majority. Distributed Computing , 21(2):87--102, July 2008

    work page 2008

  14. [14]

    Fast randomized test-and-set and renaming

    Dan Alistarh, Hagit Attiya, Seth Gilbert, Andrei Giurgiu, and Rachid Guerraoui. Fast randomized test-and-set and renaming. In Nancy A. Lynch and Alexander A. Shvartsman, editors, Distributed Computing, 24th International Symposium, DISC 2010, Cambridge, MA, USA, September 13-15, 2010. Proceedings , volume 6343 of Lecture Notes in Computer Science , pages ...

    work page 2010

  15. [15]

    The complexity of renaming

    Dan Alistarh, James Aspnes, Seth Gilbert, and Rachid Guerraoui. The complexity of renaming. In Fifty-Second Annual IEEE Symposium on Foundations of Computer Science , pages 718--727, October 2011

    work page 2011

  16. [16]

    Randomized loose renmaing in O( n) time

    Dan Alistarh, James Aspnes, George Giakkoupis, and Philipp Woelfel. Randomized loose renmaing in O( n) time. In 2013 ACM Symposium on Principles of Distributed Computing , pages 200--209, July 2013

    work page 2013

  17. [17]

    Renaming in an asynchronous environment

    Hagit Attiya, Amotz Bar-Noy, Danny Dolev, David Peleg, and Rüdiger Reischuk. Renaming in an asynchronous environment. J. ACM , 37(3):524--548, 1990

    work page 1990

  18. [18]

    Sharing memory robustly in message-passing systems

    Hagit Attiya, Amotz Bar-Noy, and Danny Dolev. Sharing memory robustly in message-passing systems. Journal of the ACM , 42(1):124--142, 1995

    work page 1995

  19. [19]

    On achieving consensus using a shared memory

    Karl Abrahamson. On achieving consensus using a shared memory. In Proceedings of the 7th Annual ACM Symposium on Principles of Distributed Computing (PODC) , pages 291--302, 1988

    work page 1988

  20. [20]

    Tight bounds for asynchronous randomized consensus

    Hagit Attiya and Keren Censor. Tight bounds for asynchronous randomized consensus. Journal of the ACM , 55(5):20, October 2008

    work page 2008

  21. [21]

    Approximate shared-memory counting despite a strong adversary

    James Aspnes and Keren Censor. Approximate shared-memory counting despite a strong adversary. In SODA '09: Proceedings of the Nineteenth Annual ACM -SIAM Symposium on Discrete Algorithms , pages 441--450, Philadelphia, PA, USA, 2009. Society for Industrial and Applied Mathematics

    work page 2009

  22. [22]

    Lower bounds for restricted-use objects

    James Aspnes, Keren Censor - Hillel, Hagit Attiya, and Danny Hendler. Lower bounds for restricted-use objects. SIAM J. Comput. , 45(3):734--762, 2016

    work page 2016

  23. [23]

    Lower bounds for randomized consensus under a weak adversary

    Hagit Attiya and Keren Censor-Hillel. Lower bounds for randomized consensus under a weak adversary. SIAM J. Comput. , 39(8):3885--3904, 2010

    work page 2010

  24. [24]

    Atomic snapshots in O (log^3 n) steps using randomized helping

    James Aspnes and Keren Censor-Hillel. Atomic snapshots in O (log^3 n) steps using randomized helping. In Yehuda Afek, editor, Distributed Computing: 27th International Symposium, DISC 2013, Jerusalem, Israel, October 14--18, 2013. Proceedings , volume 8205 of Lecture Notes in Computer Science , pages 254--268. Springer Berlin Heidelberg, 2013

    work page 2013

  25. [25]

    Atomic snapshots in expected O (log^3 n) steps using randomized helping

    James Aspnes and Keren Censor-Hillel. Atomic snapshots in expected O (log^3 n) steps using randomized helping. Submitted to Distributed Computing. Available from http://www.cs.yale.edu/homes/aspnes/papers/randomized-snapshot-abstract.html., 2018

    work page 2018

  26. [26]

    Are Lock-Free Concurrent Algorithms Practically Wait-Free?

    Dan Alistarh, Keren Censor-Hillel, and Nir Shavit. Are lock-free concurrent algorithms practically wait-free? arXiv preprint arXiv:1311.3200 , 2013

    work page internal anchor Pith review Pith/arXiv arXiv 2013

  27. [27]

    Tight bounds for anonymous adopt-commit objects

    James Aspnes and Faith Ellen. Tight bounds for anonymous adopt-commit objects. In 23rd Annual ACM Symposium on Parallelism in Algorithms and Architectures , pages 317--324, June 2011

    work page 2011

  28. [28]

    Deterministic objects: Life beyond consensus

    Yehuda Afek, Faith Ellen, and Eli Gafni. Deterministic objects: Life beyond consensus. In Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing , PODC '16, pages 97--106, New York, NY, USA, 2016. ACM

    work page 2016

  29. [29]

    E. A. Akkoyunlu, K. Ekanadham, and R. V. Huber. Some constraints and tradeoffs in the design of network communications. SIGOPS Oper. Syst. Rev. , 9:67--74, November 1975

    work page 1975

  30. [30]

    Adaptive and efficient algorithms for lattice agreement and renaming

    Hagit Attiya and Arie Fouren. Adaptive and efficient algorithms for lattice agreement and renaming. SIAM Journal on Computing , 31(2):642--664, 2001

    work page 2001

  31. [31]

    Fischer, and Nancy A

    Eshrat Arjomandi, Michael J. Fischer, and Nancy A. Lynch. Efficiency of synchronous versus asynchronous distributed systems. J. ACM , 30(3):449--456, 1983

    work page 1983

  32. [32]

    Time and message bounds for election in synchronous and asynchronous complete networks

    Yehuda Afek and Eli Gafni. Time and message bounds for election in synchronous and asynchronous complete networks. SIAM Journal on Computing , 20(2):376--394, 1991

    work page 1991

  33. [33]

    Adve and Kourosh Gharachorloo

    Sarita V. Adve and Kourosh Gharachorloo. Shared memory consistency models: A tutorial. Technical Report 95/7, DEC Western Research Laboratory, 1995

    work page 1995

  34. [34]

    Recent algorithmic advances in population protocols

    Dan Alistarh and Rati Gelashvili. Recent algorithmic advances in population protocols. SIGACT News , 49(3):63--73, October 2018

    work page 2018

  35. [35]

    Of choices, failures and asynchrony: The many faces of set agreement

    Dan Alistarh, Seth Gilbert, Rachid Guerraoui, and Corentin Travers. Of choices, failures and asynchrony: The many faces of set agreement. In Yingfei Dong, Ding-Zhu Du, and Oscar H. Ibarra, editors, ISAAC , volume 5878 of Lecture Notes in Computer Science , pages 943--953. Springer, 2009

    work page 2009

  36. [36]

    Synchronizing without locks is inherently expensive

    Hagit Attiya, Rachid Guerraoui, Danny Hendler, and Petr Kouznetsov. Synchronizing without locks is inherently expensive. In PODC '06: Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing , pages 300--307, New York, NY, USA, 2006. ACM

    work page 2006

  37. [37]

    Yehuda Afek, Eli Gafni, John Tromp, and Paul M. B. Vit á nyi. Wait-free test-and-set (extended abstract). In Adrian Segall and Shmuel Zaks, editors, Distributed Algorithms, 6th International Workshop, WDAG '92, Haifa, Israel, November 2-4, 1992, Proceedings , volume 647 of Lecture Notes in Computer Science , pages 85--94. Springer, 1992

    work page 1992

  38. [38]

    Fast randomized consensus using shared memory

    James Aspnes and Maurice Herlihy. Fast randomized consensus using shared memory. Journal of Algorithms , 11(3):441--461, September 1990

    work page 1990

  39. [39]

    Wait-free data structures in the asynchronous PRAM model

    James Aspnes and Maurice Herlihy. Wait-free data structures in the asynchronous PRAM model. In Second Annual ACM Symposium on Parallel Algorithms and Architectures , pages 340--349, July 1990

    work page 1990

  40. [40]

    Inherent limitations on disjoint-access parallel implementations of transactional memory

    Hagit Attiya, Eshcar Hillel, and Alessia Milani. Inherent limitations on disjoint-access parallel implementations of transactional memory. In Friedhelm Meyer auf der Heide and Michael A. Bender, editors, SPAA 2009: Proceedings of the 21st Annual ACM Symposium on Parallelism in Algorithms and Architectures, Calgary, Alberta, Canada, August 11-13, 2009 , pa...

    work page 2009

  41. [41]

    Atomic snapshots using lattice agreement

    Hagit Attiya, Maurice Herlihy, and Ophir Rachman. Atomic snapshots using lattice agreement. Distributed Computing , 8(3):121--132, 1995

    work page 1995

  42. [42]

    Counting networks

    James Aspnes, Maurice Herlihy, and Nir Shavit. Counting networks. Journal of the ACM , 41(5):1020--1048, September 1994

    work page 1994

  43. [43]

    Allocate-on-use space complexity of shared-memory algorithms

    James Aspnes, Bernhard Haeupler, Alexander Tong, and Philipp Woelfel. Allocate-on-use space complexity of shared-memory algorithms. In Ulrich Schmid and Josef Widder, editors, 32nd International Symposium on Distributed Computing, DISC 2018, New Orleans, LA, USA, October 15--19, 2018 , volume 121 of LIPIcs , pages 8:1--8:17. Schloss Dagstuhl - Leibniz-Zen...

    work page 2018

  44. [44]

    Tight RMR lower bounds for mutual exclusion and other problems

    Hagit Attiya, Danny Hendler, and Philipp Woelfel. Tight RMR lower bounds for mutual exclusion and other problems. In Proceedings of the 40th annual ACM symposium on Theory of computing , STOC '08, pages 217--226, New York, NY, USA, 2008. ACM

    work page 2008

  45. [45]

    Time optimal self-stabilizing synchronization

    Baruch Awerbuch, Shay Kutten, Yishay Mansour, Boaz Patt-Shamir, and George Varghese. Time optimal self-stabilizing synchronization. In Proceedings of the twenty-fifth annual ACM symposium on Theory of computing , pages 652--661. ACM, 1993

    work page 1993

  46. [46]

    A time-optional self-stabilizing synchronizer using a phase clock

    Baruch Awerbuch, Shay Kutten, Yishay Mansour, Boaz Patt-Shamir, and George Varghese. A time-optional self-stabilizing synchronizer using a phase clock. IEEE Transactions on Dependable and Secure Computing , 4(3):180--190, July--September 2007

    work page 2007

  47. [47]

    Greg Plaxton, Mirjam Wattenhofer, and Roger Wattenhofer

    Hagit Attiya, Fabian Kuhn, C. Greg Plaxton, Mirjam Wattenhofer, and Roger Wattenhofer. Efficient adaptive collect using randomization. Distributed Computing , 18(3):179--188, 2006

    work page 2006

  48. [48]

    Ajtai, J

    M. Ajtai, J. Komlós, and E. Szemerédi. An o(n n) sorting network. In Proceedings of the fifteenth annual ACM symposium on Theory of computing , pages 1--9, New York, NY, USA, 1983. ACM

    work page 1983

  49. [49]

    Anderson and Mark Moir

    James H. Anderson and Mark Moir. Towards a necessary and sufficient condition for wait-free synchronization (extended abstract). In André Schiper, editor, Distributed Algorithms, 7th International Workshop, WDAG '93, Lausanne, Switzerland, September 27-29, 1993, Proceedings , volume 725 of Lecture Notes in Computer Science , pages 39--53. Springer, 1993

    work page 1993

  50. [50]

    Efficiency of semisynchronous versus asynchronous networks

    Hagit Attiya and Marios Mavronicolas. Efficiency of semisynchronous versus asynchronous networks. Mathematical Systems Theory , 27(6):547--571, November 1994

    work page 1994

  51. [51]

    Fast, wait-free (2k-1) -renaming

    Yehuda Afek and Michael Merritt. Fast, wait-free (2k-1) -renaming. In PODC , pages 105--112, 1999

    work page 1999

  52. [52]

    From bounded to unbounded concurrency objects and back

    Yehuda Afek, Adam Morrison, and Guy Wertheim. From bounded to unbounded concurrency objects and back. In Proceedings of the 30th Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing , pages 119--128. ACM, 2011

    work page 2011

  53. [53]

    Anderson

    Thomas E. Anderson. The performance of spin lock alternatives for shared-money multiprocessors. IEEE Trans. Parallel Distrib. Syst. , 1(1):6--16, 1990

    work page 1990

  54. [54]

    Anderson

    James H. Anderson. Multi-writer composite registers. Distributed Computing , 7(4):175--195, 1994

    work page 1994

  55. [55]

    Local and global properties in networks of processors (extended abstract)

    Dana Angluin. Local and global properties in networks of processors (extended abstract). In Proceedings of the twelfth annual ACM symposium on Theory of computing , STOC '80, pages 82--93, New York, NY, USA, 1980. ACM

    work page 1980

  56. [56]

    Fault-tolerant gathering algorithms for autnonomous mobile robots

    Noa Agmon and David Peleg. Fault-tolerant gathering algorithms for autnonomous mobile robots. SIAM Journal on Computing , 36(1):56--82, 2006

    work page 2006

  57. [57]

    An introduction to population protocols

    James Aspnes and Eric Ruppert. An introduction to population protocols. In Beno\^it Garbinato, Hugo Miranda, and Lu\'is Rodrigues, editors, Middleware for Network Eccentric and Mobile Applications , pages 97--120. Springer-Verlag, 2009

    work page 2009

  58. [58]

    Lower bounds for distributed coin-flipping and randomized consensus

    James Aspnes. Lower bounds for distributed coin-flipping and randomized consensus. Journal of the ACM , 45(3):415--450, May 1998

    work page 1998

  59. [59]

    Slightly smaller splitter networks

    James Aspnes. Slightly smaller splitter networks. Technical Report YALEU/DCS/TR-1438, Yale University Department of Computer Science, November 2010

    work page 2010

  60. [60]

    Notes on randomized algorithms

    James Aspnes. Notes on randomized algorithms. http://www.cs.yale.edu/homes/aspnes/classes/469/notes.pdf, July 2011

    work page 2011

  61. [61]

    Faster randomized consensus with an oblivious adversary

    James Aspnes. Faster randomized consensus with an oblivious adversary. In 2012 ACM Symposium on Principles of Distributed Computing , pages 1--8, July 2012

    work page 2012

  62. [62]

    A modular approach to shared-memory consensus, with applications to the probabilistic-write model

    James Aspnes. A modular approach to shared-memory consensus, with applications to the probabilistic-write model. Distributed Computing , 25(2):179--188, May 2012

    work page 2012

  63. [63]

    Hagit Attiya, Marc Snir, and Manfred K. Warmuth. Computing on an anonymous ring. J. ACM , 35:845--875, October 1988

    work page 1988

  64. [64]

    Lower bounds and impossibility results for transactional memory computing

    Hagit Attiya. Lower bounds and impossibility results for transactional memory computing. Bulletin of the European Association for Computer Science , 112:38--52, February 2014

    work page 2014

  65. [65]

    Efficient asynchronous consensus with the weak adversary scheduler

    Yonatan Aumann. Efficient asynchronous consensus with the weak adversary scheduler. In PODC '97: Proceedings of the Sixteenth Annual ACM Symposium on Principles of Distributed Computing , pages 209--218, New York, NY, USA, 1997. ACM

    work page 1997

  66. [66]

    The instancy of snapshots and commuting objects

    Yehuda Afek and Eytan Weisberger. The instancy of snapshots and commuting objects. J. Algorithms , 30(1):68--105, 1999

    work page 1999

  67. [67]

    Distributed Computing: Fundamentals, Simulations, and Advanced Topics

    Hagit Attiya and Jennifer Welch. Distributed Computing: Fundamentals, Simulations, and Advanced Topics . Wiley, second edition, 2004. On-line version: http://dx.doi.org/10.1002/0471478210. (This may not work outside Yale.)

    work page doi:10.1002/0471478210 2004

  68. [68]

    Complexity of network synchronization

    Baruch Awerbuch. Complexity of network synchronization. J. ACM , 32:804--823, October 1985

    work page 1985

  69. [69]

    A completeness theorem for a class of synchronization objects (extended abstract)

    Yehuda Afek, Eytan Weisberger, and Hanan Weisman. A completeness theorem for a class of synchronization objects (extended abstract). In Proceedings of the Twelfth Annual ACM Symposium on Principles of Distributed Computing , pages 159--170, 1993

    work page 1993

  70. [70]

    K. E. Batcher. Sorting networks and their applications. In Proceedings of the AFIPS Spring Joint Computer Conference 32 , pages 307--314, 1968

    work page 1968

  71. [71]

    Berenbrink, A

    P. Berenbrink, A. Brinkmann, R. Elsässer, T. Friedetzky, and L. Nagel. Randomized renaming in shared memory systems. In Parallel and Distributed Processing Symposium (IPDPS), 2015 IEEE International , pages 542--549, May 2015

    work page 2015

  72. [72]

    Datta, Lawrence L

    Christian Boulinier, Ajoy K. Datta, Lawrence L. Larmore, and Franck Petit. Space efficient and time optimal distributed BFS tree construction. Information Processing Letters , 108(5):273--278, November 2008. http://dx.doi.org/10.1016/j.ipl.2008.05.016

    work page doi:10.1016/j.ipl.2008.05.016 2008

  73. [73]

    Wait-Free Gathering of Mobile Robots

    Zohir Bouzid, Shantanu Das, and S \' e bastien Tixeuil. Wait-free gathering of mobile robots. CoRR , abs/1207.0226, 2012

    work page internal anchor Pith review Pith/arXiv arXiv 2012

  74. [74]

    On a routing problem

    RE Bellman. On a routing problem. Quarterly of Applied Mathematics , 16:87--90, 1958

    work page 1958

  75. [75]

    Bellovin

    S. Bellovin. The Security Flag in the IPv4 Header . RFC 3514 (Informational), April 2003

    work page 2003

  76. [76]

    Fully-adaptive algorithms for long-lived renaming

    Alex Brodsky, Faith Ellen, and Philipp Woelfel. Fully-adaptive algorithms for long-lived renaming. Distributed Computing , 24(2):119--134, 2011

    work page 2011

  77. [77]

    Generalized flp impossibility result for t -resilient asynchronous computations

    Elizabeth Borowsky and Eli Gafni. Generalized flp impossibility result for t -resilient asynchronous computations. In STOC , pages 91--100, 1993

    work page 1993

  78. [78]

    A simple algorithmically reasoned characterization of wait-free computations (extended abstract)

    Elizabeth Borowsky and Eli Gafni. A simple algorithmically reasoned characterization of wait-free computations (extended abstract). In PODC , pages 189--198, 1997

    work page 1997

  79. [79]

    Consensus power makes (some) sense! (extended abstract)

    Elizabeth Borowsky, Eli Gafni, and Yehuda Afek. Consensus power makes (some) sense! (extended abstract). In PODC , pages 363--372, 1994

    work page 1994

  80. [80]

    Borowsky, E

    E. Borowsky, E. Gafni, N. Lynch, and S. Rajsbaum. The bg distributed simulation algorithm. Distrib. Comput. , 14(3):127--146, October 2001

    work page 2001

Showing first 80 references.