Chi parla con chi: le topologie del coordinamento#
Una rete centralizzata, con un nodo al centro e tutti gli altri appesi a lui, come i raggi di una ruota. Una rete decentralizzata, fatta di tanti piccoli centri di quel tipo collegati fra loro. Una rete distribuita, una maglia senza centri in cui ogni nodo ha molte strade per raggiungere ogni altro, come gli incroci di una città. Tre disegni, e nessuna formula: sono la prima figura del primo di undici memorandum che Paul Baran, ingegnere della RAND Corporation, pubblica nell’agosto del 1964 su come costruire una rete di comunicazione che continui a funzionare dopo che una parte dei suoi nodi è stata distrutta. Stessi apparati, stesso mestiere, tre destini diversi. La domanda che Baran mette davanti al lettore è che forma debbano avere, più che quanti ne servano.
La stessa domanda vale per una squadra di agenti. La sezione sul costo del coordinamento finiva su una differenza che qui diventa il tema: con una trascrizione condivisa, in cui ognuno legge tutto quello che dicono gli altri, i token letti crescono come il quadrato dei turni; con contesti separati, in cui ognuno legge soltanto il proprio pezzo, crescono come il numero di agenti, e il divario fra i due si allarga man mano che la squadra cresce. Fra i due casi non cambia il modello e non cambia il numero dei partecipanti: cambia chi legge i messaggi di chi, cioè la topologia.
Una precisazione sulla parola, perché qui ha due sensi molto vicini. Nella pagina d’apertura del capitolo «topologica» descriveva la regola degli storni, quella che conta i vicini invece di misurarli in metri. Qui «topologia» vuol dire una cosa più vicina all’uso comune: la forma dello schema, chi è collegato a chi. I due sensi hanno la stessa radice, perché in entrambi i casi si guarda la struttura dei collegamenti e non le distanze, ma non vanno sovrapposti: gli storni non c’entrano con le cinque forme che seguono.
Il sistema è un grafo#
La rappresentazione giusta è la più spoglia possibile: un grafo, i cui nodi sono gli agenti e i cui archi sono i canali di comunicazione. Un arco non significa «questi due possono scriversi»: dentro un programma tutti possono scrivere a tutti, basta una riga di codice. Significa «in questo progetto questi due si scrivono, e gli altri no». La topologia è un vincolo che il progettista impone, e il suo valore sta esattamente in ciò che vieta.
Su un grafo si misurano tre grandezze, le stesse che governano il progetto di una rete di calcolatori: quanta strada fa l’informazione per arrivare dove serve, quanto pesa sul nodo più carico, e cosa resta in piedi se quel nodo smette di funzionare. Ogni topologia è un compromesso fra loro.
Venti persone devono mettere in piedi una festa. Fatti tre domande sul modo in cui si sono organizzate.
La prima: per quante mani passa una notizia prima di arrivare a tutti? Se c’è un organizzatore che chiama uno per uno, due passaggi bastano sempre. Se invece ognuno telefona solo al successivo, come in una catena di sant’Antonio, per andare dal primo all’ultimo servono diciannove telefonate in fila, e chi sta in fondo la sera prima non sa ancora niente.
La seconda: quanto lavoro fa il più carico? Nel primo caso l’organizzatore di telefonate ne fa diciannove, gli altri una a testa. Nel secondo nessuno ne fa più di due. Il primo modo è velocissimo, ma tutta la fatica sta su una persona sola.
La terza, la più sgradevole: cosa succede se proprio quella persona prende l’influenza? Nel primo caso non si sa più niente: diciannove persone che non si parlano fra loro restano al buio. Nel secondo la catena si spezza in due tronconi, e metà del gruppo, quella a monte, la notizia ce l’ha comunque.
Nessuna delle due organizzazioni è migliore in assoluto: ognuna compra una di quelle tre cose vendendo le altre due, ed è questo, non il numero di invitati, che decide come andrà la serata.
Attenzione però a dove finisce quella regola, perché più avanti ci servirà. Vale per queste due organizzazioni e per tutte quelle in cui, fra due persone qualsiasi, esiste una strada sola: un solo giro di telefonate che porta da me a te. Se si accetta di dare a ciascuno una o due telefonate in più, in modo che le strade fra due persone diventino parecchie, il baratto smette di essere obbligato e si possono comprare tutte e tre le cose insieme. Lo mostreranno i numeri, quando una rete a maglia batterà l’organigramma su tutte e tre le domande, ed è la ragione per cui Baran ha disegnato tre reti e non due.
Sia \(G = (V, E)\) il grafo di comunicazione, con \(|V| = N\) agenti, e sia \(d(u,v)\) la lunghezza del cammino minimo fra due nodi. Le tre grandezze sono:
dove \(\mathrm{diam}(G)\) è il diametro (il più lungo dei cammini minimi, cioè il caso peggiore di quanti passaggi servono), \(\Delta(G)\) è il grado massimo (quanti canali fanno capo al nodo più connesso) e \(\ell(v)\) è il carico del nodo, cioè la frazione di coppie \((s,t)\) per cui almeno un cammino minimo \(\mathrm{sp}(s,t)\) attraversa \(v\) senza averlo come estremo. È una versione semplificata della centralità di intermediazione (la betweenness) su due punti: conta le coppie invece di pesarle con la frazione dei loro cammini minimi che passa davvero per \(v\), e le normalizza sul totale \(\binom{N}{2}\) delle coppie anziché sulle sole coppie che escludono \(v\). La fragilità si legge da \(\kappa(G)\), la connettività per vertici: quanti nodi bisogna rimuovere perché il grafo si spezzi. Negli alberi e nelle stelle \(\kappa(G) = 1\), e ogni nodo interno è un punto di articolazione. Per distinguere fra loro grafi che hanno tutti \(\kappa(G) = 1\) serve una misura graduata, ed è quella che stampa il programma sulle cinque forme: detto \(A\) l’insieme degli agenti e \(v^{*} = \arg\max_v \ell(v)\) il nodo più carico, la connettività residua è la frazione di coppie di agenti ancora collegate dopo averlo tolto,
dove \(G - v^{*}\) è il grafo senza quel nodo e i suoi archi. Il programma stampa anche il carico del nodo più carico, \(\ell(v^{*}) = \max_v \ell(v)\). Dove \(\kappa\) dice soltanto se il grafo si spezza, \(\mathrm{res}\) dice di quanto.
Sugli alberi le tre non sono indipendenti, ed è questo a rendere il progetto interessante. Con \(N-1\) archi in tutto non c’è margine: abbassare il diametro obbliga a concentrare gli archi da qualche parte, il che alza \(\Delta\) e \(\ell\). Lo dice una disuguaglianza. Un albero di diametro \(2k\) ha un centro da cui ogni nodo dista al più \(k\), e se il grado massimo è \(\Delta\) i nodi a distanza \(i \ge 1\) dal centro sono al più \(\Delta(\Delta-1)^{i-1}\), quindi
che è il limite di Moore per gli alberi: a \(N\) fissato, abbassare il diametro obbliga ad alzare \(\Delta\) (per la stella, \(k = 1\), dà \(\Delta \ge N-1\)). E siccome \(\kappa(G) = 1\), il nodo con \(\ell\) alto è per costruzione quello la cui rimozione taglia più coppie. In una rete di calcolatori \(\ell(v)\) alto significa un instradatore congestionato; in una squadra di agenti significa una finestra di contesto che deve contenere tutto ciò che transita, e questo è un limite più duro, perché la qualità della lettura degrada prima della lunghezza dichiarata (lo misura RULER, nella sezione sul contesto: nel 2024, di diciassette modelli che dichiaravano almeno 32.000 token, solo la metà manteneva prestazioni soddisfacenti a quella lunghezza [HSK+24]), e perché quello che sta in mezzo viene letto peggio, l’effetto lost in the middle [LLH+24].
Il vincolo non è una legge dei grafi: vale per gli alberi, la famiglia con meno archi che tenga il grafo connesso. Non discende dalle definizioni di \(\mathrm{diam}\), \(\Delta\) e \(\ell\), discende da \(|E| = N-1\). Concedendo qualche arco in più il baratto si scioglie, come mostra il conto sull’ipercubo \(Q_4\).
Le cinque forme che si incontrano davvero sono in fila nella Fig. 22.2.
Fig. 22.2 Le cinque topologie di coordinamento, in ordine di apparizione. Un supervisore che spezza il compito, lo distribuisce e ricompone; una catena in cui ognuno passa il lavoro al successivo ed esce di scena; una gerarchia, cioè supervisori di supervisori; una lavagna su cui tutti scrivono e da cui tutti leggono, senza rivolgersi a nessuno; un mercato, in cui chi ha un lavoro da far fare lo mette a bando e lo assegna a chi si offre. Nelle prime tre chi parla con chi lo decide il progettista; nelle ultime due no.#
Supervisore e lavoratori#
Un agente riceve il compito, lo scompone, ne distribuisce i pezzi ai lavoratori, raccoglie i risultati e li ricompone. I lavoratori non si parlano fra loro. È la rete centralizzata di Baran, quella con un nodo al centro e tutti gli altri appesi a lui, e nel linguaggio dei grafi è una stella: da qui in avanti la chiameremo così. È la forma più semplice da realizzare, perché nasce da sé appena un programma comincia a interrogare un modello più volte di seguito. È anche la squadra dell’apertura del capitolo: uno tiene le fila, uno scrive il codice, uno controlla se è sicuro eseguirlo, e i due in fondo non si scrivono mai [WBZ+24].
Quello che compra è il controllo, e vale più di quanto sembri: esiste un posto, uno solo, in cui sta la verità su come sta andando il compito. Chi va a cercare un errore ha un registro da leggere invece di una conversazione da ricostruire, e chi vuole fermare il lavoro prima che faccia danni sa dove mettere il controllo che sbarra la strada.
È il capo cantiere. Legge il progetto, dice al muratore di fare la parete e all’elettricista di passare i cavi, e alla fine controlla che le due cose combacino. I due non si parlano: se serve una modifica passa da lui, e nessuno dei due perde tempo dietro al lavoro dell’altro.
Il vantaggio è che, quando qualcosa non torna, c’è una persona sola a cui chiedere cosa sta succedendo. Lo svantaggio è che tutto passa da quella persona, e la sua giornata ha ventiquattro ore come quella degli altri. Con tre operai funziona benissimo. Con trenta, il capo cantiere passa la giornata ad ascoltare rapporti e non gli resta tempo per decidere.
Il rimedio sta nel modo in cui gli si parla. Niente racconti: un modulo di tre righe, che cosa è fatto, che cosa manca, che cosa serve. Otto minuti di chiacchiere a testa, con trenta operai, sono quattro ore di giornata; un minuto e mezzo a testa sono quarantacinque minuti, cioè quello che gli costerebbero cinque o sei operai lasciati liberi di raccontare. E i trenta hanno lavorato come prima.
Resta la cosa che nessun modulo ripara: se il capo cantiere si ammala, il cantiere non rallenta, si ferma.
Con \(N\) lavoratori (quindi \(N+1\) nodi in tutto, supervisore compreso) la stella ha \(\mathrm{diam}(G) = 2\) e \(\Delta(G) = N\), tutto concentrato sul centro. Ma il costo che morde è ciò che scorre negli archi, più del loro numero: il supervisore riceve \(N\) rapporti, e se ciascuno è lungo \(\bar{m}\) token la sua finestra cresce come
dove \(c_0\) è il contesto iniziale. È lineare in \(N\), non quadratica come nella trascrizione condivisa del costo del coordinamento, ed è esattamente il guadagno della stella: i lavoratori non si leggono a vicenda. Ma è lineare su un solo nodo. Con \(N = 30\) lavoratori che riportano \(\bar{m} = 800\) token, la finestra del supervisore contiene 24.000 token di rapporti prima di qualunque ragionamento.
La contromisura sta nel comprimere all’ingresso, imponendo ai lavoratori un formato di risposta stretto (uno schema, non prosa libera). Portare \(\bar{m}\) da 800 a 150 token vale, in questa formula, quanto ridurre di oltre cinque volte il numero di lavoratori, e non costa nulla in capacità di lavoro.
Quello che si paga sta tutto sullo stesso nodo. Il supervisore è insieme il collo di bottiglia (ogni decisione aspetta il suo turno) e il punto singolo di rottura: se sbaglia lui, nessun altro può accorgersene, perché i lavoratori vedono solo il proprio pezzo. Sotto una certa taglia è quasi sempre la scelta giusta; sopra, la stella non si allarga, si spezza.
La catena#
Ognuno riceve dal precedente, fa la sua parte, passa al successivo ed esce di scena: chi estrae i dati li passa a chi li analizza, che passa a chi scrive il rapporto. In inglese si chiama handoff, «passaggio di consegne», ed è la forma più semplice che esista: una fila, senza scorciatoie e senza modo di tornare indietro. Compra due cose. La semplicità, perché non c’è niente da coordinare, l’ordine della fila è il programma. E la pulizia di quello che ciascuno si trova davanti: nessuno legge conversazioni altrui, ognuno vede solo il proprio pezzo, e le finestre restano le più corte di tutte le cinque forme. Quello che costa è l’assenza di ritorno.
I bambini del telefono senza fili, questa volta, non stanno giocando, stanno lavorando. Il primo raccoglie i dati e li passa al secondo, il secondo li analizza e passa al terzo, il terzo scrive il rapporto. E come nel gioco, nessuno ha visto l’originale tranne il primo.
Da lì viene tutto il resto. Se al secondo passaggio qualcuno capisce male una cosa, quell’errore arriva al quinto travestito da verità di partenza, e al quinto non c’è nessuno che possa accorgersene: per accorgersene bisognerebbe avere in mano il foglietto iniziale, e chi sta in fondo alla fila non ce l’ha mai avuto.
E poi c’è il conto che si moltiplica. Sei passaggi fatti bene novantacinque volte su cento non danno una fila affidabile al novantacinque per cento: danno una fila che arriva in fondo intatta poco più di settantatré volte su cento, cioè fallisce più di una volta su quattro, pur essendo fatta di partecipanti che non sbagliano quasi mai. E la fila si può allungare molto: quindici agenti in fila sono quattordici passaggi, cioè quattordici occasioni perché la richiesta di partenza si deformi per strada.
La cosa più sgradevole è che non se ne vede niente. Due agenti che hanno in testa due versioni diverse del compito continuano a scriversi messaggi cortesi e ben scritti fino in fondo [CPY+25], e il rapporto finale esce pulito, ordinato e sbagliato.
La catena è un cammino, cioè l’albero con fattore di ramificazione \(b = 1\): \(N-1\) archi, nessun arco all’indietro, \(\mathrm{diam}(G) = N-1\).
Quello che paga lo abbiamo già calcolato: non c’è ritorno. Un errore commesso al secondo passo arriva al quinto travestito da dato di partenza, e a valle nessuno ha modo di accorgersene, perché a valle nessuno ha visto l’originale. È la composizione moltiplicativa degli errori nella sua forma peggiore: con sei passi corretti al 95% ciascuno, la catena intera regge \(0{,}95^6 \approx 0{,}74\), cioè fallisce una volta su quattro pur essendo fatta di agenti che non sbagliano quasi mai. E siccome il diametro cresce come \(N\), quindici agenti in fila sono quattordici passaggi fra il primo e l’ultimo, quattordici occasioni perché una specifica si deformi strada facendo. Nella tassonomia dei fallimenti reali questa famiglia ha un nome, disallineamento fra agenti, ed è la più insidiosa perché non produce sintomi: due agenti che hanno in testa due versioni diverse del compito si scrivono messaggi cortesi e ben formati fino in fondo [CPY+25].
La catena si usa quando i passi sono davvero uno dopo l’altro e ciascuno ha un modo suo di verificare il proprio risultato, così che il controllo stia dentro ogni passaggio e non solo alla fine. Senza controlli lungo la strada, ogni agente aggiunto alla fila toglie un’altra fetta all’affidabilità di quello che arriva in fondo.
La gerarchia#
Quando la stella non regge più, la mossa naturale è metterne una dentro l’altra: supervisori di supervisori, ciascuno con la sua squadretta. È l’organigramma, lo schema di chi riferisce a chi che hanno un’azienda o una scuola, ed è la forma che permette di diventare grandi, per una ragione aritmetica: si decide in anticipo quanti sottoposti può avere ciascun capo, e quel numero non cambia per quanti agenti ci siano in fondo. Nel gergo dei grafi l’organigramma si chiama albero, il capo supremo è la radice, quelli in fondo che non hanno sottoposti sono le foglie, e quanti sottoposti ha ciascun capo è il fattore di ramificazione \(b\).
Fila e organigramma sono la stessa forma con un numero diverso. In tutte e due, fra due partecipanti qualsiasi c’è una strada sola. Quello che cambia è quante persone riferiscono a ciascuno. Nella fila una, e allora si allunga senza fine: quindici agenti, quattordici passaggi. Nell’organigramma due, o cinque, o dieci, e la fila si accorcia di colpo, perché a ogni livello il gruppo si moltiplica.
Il conto, con due sottoposti a testa. Il capo supremo è uno; sotto di lui due; sotto quei due, quattro; sotto i quattro, otto: uno più due più quattro più otto fa quindici, ed è tutto l’organigramma in quattro livelli. Adesso manda uno dell’ultimo livello a parlare con un altro dell’altra metà: deve salire tre gradini fino al capo supremo e riscenderne tre. Sei passaggi invece di quattordici, con le stesse quindici persone.
Il prezzo si vede già a scuola. A ogni livello qualcuno riassume: la classe discute, il rappresentante riporta al consiglio d’istituto l’essenziale, e l’essenziale lo sceglie lui. È il modulo di tre righe del capo cantiere, ma lì il passaggio era uno e a sparire erano le chiacchiere; qui i passaggi sono in fila, e ogni volta resta fuori qualcosa che contava. Se a ogni passaggio verso l’alto sopravvive l’ottanta per cento di ciò che contava, con tre passaggi in cima arriva l’ottanta per cento dell’ottanta per cento dell’ottanta per cento, cinquantuno su cento. Il riassunto però sembra completo, è per questo che è un riassunto, e chi sta in cima non sa che cosa manca.
Da qui una regola che sorprende: pochi livelli e larghi. Ogni livello in meno è un riassunto in meno, e i riassunti si moltiplicano fra loro. Al limite il capo supremo prende quattordici sottoposti diretti: un riassunto solo, ottanta su cento invece di cinquantuno, ma quel capo è di nuovo il capo cantiere che passa la giornata ad ascoltare. Si allarga finché la sua giornata regge.
E quando il risultato finale è sbagliato, capire dove lo sia diventa difficile: la responsabilità si è diluita lungo la scala, e ogni livello può dire in buona fede di aver fatto la sua parte.
Catena e gerarchia sono entrambe alberi, cioè grafi connessi e aciclici con \(N-1\) archi e un solo cammino fra ogni coppia di nodi; a distinguerle è il fattore di ramificazione \(b\). Con \(b = 1\) si ha il cammino, \(\mathrm{diam}(G) = N-1\). Con \(b > 1\) e un albero completo di profondità \(D\) si ha \(N = (b^{D+1}-1)/(b-1)\), quindi
dove \(D\) è il numero di livelli sotto la radice. Il \(b+1\) è il grado di un nodo interno, \(b\) figli più il genitore, e vale appena esiste un nodo interno che non sia la radice: a \(D = 1\) l’albero è la stella e il massimo torna a essere \(b\). Il diametro passa da lineare a logaritmico in \(N\): è tutto il guadagno della gerarchia, e con \(b = 2\) e \(N = 15\) vale \(D = 3\), \(\mathrm{diam}(G) = 6\) contro i \(14\) della catena.
La perdita per riassunto si modella, in modo dichiaratamente grossolano, come un fattore per livello: se ogni passaggio verso l’alto conserva una frazione \(\lambda \in (0,1)\) dell’informazione rilevante, in cima ne arriva \(\lambda^{D}\). Il valore di \(\lambda\) non si sa misurare su un riassunto in linguaggio naturale; la forma sì. A \(N\) fissato, alzare \(b\) abbassa la profondità \(D\), e con essa migliorano insieme la frazione che arriva in cima, \(\lambda^{D}\), e il diametro, \(2D\): per \(N = 15\) e \(\lambda = 0{,}8\), con \(b = 2\) si ha \(D = 3\) e \(\lambda^{D} = 0{,}512\), con \(b = 14\) si ha \(D = 1\) e \(\lambda^{D} = 0{,}8\). Preso da solo, questo modello spingerebbe \(b\) all’assurdo: con \(b = N-1\) e \(D = 1\) si è ricostruita la stella, con il collo di bottiglia e il punto singolo di rottura che la rendono insostenibile oltre una certa taglia. Il termine che manca è il carico del singolo supervisore, la finestra \(c_0 + b\,\bar{m}\) vista per la stella, che cresce linearmente in \(b\): è lui il freno, e la regola operativa che ne esce è alzare \(b\) finché la finestra di ciascun supervisore regge, e abbassare \(D\) di conseguenza. È il contrario di ciò che suggerisce l’istinto organizzativo.
Il secondo costo è formale quanto il primo: la gerarchia rende difficile l’assegnazione del merito (e della colpa). Attribuire un esito sbagliato a un nodo richiede di ripercorrere all’indietro tutti i riassunti, e i riassunti sono proprio ciò che ha cancellato l’informazione che servirebbe. È lo stesso problema di credit assignment che nell’apprendimento per rinforzo multi-agente si affronta con la scomposizione del valore, e ne parla la sezione su imparare insieme.
Le tre forme viste finora sono schemi di agenti veri, e allora conviene misurarle invece di ragionarci a intuito. Il codice che segue ne costruisce cinque: le tre, più la lavagna (un foglio comune su cui tutti scrivono, che arriva fra poco) e una forma che serve solo da termine di paragone. Per ciascuna calcola quattro numeri: le tre domande sulla festa più una.
Il diametro è la prima domanda: per quante mani passa una notizia, nel caso peggiore. Il grado massimo è la seconda nella versione più concreta: quanti interlocutori diretti ha chi ne ha di più (nella festa erano le diciannove telefonate dell’organizzatore). Il carico è la stessa domanda guardata da un altro lato, e misura quanto uno è di passaggio: quale frazione degli scambi fra gli altri deve attraversarlo. La connettività residua è la terza domanda: quante coppie riescono ancora a parlarsi dopo che quella persona si è ammalata, e se fa zero non parla più nessuno. I quattro numeri non si leggono tutti nello stesso verso: per il diametro, il grado massimo e il carico il valore buono è quello basso, per la connettività residua è quello alto.
Le prime quattro forme hanno quindici agenti a testa: stessa squadra, schemi diversi. La quinta è quella che Baran disegnava per terza e che finora abbiamo lasciato da parte: una maglia in cui ogni nodo ha più strade per raggiungere ogni altro. Ne usiamo la versione con più struttura, l’ipercubo \(Q_4\), cioè il cubo portato a quattro dimensioni: sedici nodi, uno per ogni numero da 0 a 15 scritto in binario con quattro cifre (il modo in cui contano i calcolatori), e un arco fra due numeri che differiscono in una cifra sola. Ogni agente ha esattamente quattro vicini, nessuno sta più al centro degli altri, e gli archi sono trentadue. Di agenti ne vuole sedici e non quindici, perché \(2^4\) non si ritaglia: uno in più su quindici è troppo poco per spiegare i numeri che seguono.
import numpy as np
INF = 10**6
def distanze(A):
"""Cammini minimi fra tutte le coppie (Floyd-Warshall), grafo non pesato."""
D = np.where(A == 1, 1, INF)
np.fill_diagonal(D, 0)
for k in range(len(A)):
D = np.minimum(D, D[:, k, None] + D[None, k, :])
return D
def grafo(n, archi):
A = np.zeros((n, n), dtype=int)
for i, j in archi:
A[i, j] = A[j, i] = 1
return A
def metriche(A, agenti):
"""Diametro fra agenti, grado massimo, carico del nodo piu' sollecitato
(frazione di cammini minimi che lo attraversano) e frazione di coppie
ancora collegate dopo averlo tolto."""
D = distanze(A)
coppie = [(s, t) for i, s in enumerate(agenti) for t in agenti[i + 1:]]
carico = [sum(1 for s, t in coppie
if v not in (s, t) and D[s, v] + D[v, t] == D[s, t]) / len(coppie)
for v in range(len(A))]
v = int(np.argmax(carico)) # il nodo piu' sollecitato
Dv = distanze(np.delete(np.delete(A, v, 0), v, 1))
resta = [a - (a > v) for a in agenti if a != v] # indici dopo la rimozione
vive = sum(1 for i, s in enumerate(resta) for t in resta[i + 1:]
if Dv[s, t] < INF)
n = len(resta)
return (max(D[s, t] for s, t in coppie), A.sum(axis=1).max(),
carico[v], vive / (n * (n - 1) / 2))
N = 15 # quindici agenti in tutte le topologie ad albero: stessa squadra, forme diverse
stella = grafo(N, [(0, i) for i in range(1, N)])
catena = grafo(N, [(i, i + 1) for i in range(N - 1)])
albero = grafo(N, [(i, 2*i + 1) for i in range(7)] + [(i, 2*i + 2) for i in range(7)])
lavagna = grafo(N + 1, [(N, i) for i in range(N)]) # il nodo N e' la lavagna
# La terza rete di Baran, la maglia: ipercubo a 4 dimensioni. Sedici agenti,
# arco fra due numeri che in binario differiscono per una sola cifra.
ipercubo = grafo(16, [(i, i ^ (1 << b))
for i in range(16) for b in range(4) if i < (i ^ (1 << b))])
print(f"{'topologia':10} {'diametro':>9} {'grado max':>10} {'carico':>7} {'residua':>8}")
for nome, A, agenti in [("stella", stella, list(range(N))),
("catena", catena, list(range(N))),
("albero", albero, list(range(N))),
("lavagna", lavagna, list(range(N))),
("ipercubo", ipercubo, list(range(16)))]:
d, g, c, r = metriche(A, agenti)
print(f"{nome:10} {d:9d} {g:10d} {c:6.0%} {r:7.0%}")
# La tabella stampa solo il nodo piu' carico. Nell'albero conviene guardarli
# tutti, perche' il primo della classe non e' quello che ci si aspetta.
D = distanze(albero)
coppie = [(s, t) for s in range(N) for t in range(s + 1, N)]
carico = [sum(1 for s, t in coppie
if v not in (s, t) and D[s, v] + D[v, t] == D[s, t]) / len(coppie)
for v in range(N)]
print(f"\nalbero: radice {carico[0]:.0%}, capo intermedio {carico[1]:.0%}, "
f"foglia {carico[7]:.0%}")
topologia diametro grado max carico residua
stella 2 14 87% 0%
catena 14 2 47% 46%
albero 6 3 54% 37%
lavagna 2 15 100% 0%
ipercubo 4 4 21% 100%
albero: radice 47%, capo intermedio 54%, foglia 0%
Quattro letture, e l’ultima rimette in discussione le prime tre.
La prima. La stella compra il diametro più basso possibile fra le forme che spendono pochi fili (due passaggi: da un lavoratore al centro, e dal centro all’altro) e lo paga con l’87% del traffico su un nodo solo e una connettività residua nulla: se quel nodo si ferma non resta niente. L’87 e non il 100 perché quando è il centro stesso a parlare con qualcuno non lo si conta come traffico di passaggio, e quelle conversazioni sono quattordici delle centocinque coppie possibili. La lavagna, che ha lo stesso diametro, arriva invece al 100%: il foglio comune sta nel mezzo di ogni scambio, perché non parla mai per conto suo.
La seconda. L’organigramma non batte la fila né sul carico (54% contro 47%) né su quello che resta in piedi (37% contro 46%): la batte sul diametro, sei contro quattordici, e basta. La gerarchia compra distanza, non robustezza, ed è bene non aspettarsi dell’altro.
La terza, ed è la più istruttiva: nell’organigramma il più carico è un capo intermedio, non il capo supremo, con il 54% del traffico contro il 47%. È la riga che il programma stampa in fondo, dopo la tabella. La ragione si vede contando le coppie. Il capo supremo sta in mezzo soltanto fra chi sta nella metà sinistra e chi sta nella destra: sette per sette, 49 coppie su 105. Un capo intermedio sta in mezzo fra ciascuno dei sei che ha sotto di sé e gli otto che stanno fuori dal suo ramo, 48 coppie, e in più fra i due gruppetti da tre che ha sotto, altre 9: 57 su 105. Chi progetta squadre di agenti farebbe bene a saperlo, perché il ruolo da irrobustire per primo non è quello che sembra.
E poi c’è l’ultima riga della tabella. L’ipercubo batte l’organigramma a due sottoposti su tutte e tre le grandezze insieme: diametro quattro contro sei, carico 21% contro 54%, connettività residua 100% contro 37%, cioè togliendo il nodo più carico non si scollega nessuno. Lo paga con un collegamento in più sul nodo più connesso, quattro invece di tre; ma lo paga su tutti, perché nell’ipercubo quattro ce li hanno tutti, mentre nell’albero tre ce li hanno solo i sei capi intermedi, il capo supremo ne ha due e le otto foglie uno.
Contiamoli, i fili. Se sommo i collegamenti che ciascuno ha, ogni filo lo conto due volte, una per ognuno dei due che sta alle sue estremità: il totale va quindi diviso a metà. Nell’albero la somma è due (il capo supremo) più tre per sei (i capi intermedi) più uno per otto (le foglie), cioè ventotto, e diviso due fa quattordici fili. Nell’ipercubo è quattro per sedici, cioè sessantaquattro, e diviso due fa trentadue. Più del doppio, ed è tutto lì il segreto.
La ragione è strutturale: in uno schema abbastanza regolare nessuno sta più al centro degli altri, quindi il traffico si distribuisce da sé, e con più strade fra ogni coppia togliere qualcuno non spezza niente. Il baratto fra le tre grandezze era il prezzo di chi vuole spendere pochi fili, non una legge: vale perché fra due partecipanti c’è una strada sola, e chi sta su quella strada la porta tutta.
Se la maglia vince su tutto, perché il resto della sezione parla d’altro? Perché i nodi di Baran erano macchine che smistano, mentre i nostri sono agenti che leggono e scrivono, e un collegamento in più non costa un cavo: costa, a ogni giro, altro testo da rileggere e da scrivere. Se a ogni giro ciascuno scrive ai suoi vicini e legge quello che gli arriva, ogni filo porta due messaggi, uno per verso, e il testo letto in un giro va con il numero di fili: sessantaquattro messaggi nell’ipercubo, ventotto nell’organigramma, più del doppio per lo stesso lavoro. Non è il conto che esplode della trascrizione condivisa, dove fra sedici agenti che leggono tutti gli altri i messaggi letti in un giro sarebbero duecentoquaranta; e a ciascun agente ne toccano pochi, quattro, meno dei quattordici che arrivano al centro di una stella. Il prezzo vero è un altro: nella maglia nessuno vede l’insieme. Un’informazione impiega fino a quattro giri per attraversarla, e ogni giro sono sedici chiamate al modello; e alla fine non c’è nessuno che tenga la risposta, per cui gli agenti devono mettersi d’accordo su quale sia, che è il problema della sezione su protocolli e consenso. Baran poteva tirare fili perché la sua rete doveva soltanto far passare i messaggi, e un cavo in più costava un cavo in più; la nostra deve anche decidere. Ed è la ragione per cui le forme che si usano davvero, le tre viste fin qui e le due che seguono, sono varianti dei primi due disegni di Baran e mai del terzo.
La lavagna condivisa#
Le prime tre topologie hanno una cosa in comune: chi parla con chi lo decide il progettista, e lo decide prima che il sistema parta. Le due che restano vi rinunciano, e in cambio ottengono qualcosa che con un grafo fissato in anticipo non si ottiene.
Nella prima, nessuno scrive a nessuno. C’è un foglio comune, la lavagna, su cui tutti leggono e scrivono: un agente ci mette sopra un’ipotesi, un altro la vede comparire e reagisce, un terzo la corregge. Nessuno sa chi siano gli altri, e non gli serve saperlo; un pezzo di programma a parte decide, giro dopo giro, chi lasciar agire.
L’architettura nasce dentro un riconoscitore di parlato, e il motivo per cui nasce lì è il ritratto in miniatura del problema che risolve (il riconoscimento del parlato ha poi un capitolo suo, Speech Recognition). Riconoscere il parlato vuol dire far collaborare conoscenze di natura incompatibile, e nessuna affidabile da sola: com’è fatto il suono, come si dividono le sillabe, quali parole esistono, come si mettono in fila, che cosa ha senso dire in quel contesto. Il suono propone parole plausibili e sbagliate, la grammatica scarta le sequenze impossibili, il significato sa che in quel dominio si parla di computazione e non di cucina. Soprattutto, non esiste un ordine giusto in cui interpellarle: a volte è un pezzo di suono chiaro a far partire tutto, a volte è una parola riconosciuta a metà frase che permette di indovinare quelle attorno. Una catena di montaggio avrebbe dovuto fissare quell’ordine in anticipo. La lavagna non lo fissa.
Il sistema si chiama Hearsay-II e fu costruito alla Carnegie Mellon University, a Pittsburgh, in un programma di ricerca di cinque anni sulla comprensione del parlato finanziato dalla DARPA, l’agenzia del Dipartimento della difesa statunitense che finanzia la ricerca a lungo termine; lo racconta un articolo di rassegna del 1980 di Lee Erman e colleghi [EHRLR80]. Doveva capire frasi dette a voce, di seguito e senza pause, per interrogare una raccolta di riassunti di articoli di informatica, con un vocabolario di 1011 parole. Delle ventitré frasi di prova, mai sentite prima, ne fraintese il senso di due, cioè ne capì il novantuno per cento (le frasi con almeno una parola sbagliata, e non soltanto quelle fraintese nel senso, erano il diciannove per cento); su così pochi casi, una percentuale va presa come un ordine di grandezza.
In una sala operativa, come quella della protezione civile durante un’alluvione, la lavagna tiene tutto quello che si sa finora, scritto a mano e cancellabile. Chi entra non chiede a nessuno il permesso di parlare: guarda la lavagna, vede se sa aggiungere qualcosa, scrive, esce. Il meteorologo scrive che il vento gira; il tecnico legge quella riga e corregge una stima che aveva scritto lui mezz’ora prima; nessuno dei due sa dell’esistenza dell’altro.
Il pregio è che si può aggiungere uno specialista nuovo senza avvisare nessuno: se sa leggere la lavagna e scriverci sopra, è dentro, e nessuno degli altri va modificato. È il contrario del capo cantiere, che va aggiornato ogni volta che arriva un operaio e che, a differenza della lavagna, ha una giornata sola da spendere.
I difetti sono i due che chiunque abbia visto una lavagna vera conosce. Il primo è la ressa: in due che scrivono nello stesso punto nello stesso momento si danno fastidio, e serve una regola su chi va prima. La regola non guarda i gradi: scrive per primo chi in quel momento ha da aggiungere la cosa che serve di più, e lo si decide riga per riga. Il secondo difetto è che, guardandola a fine giornata, non si sa più chi ha scritto cosa: c’è un risultato, e se è sbagliato non si sa da quale mano sia uscito l’errore.
Non tutto passa dalla lavagna. I conti che uno fa per arrivare alla sua riga restano sul suo taccuino: trascriverne ogni passaggio intermedio lo rallenterebbe e basta, e certe volte gli impedirebbe di arrivarci. E se il lavoro è sempre lo stesso e l’ordine si conosce già, radunarsi a ogni giro per decidere chi scrive è tempo tolto al lavoro: lì serve una fila con i compiti assegnati.
L’architettura ha tre pezzi, e conviene chiamarli con i nomi originali. La blackboard è una memoria globale strutturata in livelli di astrazione crescente (in Hearsay-II sono sette: parametro, segmento, sillaba, parola, sequenza di parole, frase, e in cima l’interrogazione alla base dati), su cui vivono le ipotesi, ciascuna con il proprio intervallo temporale e un punteggio di credibilità. Le knowledge source sono programmi indipendenti, ciascuno una coppia condizione-azione: la condizione dichiara a quali cambiamenti della lavagna il modulo reagisce, l’azione dice cosa scrive in risposta. Il terzo pezzo è lo scheduler: a ogni ciclo calcola una priorità per ogni azione applicabile ed esegue quella di valore atteso più alto, il che rende il controllo opportunistico invece che prestabilito.
Topologicamente è una stella il cui centro non è un agente: nella tabella di poco fa la lavagna ha diametro 2 come il supervisore, ma un carico del 100% (ogni interazione fra agenti la attraversa) e un grado massimo di 15 che non appartiene a nessun agente. La differenza conta: un centro che decide ha per limite una finestra di contesto e una capacità di ragionamento, un centro che conserva ha per limite la contesa in scrittura e la coerenza, cioè problemi da basi di dati (transazioni, versioni, blocchi) con soluzioni note. Con agenti linguistici, però, la lavagna è testo libero: il controllo di versione e di conflitto che una base di dati fa su campi tipizzati qui non c’è, e due scritture fra loro incoerenti si scoprono soltanto con un terzo agente che le legga, o imponendo uno schema rigido a ciò che si scrive. In cambio il disaccoppiamento è massimo: le knowledge source non si nominano fra loro, e aggiungerne una non richiede di modificare le altre.
Gli autori stessi elencano due debolezze, e valgono ancora. La prima nasce dalla generalità: ogni decisione passa per la lavagna, una scelta che si è rivelata desiderabile fra moduli e inadatta ai passaggi intermedi dentro un modulo, dove le knowledge source di Hearsay-II usavano strutture dati private e specializzate (reti sequenziali per il riconoscitore di parole, una grande matrice di bit delle adiacenze per quello di sequenze); costringerle nello stile della lavagna, scrivono, o falliva del tutto o degradava le prestazioni in modo intollerabile. La seconda riguarda l’efficienza: deliberare a ogni ciclo su quale azione convenga costa, e si giustifica solo finché per lo stesso compito non esiste un algoritmo esplicito; appena l’algoritmo c’è, compilarlo ed eseguirlo direttamente rende di più.
Un terzo costo lo aggiungiamo noi, ed è quello che ci riguarda più da vicino: la provenienza. Con decine di scritture asincrone su una struttura condivisa, ricostruire quale agente abbia prodotto quale contributo richiede di registrarlo esplicitamente, altrimenti l’informazione è perduta e con essa ogni possibilità di attribuzione.
Il mercato#
Le prime quattro topologie danno per scontato che si sappia in anticipo chi sa fare cosa. Ma se non lo si sa? Se gli agenti disponibili cambiano, se le loro competenze non sono dichiarate, se chi è libero adesso non lo era un minuto fa?
La risposta è vecchia quanto il commercio: si mette il compito a bando. Chi ha un lavoro da far fare lo annuncia, chi si ritiene capace presenta un’offerta, il banditore valuta e assegna. È il contract net protocol, formulato da Reid G. Smith in un articolo del dicembre 1980 sulle IEEE Transactions on Computers [Smi80] e dimostrato lì su una rete di sensori distribuiti, che doveva organizzarsi da sé in base a quali nodi c’erano e a dove si trovavano.
Quello che compra è la possibilità di assegnare il lavoro strada facendo, senza che nessuno tenga l’elenco di chi c’è e di chi sa fare cosa. Nessuno è designato capo in anticipo: «chi bandisce» e «chi esegue» sono ruoli che si prendono e si lasciano durante il lavoro, e di solito uno li ricopre entrambi nello stesso momento, per contratti diversi. Chi ha vinto un lavoro può spezzarlo e bandirne i pezzi, diventando banditore a sua volta: una gerarchia c’è, ma è temporanea, e la disegna il lavoro invece del progettista.
Funziona come un bando di gara, e i messaggi che servono sono quattro. Il banditore dice: «serve questo lavoro; possono rispondere solo quelli che hanno il tal requisito; nella risposta scrivetemi queste cose; c’è tempo fino a giovedì». Chi si sente in grado risponde con un’offerta. Il banditore le confronta e assegna il compito a chi gli sembra più adatto. E il quarto, quello che ci si dimentica sempre: chi ha preso il lavoro alla fine deve riferire, altrimenti il banditore non sa nemmeno se è stato svolto.
La cosa elegante è che la scelta la fanno in due. Il banditore sceglie fra chi si è offerto, ma prima ancora ciascuno ha scelto se offrirsi e per quale bando: un agente sommerso di lavoro semplicemente non risponde, e il sistema si riequilibra da sé senza che nessuno tenga il conto di chi è libero.
Il costo è altrettanto facile da vedere: il bando è lavoro che non produce niente. Se dieci agenti leggono l’annuncio e cinque preparano un’offerta, sono cinque ragionamenti spesi per decidere chi ne farà uno. Su compiti piccoli la gara costa più del lavoro che assegna.
E poi c’è il problema di chi promette troppo: quello che giura di finire in due giorni a metà prezzo, e poi non lo fa. Nelle gare vere ha perfino un nome, l’offerta anomala, ed è quella che chi bandisce deve controllare prima di assegnare. Un modello di linguaggio a cui si chiede «sei in grado di fare questo?» tende a rispondere di sì, e allora la gara premia chi si stima meglio, non chi lavora meglio. Contro le promesse il rimedio è chiedere qualcosa di guardabile: un pezzo di lavoro già fatto su un campione, e la memoria di come è andata l’ultima volta con lui.
Il protocollo ha quattro messaggi principali. L’annuncio di compito, con quattro campi: l’astrazione del compito (di che lavoro si tratta), la specifica di eleggibilità (i requisiti minimi per poter offrire, un filtro che serve a tagliare traffico inutile), la specifica dell’offerta (quali informazioni il gestore vuole ricevere) e il tempo di scadenza. L’offerta, che descrive il nodo secondo quanto richiesto. L’assegnazione, con la specifica del compito. E i rapporti, interinali e finale. Smith attribuisce alla negoziazione quattro proprietà: è locale (nessun controllo centralizzato), lo scambio è bidirezionale, ciascuna parte valuta secondo il proprio criterio, e l’accordo finale è per selezione reciproca.
Il costo si conta in messaggi. Collocare un compito fra \(N\) candidati richiede un annuncio (uno solo se il canale è a diffusione, altrimenti \(N\)), fino a \(N\) offerte e un’assegnazione:
dove \(M(N)\) è il numero di messaggi per collocare un solo compito, e l’uguaglianza vale quando rispondono tutti i candidati: la specifica di eleggibilità serve proprio a ridurre le offerte. Con agenti classici sono pacchetti di rete e non contano nulla; con gli LLM ogni offerta è una chiamata al modello che legge l’annuncio e produce una valutazione. Con \(N = 10\) candidati e un annuncio da 2000 token, la gara costa dell’ordine di \(10 \times 2000 = 20.000\) token in ingresso prima che qualcuno abbia cominciato a lavorare. Smith lo dice a modo suo, ed è la regola operativa da portarsi via: la dimensione dei compiti messi a contratto dev’essere grande, altrimenti l’accelerazione ottenuta distribuendo se la mangia lo sforzo di distribuire.
Il secondo costo è la calibrazione delle offerte. Il protocollo assume che un nodo sappia stimare la propria idoneità, ipotesi ragionevole quando l’offerta è «ho tre sensori acustici a queste coordinate» e insostenibile quando è un modello di linguaggio che dichiara di saper fare una cosa. Il vincitore sistematico diventa l’agente più ottimista, e l’ottimismo non correla con la competenza. È la maledizione del vincitore delle aste: vince chi ha sovrastimato di più. E se l’ottimismo è un tratto stabile di certi agenti, e non un errore che capita a caso, diventa una selezione avversa: il protocollo seleziona proprio il tipo di partecipante che non voleva. Le contromisure sono due, e nessuna sta nel protocollo: rendere l’offerta verificabile (non «so farlo» ma un risultato parziale su un campione, che il gestore può controllare) e pesare le offerte con la storia degli esiti passati. È la stessa lezione dei fallimenti reali dei sistemi multi-agente, dove la verifica inadeguata è una delle tre famiglie ricorrenti [CPY+25]: chi dichiara di saper fare una cosa e chi dichiara che è stata fatta bene pongono lo stesso problema, e la cura è la stessa, cioè qualcosa che il banditore possa controllare da sé.
Coordinarsi senza sapere con chi#
Conviene isolare ciò che lavagna e mercato hanno in comune, perché è il punto più profondo della sezione. Sono i due modi di coordinarsi senza un grafo deciso in anticipo, e risolvono lo stesso problema in modi opposti e simmetrici. Il malinteso da togliere di mezzo subito è che rinuncino ai messaggi diretti: il contract net è fatto soltanto di messaggi diretti, appena quattro tipi, e la Fig. 22.2 disegna le frecce che vanno dal banditore a ciascun offerente. A sparire è il progettista che stabilisce in anticipo chi scriverà a chi, non il canale.
La lavagna ci rinuncia togliendo il destinatario: nessuno scrive a nessuno, ognuno lascia una traccia in uno spazio comune e reagisce alle tracce che ci trova. Il coordinamento sta in quello che c’è scritto nello spazio comune. L’idea ha un nome preciso, stigmergia, coniato nel 1959 dal biologo francese Pierre-Paul Grassé per le termiti che ricostruiscono il nido senza progetto e senza capo, ciascuna reagendo a quello che le altre hanno già costruito; ed è il meccanismo su cui si regge l’ottimizzazione a colonia di formiche, nella sezione su sciami e simulazioni.
Il mercato ci rinuncia in modo opposto: il destinatario ce l’ha eccome, ma non lo sceglie il progettista, lo trova il bando. Gli agenti non si conoscono e condividono una grammatica di messaggi (annuncia, offri, assegna) che permette a due sconosciuti di accordarsi su chi fa cosa; chi risponderà al prossimo annuncio non lo sa nessuno finché non risponde, e il grafo di quella conversazione esiste solo dopo che è avvenuta. Il coordinamento sta qui nella forma della conversazione, che è il tema della sezione su protocolli e consenso: là ogni messaggio si porterà scritto in cima che cosa fa, e la decisione collettiva diventerà una regola di voto.
Detto altrimenti: quando non si sa in anticipo con chi si parlerà, o si condivide un posto o si condivide una lingua.
Scegliere#
La topologia si sceglie dal compito, mai dall’eleganza. Le tre domande sulla festa non dicono quale forma sia migliore, dicono cosa si compra e cosa si vende; il compito dice quale delle tre cose non è negoziabile. E vale l’avvertenza dell’ipercubo: quel baratto obbligato è il prezzo di chi vuole spendere pochi collegamenti, non una legge di natura, e qui lo si accetta perché ogni collegamento in più è altro testo da rileggere per qualcuno, e perché una maglia senza centro, alla fine, deve mettersi d’accordo.
Un compito le cui parti sono indipendenti chiede un supervisore: scomponi, distribuisci, ricomponi, e il costo del centro è un prezzo onesto per avere un posto solo dove sta la verità. Un compito i cui passi vengono davvero uno dopo l’altro, e ciascuno si può verificare per conto suo, chiede una catena, con un controllo dentro ogni passaggio.
Un compito troppo grande per un supervisore solo chiede una gerarchia, tenuta più larga che alta. Ogni livello in più è un riassunto in più, e i riassunti si moltiplicano fra loro; a parità di agenti, allargare toglie livelli e accorcia anche le distanze, quindi su questi due conti più larga è sempre meglio. Il limite viene da un terzo conto, quanto ciascun capo intermedio riesce a leggere: si allarga finché la sua giornata regge, e non oltre, perché oltre si è semplicemente rifatta la stella con i suoi guai.
Un compito in cui contributi di natura diversa devono incontrarsi senza un ordine stabilito in anticipo chiede una lavagna. Un compito in cui non si sa chi sa fare cosa chiede un mercato, purché i pezzi messi a bando siano grandi abbastanza da ripagare il bando.
Chi non riesce a rispondere a queste domande sul proprio compito ha comunque un’informazione utile: non lo ha ancora capito abbastanza per costruirci attorno una squadra. Un agente solo, con un buon foglio di istruzioni e un controllo che sbarra la strada, è nel frattempo un ottimo posto dove aspettare.
Da ricordare
Un sistema multi-agente è uno schema di chi parla con chi, e si giudica su tre domande: per quante mani passa una notizia, quanto lavora il più carico, e che cosa resta in piedi se proprio quello si ferma.
Nelle forme in cui fra due partecipanti c’è una strada sola (la fila, il capo cantiere, l’organigramma) quelle tre cose si comprano una vendendo le altre. Non è una legge, ed è il conto dell’ipercubo a dimostrarlo: dando a ciascuno qualche collegamento in più, in modo che le strade fra due qualsiasi siano parecchie, si possono avere tutte e tre le cose insieme. Qui non si fa perché ogni collegamento in più è, a ogni giro, altro testo da leggere e da scrivere (nell’ipercubo più del doppio che nell’organigramma), e perché in una maglia nessuno vede l’insieme: per arrivare a una risposta, alla fine, bisogna mettersi d’accordo.
Supervisore e lavoratori, cioè il capo cantiere (tanti lavoratori che non si parlano fra loro): c’è una persona sola a cui chiedere che cosa sta succedendo [WBZ+24], e si paga con la sua giornata, che ha ventiquattro ore come quella degli altri, e con il fatto che se si ferma lui si ferma tutto. La cura sta nell’obbligare gli altri a scrivergli meno, più che nel dargli più tempo per leggere.
Catena, cioè la fila (handoff): semplicissima e con la testa sgombra per tutti, ma non si torna indietro, e chi sta in fondo non ha mai visto il foglio di partenza. Sei passaggi fatti bene novantacinque volte su cento arrivano in fondo intatti poco più di settantatré volte su cento. Serve un controllo dentro ogni passaggio, non solo alla fine [CPY+25].
Gerarchia, cioè l’organigramma: è la stessa fila, ma con più persone che riferiscono a ciascuno, e allora si accorcia di colpo (quindici agenti diventano sei passaggi invece di quattordici). Si paga con i riassunti, che perdono qualcosa a ogni livello e non dicono che cosa hanno perso, e con la responsabilità che si diluisce. Conviene quindi tenerla larga e bassa, ma solo finché ogni capo riesce a leggere quel che gli arriva. E il più carico è un capo intermedio, non il capo supremo.
Lavagna condivisa, come quella di una sala operativa: nessuno scrive a nessuno, si scrive sulla lavagna e si reagisce a quello che ci si trova. Nata con Hearsay-II per capire il parlato, dove suoni, parole, grammatica e significato devono contribuire senza un ordine stabilito prima [EHRLR80]. Ottimo per aggiungere uno specialista senza avvisare nessuno; si paga con la ressa in scrittura e col fatto che a fine giornata non si sa più chi ha scritto cosa.
Mercato, cioè il bando di gara (il contract net di Smith, 1980 [Smi80]): chi ha un lavoro lo annuncia, chi si sente in grado si offre, il banditore assegna, e chi ha vinto alla fine riferisce. Nessuno è capo per decreto, e il sistema si riequilibra da sé perché chi è sommerso non risponde. Si paga con il bando stesso, che è lavoro che non produce niente, e con l’offerta anomala: un modello a cui si chiede «sei in grado?» tende a dire di sì, e la gara premia chi si stima meglio, non chi lavora meglio.
Lavagna e mercato sono i due modi di coordinarsi senza sapere in anticipo con chi si parlerà: o si condivide un posto (la lavagna, ed è la stigmergia, che torna con le formiche) o si condivide una lingua (la grammatica del bando).
Da ricordare
Un sistema multi-agente è un grafo (nodi gli agenti, archi i canali) e si progetta su tre grandezze, le stesse delle reti di calcolatori: diametro, carico sul nodo più sollecitato, e cosa resta se quel nodo si ferma. Negli alberi (\(|E| = N-1\), \(\kappa(G) = 1\)) si compra una delle tre vendendo le altre; il vincolo è del numero di archi, non delle tre grandezze, e un grafo regolare ben connesso le prende tutte insieme (l’ipercubo \(Q_4\) fa diametro \(4\), carico \(21\%\) e connettività residua \(100\%\) contro \(6\), \(54\%\) e \(37\%\) dell’albero binario, con più del doppio degli archi). Qui non si usa perché il testo letto per giro va come \(2|E|\,\bar{m}\) (\(64\bar{m}\) contro i \(28\bar{m}\) dell’albero: lineare negli archi, non quadratico come nella trascrizione condivisa) e perché nessun nodo ha la vista d’insieme: l’informazione impiega fino a \(\mathrm{diam}(G)\) giri ad attraversare la maglia, e una risposta comune richiede un protocollo di consenso. Per gli alberi il vincolo si scrive col limite di Moore, \(N \le 1 + \Delta\sum_{i=0}^{k-1}(\Delta-1)^i\) con diametro \(2k\), e la fragilità graduata con la connettività residua \(\mathrm{res}(G)\).
Supervisore e lavoratori (stella): ottimizza controllo e tracciabilità, c’è un posto solo dove sta la verità sul compito [WBZ+24]; paga con il collo di bottiglia e il punto singolo di rottura. Il contesto del centro cresce come \(c_0 + N\bar{m}\), e la cura è comprimere all’ingresso, non allargare la finestra.
Catena (handoff): semplicità massima e contesto pulitissimo, ma nessun ritorno, quindi un errore a monte non è più recuperabile a valle: con sei passi al 95% la catena regge \(0{,}95^6 \approx 0{,}74\). Serve un cancello dentro ogni anello, non alla fine [CPY+25].
Gerarchia: catena e gerarchia sono lo stesso albero con ramificazione diversa, e alzare \(b\) porta il diametro da lineare a logaritmico (\(6\) contro \(14\) su quindici agenti). Paga con la perdita per riassunto, esponenziale nella profondità, e con la responsabilità diluita: conviene quindi allargare la ramificazione e abbassare i livelli, ma solo finché la finestra \(c_0 + b\,\bar{m}\) di ogni supervisore regge, perché spinta all’estremo la regola ricostruisce la stella. Il nodo più carico è un capo intermedio, non la radice.
Lavagna condivisa: nata con Hearsay-II alla Carnegie Mellon per la comprensione del parlato, dove acustica, lessico, sintassi e semantica devono contribuire senza un ordine prestabilito [EHRLR80]. Ottimizza il disaccoppiamento (si aggiunge un agente senza toccare gli altri); paga con la contesa sulla struttura condivisa e con la perdita della provenienza, e con agenti linguistici la lavagna è testo libero, senza il controllo dei conflitti che una base di dati fa su campi tipizzati.
Mercato (il contract net di Smith, 1980 [Smi80]): annuncio, offerta, assegnazione, rapporto, con ruoli assunti e lasciati. Ottimizza l’allocazione senza pianificatore; paga il costo del bando (fino a \(N+2\) messaggi, e con gli LLM fino a \(N\) inferenze per assegnarne uno) e l’offerta anomala, cioè l’agente che vince perché si stima meglio, non perché lavora meglio: la maledizione del vincitore, che diventa selezione avversa quando l’ottimismo è un tratto stabile.
Lavagna e mercato sono i due modi di coordinarsi senza un grafo deciso in anticipo (non senza messaggi: il contract net è fatto solo di messaggi diretti): la lavagna rinuncia al destinatario e lascia tracce in un ambiente comune (stigmergia, che torna con le formiche artificiali), il mercato al grafo, e il destinatario lo trova il bando. O si condivide un posto, o si condivide una lingua.
Una forma fissa chi parla con chi, ma non dice ancora che cosa vuol dire un messaggio, né come si decide quando gli agenti non sono d’accordo. Sono i due argomenti dei protocolli e del consenso, e il mercato ha già dato un indizio: quattro tipi di messaggio bastano a due sconosciuti per accordarsi su un lavoro.