Past Meetup

João Taveira on Congestion Control

Hosted by Papers we love too

Public group

This Meetup is past

172 people went

Location image of event venue

Details

Mini

Joel VanderWerf (https://twitter.com/JoelVanderWerf) on The Krohn-Rhodes Theorem and Distributed Computing ( http://www.ams.org/journals/tran/1965-116-00/S0002-9947-1965-0188316-1/S0002-9947-1965-0188316-1.pdf )

The Krohn-Rhodes Theorem of 1962 surprised the math world by building arbitrary finite semigroups, and hence arbitrary finite state machines, out of flip-flops (registers with reset operations) and groups (permutations). The construction uses the wreath product, a coordinate system with unidirectional data flow among the factors, like addition with carry. How many group factors are needed? We don't know if this complexity question is decidable, after a half century of work. However, the effort has led to deep insights into regular languages, pseudovarieties (equational specifications of finite algebras), categories, and circuits.

Recent work on distributed systems connects eventual consistency with monotonic operations. A special case of K-R shows that such operations are exactly what you can build from semilattices (commutative, idempotent semigroups, which are weaker than flip-flops) using wreath products.

[1] K. Krohn, J. Rhodes, "Algebraic Theory of Machines. I. Prime Decomposition Theorem for Finite Semigroups and Machines" Transactions of the AMS, April 1965.

[2] http://www-verimag.imag.fr/~maler/Papers/kr-new.pdf

[3] J. Rhodes, "Applications of Automata Theory and Algebra: Via the Mathematical Theory of Complexity to Biology, Physics, Psychology, Philosophy, and Games", World Scientific, 2009.

Joel's Bio

Joel studied with John Rhodes, receiving his PhD in 1994 for generalizing the K-R theory to finite algebras. Now he is applying semigroup theory to replication and convergence in distributed systems.

Main Talk

João Taveira (https://twitter.com/jta) on Congestion Control

João tells us "Resource allocation in computer networks is notoriously hard - it took over twenty years to find something that works, and jury is out as to whether we'll ever find something that works properly.

In a rollercoaster ride of historical revisionism, this talk will cover the evolution of resource allocation as applied to networking, and provide context for the mess we're currently in"

[1] Paul Baran - On Distributed Communications - https://www.rand.org/content/dam/rand/pubs/research_memoranda/2006/RM3420.pdf

[2] V. Cerf and R. Kahn - A protocol for packet network intercommunication - https://www.cs.princeton.edu/courses/archive/fall06/cos561/papers/cerf74.pdf

[3] Van Jacobson - Congestion avoidance and control - http://ee.lbl.gov/papers/congavoid.pdf

[4] Bob Briscoe - Flow Rate Fairness: Dismantling a Religion - http://pbg.cs.illinois.edu/courses/cs598fa09/readings/b07.pdf

João's Bio

João Taveira (https://twitter.com/jta) is a network engineer at Fastly, where he is responsible for making dumb switches do clever things. In addition to writing software for network orchestration, Joao works on protocol design and performance, and holds a PhD from University College London on something to that effect.

Meeting mechanics

Doors open at 6:30 pm; the presentation will begin at 7:00 pm; and, yes, there will be food.

After the paper is presented, we will open up the floor for discussion and questions then we will head over to the bar!

Remember

PWL SF strictly adheres to the Code of Conduct (https://github.com/papers-we-love/papers-we-love/blob/master/CODE_OF_CONDUCT.md) set forth by all PWL charters.