Parking sensors, lot servers and a driver app, each a separate process that only communicates by messages. Each lot server owns one lot. There is no central coordinator. Processes can be killed, links cut and replies lost; the rest keeps working.
Team: Degoma, Gonzalez-Morales, Karakra, Lee, Lopez, Nguyen, Ocegueda
alice reserves a space. bob asks for the same one and is denied.
After 6 s without a report the lot server marks the spaces unknown, not free.
On restart it replays its log. A reservation made before the crash is still there.
Five processes run in this page as Web Workers. The page acts as the network: it adds latency, drops messages and cuts links. Click a process to crash it, a link to cut it, a space to reserve it.
| time | from → to | type | detail |
|---|
TCP sockets, one JSON envelope for every message (4-byte length header, UTF-8 body), and three patterns: request-reply, publish-subscribe and group communication. Two new processes: a broker and a registry.
Each arrow is a TCP connection. Solid ones stay open, dashed ones are opened when needed. A lot server is a service to clients, a subscriber and publisher at the broker, and a member of the lot_servers group.
Connect, REQUEST, REPLY, close. The REPLY carries the request's msg_id in reply_to. If nothing comes back in 2 s the client reconnects and sends the same REQUEST again. The service caches replies by msg_id, so the retry gets the cached reply and nothing runs twice.
Unknown op or bad args: status: ERROR. No reply after 3 tries: ServiceUnavailable, written to the log.
Subscribers keep one long-lived connection to the broker. A PUBLISH becomes one EVENT per subscriber, sent on that subscriber's connection and logged once per delivery. The publisher gets an ACK with the delivered count. A subscriber that cannot be reached is removed from the topic.
Limits: the broker is a single point of failure, and a slow subscriber delays the others.
Members JOIN a group at the registry. To send, a node asks for MEMBERS, then opens one connection per member and sends GROUP_MSG, one log line per target. An unreachable member is logged and skipped. The others still get the message.
No ordering or atomic delivery. Membership can change during a send. Future work: total ordering, acknowledgements, multicast.
| field | meaning |
|---|---|
type | which kind of message; the receiver dispatches on it |
msg_id | unique id; a REPLY or ACK carries the id it answers in reply_to |
sender | process name, for the logs |
timestamp | ISO 8601 with milliseconds, sender's clock, used as ordering evidence |
payload | type-specific data |
ProtocolError and the connection is closed. A socket closed mid-read raises ConnectionClosed. Max message size 1 MB.op + args from a client to a service
status OK / ERROR, result or error text, reply_to
subscriber asks the broker for a topic
subscriber leaves a topic
publisher sends topic + data to the broker
broker delivers a publish to one subscriber
broker / registry acknowledgement, carries delivered count or members
node joins a group with its address
node leaves a group
ask the registry who is in a group
sender to each member, one connection each
| Browser demo (this page) | Python prototype (prototype/) | |
|---|---|---|
| processes | Web Workers, separate memory | OS processes, one per node |
| transport | postMessage via the page, which acts as the network | TCP sockets, 4-byte length prefix + JSON |
| patterns | request-reply, peer summaries | request-reply, publish-subscribe via broker, group via registry |
| overlay | simulated in the Milestone 3 section with the same rules | real mesh over TCP in prototype/p2p, up to five lots |
| faults | kill / restart, cut links, latency, drop, lost reply | kill any process, lost reply, broker crash, dead group member |
| logs | per-worker in memory, download as .jsonl | per-process logs/*.log, JSON lines, replayed on restart |
| tests | five scripted scenarios | 10 framing checks, 21 pattern checks, 27 overlay checks, 8 end-to-end scenarios |
The lot servers form an unstructured mesh. Each one keeps a short neighbor list, joins through any running peer, gossips its own summary, keeps replicas of the other lots, and floods a lookup for anything it does not have. There is no coordinator and no rule that says which node owns which key.
p2p/overlay.py, starting from the mesh run_demo.sh builds. Click a lot to crash it, click a stopped lot to start it again through a random peer.put(key, value) get(key) lookup(key, ttl) aggregate()run_demo.sh, numbers rebuilt from each server's neighbor list.| metric | value |
|---|---|
| links | A-B, A-C, A-D, B-C, C-D |
| degree | A 3, B 2, C 3, D 2 (average 2.5) |
| diameter | 2 hops (B to D), average path 1.17 |
| lookup cost | 12 owner-only lookups, all found, 1.17 hops on average, 2 at most |
| stretch | 1.00 (the flood always finds the shortest overlay path) |
| maintenance | 10 pings every 5 s, 2 messages per second for the whole overlay |
| gossip miss | (1 − 0.7)3 = 0.027 for A and C, (1 − 0.7)2 = 0.09 for B and D |
| join cost | 1 round trip to the bootstrap, then 1 per extra neighbor |
| leave cost | one message per neighbor, nothing else changes |
newcomer to one bootstrap peer; ACK carries neighbor pointers and the whole table
ask a peer to link; ACK carries its table
sent to each neighbor on a graceful exit
every 5 s; ACK carries a neighbor sample and the table
key, value, version, origin, path; forwarded with pf
qid, key, TTL, asker, path; duplicates dropped by qid
sent straight back to the asker with hops and path
flooded from the root; first sender becomes the parent
partial free and total counts, sent up to the parent
Every replica records when it was stored. find reports its age and flags it stale after 12 s, four missed gossip rounds. Clients see an old number labelled as old.
Neighbors see a put within one message. Everyone else in the same round with probability 1 − (1 − pf)n, otherwise within the next round (3 s) or the next ping (5 s), whose answer carries the full table.
Only the owning lot writes its key, and every write carries a version. A replica keeps a value only if its version is higher. Late or duplicated rumors cannot roll it back. Reservations always go to the owner.
Console lines from the prototype: four lots start, E joins through C and receives four replicas at once, D floods a lookup for B, C leaves, D is killed.
After C leaves, B and E are each down to one link. The random sample in the next ping answer lets them find each other, so the mesh stays in one piece.
All of them use the Milestone 2 envelope and arrive on the lot server's normal port. JOIN, NEIGHBOR and PING are answered with an ACK on the same connection. The rest are one way.
Each server holds the other lots' summaries, so it answers questions about them without asking. The system is eventually consistent: there is no moment when every lot agrees exactly, but each copy says how old it is.
| degree | diameter | for our lots | |
|---|---|---|---|
| ring | 2 | ⌊N/2⌋ | one break splits it in two lines; updates crawl around |
| tree | varies | O(log N) | every broadcast passes the root; the root is a bottleneck and a single point of failure |
| Chord | O(log N) | O(log N) | fast key lookups, but each join moves keys and updates fingers; a broadcast has to be built on top |
| our mesh | 2 to 3 | 2 | joins and leaves touch only neighbors; gossip spreads updates with no hot node |
| push: gossip | pull: lookup | |
|---|---|---|
| when | every 3 s, for each lot's own summary | a client asks about a lot that is not cached |
| spreads | origin to all neighbors, then each peer forwards with pf = 0.7 | to all neighbors, TTL drops by one per hop |
| stops | message already seen, or version not newer | query id already seen, or TTL reaches 0 |
| cost | about one message per link per round | grows like d(d − 1)k − 1 at step k |
| answer | none; the value is now in every store | P2P_FOUND straight back to the asker, then cached |