Booking a taxi ride on distributed ledgers: A smart contract example (Part II)
In the previous post, we presented the different actors and the parties involved and discussed discuss how the state is modelled in this taxi-booking scenario. Next, let’s see different steps in the booking flow and the deployment on Canton.
Booking a ride with a smart contract app
The life of a booking starts with a TravelerAccount created for Alice by the operator. On this contract, Alice can exercise the choice RequestRide that creates a RideRequest. The RideRequest is then handled by the operator, who can either reject it (in case there is no vehicle available to serve the ride request) or create a RideProposal, which contains a proposed pickup time, a dropoff time, and a fare.
Alice then can either accept or reject the ride proposal. If she chooses to accept, an instance of a RideProposalAccepted is created. Finally, the operator triggers the creation of the Ride, Pickup, and Dropoff contracts, and the plan of a vehicle is updated.
The flow can be visualized in the following diagram while the different templates and choices that can be exercised on them are shown in the table below.
At this point, you may wonder why we need the RideProposalAccepted contract and why we cannot directly trigger the final step (ride creation and fleet update) directly on the RideProposal. The reason is that Alice, our traveler, is a controller on the RideProposal instance but is not an observer of the fleet, which means that she is not authorized to see the Fleet and Vehicle contracts and exercise choices on them. By adding one more step in our propose-accept pattern, we make sure that the whole flow is properly authorized.
From a ride request to a ride proposal
We now discuss in more detail the ride request and its processing by the operator. Implementations of the ride requests and proposals as data structures are rather straightforward:
The biggest part is the processing of the request by the operator. The different steps that we need to perform are the following:
Gather the list of all vehicles and their properties
Find the list of vehicles that could serve the ride (in our simplified setting, we only need to check that the vehicle can reach the pickup location in time)
If the list is empty, reject the ride; otherwise, select the vehicle which is the closest to the new pickup and create a ride proposal
These high-level steps yield the following choice on the RideRequest template.
On delays, concurrency, and transactions
Several assumptions and simplifications are made in our simple implementation. The first is that every party will exercise his/her choices quickly. If that is not the case, e.g., if Alice waits a few minutes before accepting the ride proposal, then the offer made by the operator may not be feasible anymore. In particular, the pickup and the dropoff time need to be recomputed.
Moreover, concurrency issues can arise when multiple travelers try to book rides in parallel. To see why, consider the following situation:
Alice emits a ride request and gets a proposal
Bob emits a ride request and gets a proposal assigned to the same vehicle as Alice
Alice accepts her proposal
Now, when Bob accepts his ride proposal, the vehicle that is assigned is already heading towards Alice, which means that the offer is no longer valid (or not without significantly increasing the delay before Bob’s pickup). Again, this can be solved by adding additional checks in the final transaction of the flow (choice CreateRideAndAddToFleet of the RideProposal_Accepted template).
Finally, note that characteristics of Daml can alleviate some inherent issues of such a system:
By wrapping most of the side effects in the final transaction, one can ensure that creation of the ride, update of the state of the fleet, and payment for the ride happen atomically
Using contract ids, it is straightforward to check that the current state of the vehicle corresponds to the state of the vehicle when the ride proposal was made, thus decreasing the risk of concurrent updates
In the creation of the ride proposal, we chose a naïve and sub-optimal algorithm. For the purpose of simplicity, we decided to select the vehicle that is the closest to the pickup location, in case there are multiple candidate vehicles. Another possibility would be to choose the vehicle that can drive Alice from her pickup location to her destination as quickly as possible, or a combination of these two criteria.
In general, if you allow ridesharing (i.e., multiple travelers sharing the vehicle during a portion of their journeys), pre-booking (booking in advance), or specifying the desired arrival time instead of the desired departure time, then the selection of the best possibility to serve the ride is a non-trivial task (indeed, the problem is a generalization of the traveling salesman problem). Additionally, taking routing constraints and traffic into account, as well as tracking the vehicle precisely and in real time, is operationally difficult. We neglect all these issues and focus instead on high-level modeling.
Note that this choice is not a restriction: these more complex algorithms could be designed and implemented in parallel. Moreover, one could also perform some of the computations off-ledger in order to protect the IP of the algorithms. In that case, the ledger would only capture the result of such computations.
The missing pieces for a local simulation
In order to be able to run a complete workflow locally, two important pieces are missing:
Routing, to compute drive distance and time between locations (vehicle current locations, pickups, drop offs) and simulate vehicle movement
Matching, to decide whether a ride can be accepted and which vehicle should serve it
In order to perform real routing computation, one usually relies on an external provider (e.g., Google Maps, local instance of OSRM server, etc.). For the sake of simplicity (and since routing is orthogonal to the problem we’re solving), we can model vehicle location as tuples (x, y) that represent points in the Euclidean space. We then assume that vehicles drive between such points in straight lines at constant speed.
Given a vehicle plan (pickups and dropoffs to visit), its last known location and the current time (in our case, the ledger time) it is then possible to infer:
The activities that are already done and that should be dropped from the plan
The current location of the vehicle (using interpolation between points when necessary)
Similarly, we can implement a simplistic matching algorithm that only considers appending a new ride at the end of a plan. The best candidate is then the vehicle whose last dropoff (or current location, in case of an empty) is the closest to the new pickup.
Now that we have seen the different flows and building blocks for our application, we discuss the network topology that could be used to deploy our app. The ingredient that enables this deployment is Canton, a synchronization protocol that allows for the connection and synchronization of different ledger instances while maintaining privacy and integrity. This allows us to see the inter-connected ledgers as a virtual global ledger (see overview and key concepts).
The topology of Canton is flexible and is independent of the different parties mentioned above. One extreme case would be where all parties would be hosted by a single participant node: this corresponds to a fully centralized system managed by the transportation provider. On the other hand, richer topologies allow us to build a platform that possesses scalability, resiliency, and openness.
As an example, let us discuss the topology depicted by the figure below. On the traveler side, any number of nodes can be deployed and connected to the domain. On the operational side, one transportation entity (consisting of a set of vehicles and their operator) can be either hosted on the same node (e.g., “Operations Node 2”) or on different nodes (e.g., “Operations Node 1” and “Vehicles 1”). Moreover, some vehicles (e.g., “Vehicle 2”) can also be hosted by multiple nodes.
This topology enables the traveler to have a unified view over the offers of multiple operators. Moreover, with small changes in the code, it would be possible for vehicles to offer rides to clients of different operators at the same time. For the traveler, it means that a multi-modal journey can be managed in a single workflow. For the operators, it increases the efficiency of the fleet, because idling vehicles can be assigned to other missions, thus reducing the operational costs.