Anna Karlin
US-amerikanische Informatikerin Aus Wikipedia, der freien Enzyklopädie
US-amerikanische Informatikerin Aus Wikipedia, der freien Enzyklopädie
Anna R. Karlin (* 1960) ist eine US-amerikanische Informatikerin und Hochschullehrerin an der University of Washington.
Anna Karlin ist die Tochter des Mathematikers Samuel Karlin. Sie studierte an der Stanford University mit dem Bachelor-Abschluss 1981 und der Promotion bei Jeffrey Ullman 1987 (Sharing Memory in Distributed Systems - Methods and Application).[1] Danach war sie fünf Jahre beim DEC Systems Research Center. Ab 1994 war sie an der University of Washington, an der sie Bill and Melinda Gates Professorin für Informatik an der Paul G. Allen School of Computer Science and Engineering ist.
Sie entwirft und analysiert vor allem Zufalls-Algorithmen (sogenannte randomisierte oder probabilistische Algorithmen) und Online-Algorithmen, zum Beispiel im Bereich verteiltes Rechnen, Data Mining, Systemsoftware und Betriebssysteme, Computernetzwerke, algorithmische Spieltheorie. Sie veröffentlichte über Zufalls-markierte Paket-Marker, um IPs zu verfolgen,[2][3] kompetitive Analyse von Multiprozessor-Cache-Kohärenz-Algorithmen,[4] einheitliche Algorithmen um Speicher auf allen Hierarchieebenen zu verwalten,[5] kooperatives Web-Proxy-Caching[6] und Hash-Tabellen mit konstanter worst-case Nachschlagzeit.[7] Sie veröffentlichte auch über Anwendungen von Algorithmen in den Wirtschaftswissenschaften (Preisbildung, Auktionen).
Mit ihren Ko-Autoren Yossi Azar, Andrei Broder und Eli Upfall führte sie 1994 das Balanced Allocation (ausgewogene Zuteilung) Paradigma ein.[8][9] Dabei geht es um das klassische balls-into-bins Problem (oder balanced allocation), in dem n Bälle auf m Kästen (bins) verteilt werden in mehr oder weniger zufälliger Weise. Eine Strategie (power of two choices) wählt zwei Kästen zufällig aus und legt den Ball in den mit der kleineren Anzahl von Bällen. Statt des maximalen Erwartungswerts (bei m=n) von bei rein zufälliger Verteilung reduziert das Maximum auf und damit exponentiell. Das Problem hat viele Anwendungen in der Informatik, zum Beispiel gleichmäßigere Auslastungen (Balancierung) bei gemeinsamen Speicherplätzen, Verteilung von Informationspaketen auf parallele Routen in Web-Servern und Netzwerken, Hash-Tabellen. Er erfordert nur Entscheidungen auf lokaler Ebene, eine Form zentraler Kontrolle oder Kenntnis über die erwarteten Rückfragen und wurde in vielfältiger Weise weiterentwickelt. Die Einfachheit der Strategie war unerwartet und sie wurde ein neues Paradigma in der Algorithmentheorie. Anwendungen fand sie zum Beispiel beim Web-Index von iGoogle, im Overlay-Netz von Akamai und hochzuverlässige verteilte Datenspeichersysteme bei Microsoft und Dropbox.
2020 erhielt sie mit Yossi Azar, Andrei Broder, Michael Mitzenmacher und Eli Upfal den Paris-Kanellakis-Preis für die Entdeckung und Analyse von ausgewogenen Zuteilungen (balanced allocations), bekannt als „power of two choices“, und deren umfangreiche Anwendungen in der Praxis (Laudatio). 2012 wurde sie Fellow der Association for Computing Machinery, 2016 Fellow der American Academy of Arts and Sciences, 2021 Mitglied der National Academy of Sciences und 2022 der National Academy of Engineering.
1997 war sie Vorsitzende des Programmkomitees des IEEE Symposiums on Foundations of Computer Science.
Zu ihren Doktoranden gehört Frank McSherry.
Mit anderen Mitgliedern von DEC Systems Research spielte sie in der Garagen-Rockband Severe Tire Damage (Gesang, Gitarre) in Palo Alto.
Außer die in den Fußnoten zitierten Arbeiten.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.
