Nonsequential and Distributed Programming with Go

Dr. Christian Maurer

Nonsequential and Distributed Programming mit Go
Synchronization of Concurrent Processes:
Communication – Cooperation – Competition

The book contains implementations of many important algorithms

Locks

Algorithm of Dekker for the protection of the mutual exclusion for 2 processes
Dijkstra, E. W.: Hierarchical Ordering of Sequential Processes.
Acta Informatica 1 (1971) 115-138
» www.cs.utexas.edu/users/EWD/ewd03xx/EWD310.PDF
Algorithm of Dijkstra for the protection of the mutual exclusion for several processes
Dijkstra, E. W.: Cooperating Sequential Processes.
» Technical Report EWD-123, Technological University Eindhoven (1965)
Tiebreaker-algorithm of Peterson
Peterson, G. L.: Myths about the Mutual Exclusion Problem. Inf. Proc. Letters 2 (1981) 115-116 » doi
Algorithm of Kessels
Kessels, J. L. W.: Arbitration Without Common Modifiable Variables.
Acta Informatica 17 (1982) 135-141 » doi
Algorithm of Doran and Thomas
Doran, R. W., Thomas, L. K.: Variants of the software solution to mutual exclusion.
Inf. Proc. Letters 10 (1980) 206-208 » doi
Algorithm of Knuth
Knuth, D. E.: Additional Comments on a Problem in Concurrent Programming Control.
Commun. ACM 9 (1966) 321-322 » doi
Algorithm of Habermann
in: Herrtwich, R. G., Hommel, G.: Nebenläufige Programme (Kooperation und Konkurrenz). Springer-Verlag Berlin Heidelberg New York (1994, 1989) » doi
Bakery-algorithm of Lamport
Lamport, L.: A new Solution of Dijkstra's Concurrent Programming Problem.
Commun. ACM 17 (1974) 453-455 » doi
» research.microsoft.com/en-us/um/people/lamport/pubs/bakery.pdf
and
Lamport, L.: A new Approach to Proving the Correctness of Multiprocess Programs. ACM Trans. Program. Lang. Syst. 1 (1979) 84-97 » doi
» research.microsoft.com/en-us/um/people/lam\-port/pubs/new-approach.pdf
Algorithm of Morris
Morris, J. M.: A starvation: free solution to the mutual exclusion problem. Inf. Proc. Lletters 8 (1979) 76-80 » doi
Algorithm of Szymanski
Szymanski, B. K.: A Simple Solution to Lamport's Concurrent Programming Problem with Linear Wait.
in: Lenfant, J. (ed.): ICS '88, New York. ACM (1988) 621-626 » doi

Semaphores

Algorithm of Udding for the construction of fair binary semaphores
Udding, J. T.: Absence of Individual Starvation using Weak Semaphores.
Inf. Proc. Letters 23 (1986), 159-162 » doi
The sleeping barber of Dijkstra
Dijkstra, E. W.: Cooperating Sequential Processes.
» Technical Report EWD-123, Technological University Eindhoven (1965)
Algorithm of Barz for the construction of general semaphores
Barz, H. W.: Implementing Semaphores by Binary Semaphores.
ACM Sigplan Notices 18 (1983) 39-x-45 » doi
Algorithm of Courtois, Heymans und Parnas for the solution of the 2nd readers-writers problem
Courtois, P. J., Heymans, F., Parnas, D. L.: Concurrent Control with ``Readers'' and ``Writers''.
Commun. ACM 14 (1971) 667-668 » doi
Algorithm of Parnas for the solution of problem of the cigarette-smokers
Parnas, D. L.: On a Solution to the Cigarette Smoker's Problem without conditional statements.
Commun. ACM 18 (1975) 181-183 » doi

Deadlocks

The bankers algorithm of Dijkstra
Dijkstra, E. W.: Een algorithme ter voorkoming van de dodelijke omarming.
» Technical Report EWD-108, Technological University Eindhoven (1964)

Monitors

The alarm-clock of Hoare
Hoare, C. A. R.: Monitors: An Operating Systems Structuring Concept.
Commun. ACM 17 (1974) 549--557 » doi
The baton-algorithm of Andrews
in: Andrews, G. R.: Foundations of Multithreaded, Parallel and Distributed Programming, S. 171 ff.
Addison-Wesley Reading (2000)

Traversing algorithms

Algorithm of Awerbuch
Awerbuch, B.: A New Distributed Depth-First-Search Algorithm. Inf. Proc. Letters 20 (1985) 147-150 » doi
Algorithm of Hélary und Raynal
Hélary, J.-M., Raynal, M.: Depth-first traversal and virtual ring construction in distributed Systems.
Research Rreport RR-0704, INRIA, 1987 » hal.inria.fr/inria-00075848

Election algorithms

Algorithm of Chang and Roberts
Chang, E., Roberts, R.: An Improved Algorithm for Decentralized Extrema-Finding in Circular Configurations of Processes.
Commun. ACM 22 (1979) 281-283 » doi
Algorithm of Hirschberg and Sinclair
Hirschberg, D. S., Sinclair, J. B.: Decentralized Extrema Finding in Circular Configurations of Processes.
Commun. ACM 23 (1980) 627-628 » doi
Algorithm of Peterson
Peterson, G. L.: An n/log n Unidirectional Algorithm for the Circular Extrema Finding Problem.
ACM Trans. Program. Lang. Syst. 4 (1982) 758-762 » doi