The Bakery Algorithm

Mainframe Computing

Early computers were designed to recieve and process requests sequentially. As a result, no request could even begin its process until the one that preceeded it had been completed, limiting the machine’s computational abilities. This problem was solved through the development of the first mainframe computers. These powerful machines were able to handle numerous requests simulatenously through techniques in parallel processing. When the computer received a request it would be designated to a CPU core, which would then delegate these ordered requests to be processed by other CPU cores. This is the essence behind Leslie Lamport’s Bakery Algorithm¹.

Ethereum is similar to computers prior to the advent of mainframe computing. It was intended to be the world computer, but has struggled to meet the rising demands of its users due to the sequential nature by which it processes incoming requests. When a request is recieved by the Ethereum network, the entire database is locked in place in order to perform the necessary computation. This is because processing the request may rely on a variety of other states stored across the database. If those states were to change during this computation, the result would be indeterminant. As a consequence, Ethereum is limited to processing only a small number of requests at any given time.

Notoros uses an approach rooted in the ideas of mainframe computing. By creating a granular separation of dependencies, Notoros is able to determine which resources are relevant to processing each request, and which are not. This unlocks genuine parallelization and opens the door to a truly planet-scale distributed world computer. This is possible, in part, because Notoros only locks up a resource when it’s being updated, like the logical clock’s in the Bakery Algorithm, allowing numerous read requests to happen simulateously.

Visualizing the Algorithm

Imagine a small bakery that serves premium pastries. Every day, customers come into the store and order their favorite baked goods. At first, this is a simple process because the baker knows all of his customers well and can keep track of their orders in his head. Soon, however, word gets out about the delicious baked goods and suddenly the bakery has a line of customers extending out the door and around the block. Suddenly, the baker is having trouble keeping track of all of the orders, and with customers trying to cut in line, it becomes increasingly difficult to tell who was in line first.

This disorganized bakery reflects a major problem currently plaguing the web3 industry. With malicious re-ordering of events by validators, no one in an asynchronous network can be sure they will get their order on a first-come-first-serve basis, making the bakery less reliable and less attractive for customers.

To solve this problem in distributed computing, in 1974 Leslie Lamport introduced The Bakery Algorithm. In his metaphor, the baker (processor) needs to bake (execute) each request (program) such that each customer (computer in the network) has their request fulfilled in same order it was recieved. To do this, each requester (program) must maintain a incremental counter called a logical clock.

Lamport realized it is better to have the customers keep track of their own order (in their own memory), rather than forcing the baker to memorize the order of all of the customers in line. By introducing a simple “take-a-number” dispenser to the bakery, customers can write their order (to their own memory in the form of a logical clock counter), but can read the order of any other customer in line. By always serving the customer with the lowest order number, the bakery can keep operating seemlessly even when customers get out of line or leave the bakery entirely.

Pseudo-code

begin integer j;
    L1 : choosing [i] : = 1 ;
        number[i] := 1 + maximum (number[l],..., number[N]);
        choosing[i] := 0;
        forj = 1 step l until N do
            begin
                L2: if choosing[j] ~ 0 then goto L2;
                L3: if number[j] ~ 0 and (number [j'], j) < (number[i],
                    i) then goto L3;
            end;
    critical section;
    number[i] := O;
    noncritical section;
    goto L1 ;
end

While seemingly a small change to the business, the new system allows the baker to forget about which order is associated with each customer. This reduces the complexity of his work and allows him to focus on preparing the baked goods rather than keeping track of customers. This also replaces the uncertain ordering of people in line with a clear and descriptive number, which cannot be misread just because someone tried to cut the line.

What makes this innovation even more powerful is the baker’s newfound ability to scale up with additional bakers. By assigning each number in the queue to a baker, the work for multiple customer orders can be done in parallel without compromising the integrity of the first-come-first-serve policy. Now the bakery can serve as many customers as there are bakers without having to slow down the ordering process.

Notoros uses the Bakery Algorithm to parallelize read & write access across the network, enabling maximum scalability & minimal workload for the ledger. Notoros extends this concept enabling each component of each transaction to parallelize access, like if the baker also sequenced each ingredient and when it is used for every recipe while keeping track of customer orders. This powerful concept is one reason why Notoros the most versatile distributed ledger technology ever built.

_{[1] Lamport, Leslie “A New Solution of Dijkstra’s Concurrent Programming Problem.” Communications of the ACM. vol. 17, no. 8, August 1974, pp.453-455}