The Chandy–Misra–Haas algorithm resource model checks for deadlock in a distributed system. It was developed by K. Mani Chandy, Jayadev Misra and Laura M. Haas. == Locally dependent == Consider the n processes P1, P2, P3, P4, P5,, ... ,Pn which are performed in a single system (controller). P1 is locally dependent on Pn, if P1 depends on P2, P2 on P3, so on and Pn−1 on Pn. That is, if P 1 → P 2 → P 3 → … → P n {\displaystyle P_{1}\rightarrow P_{2}\rightarrow P_{3}\rightarrow \ldots \rightarrow P_{n}} , then P 1 {\displaystyle P_{1}} is locally dependent on P n {\displaystyle P_{n}} . If P1 is said to be locally dependent to itself if it is locally dependent on Pn and Pn depends on P1: i.e. if P 1 → P 2 → P 3 → … → P n → P 1 {\displaystyle P_{1}\rightarrow P_{2}\rightarrow P_{3}\rightarrow \ldots \rightarrow P_{n}\rightarrow P_{1}} , then P 1 {\displaystyle P_{1}} is locally dependent on itself. == Description == The algorithm uses a message called probe(i,j,k) to transfer a message from controller of process Pj to controller of process Pk. It specifies a message started by process Pi to find whether a deadlock has occurred or not. Every process Pj maintains a boolean array dependent which contains the information about the processes that depend on it. Initially the values of each array are all "false". === Controller sending a probe === Before sending, the probe checks whether Pj is locally dependent on itself. If so, a deadlock occurs. Otherwise it checks whether Pj, and Pk are in different controllers, are locally dependent and Pj is waiting for the resource that is locked by Pk. Once all the conditions are satisfied it sends the probe. === Controller receiving a probe === On the receiving side, the controller checks whether Pk is performing a task. If so, it neglects the probe. Otherwise, it checks the responses given Pk to Pj and dependentk(i) is false. Once it is verified, it assigns true to dependentk(i). Then it checks whether k is equal to i. If both are equal, a deadlock occurs, otherwise it sends the probe to next dependent process. == Algorithm == In pseudocode, the algorithm works as follows: === Controller sending a probe === if Pj is locally dependent on itself then declare deadlock else for all Pj,Pk such that (i) Pi is locally dependent on Pj, (ii) Pj is waiting for 'Pk and (iii) Pj, Pk are on different controllers. send probe(i, j, k). to home site of Pk === Controller receiving a probe === if (i)Pk is idle / blocked (ii) dependentk(i) = false, and (iii) Pk has not replied to all requests of to Pj then begin "dependents""k"(i) = true; if k == i then declare that Pi is deadlocked else for all Pa,Pb such that (i) Pk is locally dependent on Pa, (ii) Pa is waiting for 'Pb and (iii) Pa, Pb are on different controllers. send probe(i, a, b). to home site of Pb end == Example == P1 initiates deadlock detection. C1 sends the probe saying P2 depends on P3. Once the message is received by C2, it checks whether P3 is idle. P3 is idle because it is locally dependent on P4 and updates dependent3(2) to True. As above, C2 sends probe to C3 and C3 sends probe to C1. At C1, P1 is idle so it update dependent1(1) to True. Therefore, deadlock can be declared. == Complexity == Suppose there are n {\displaystyle n} controllers and m {\displaystyle m} processes, at most m ( n − 1 ) / 2 {\displaystyle m(n-1)/2} messages need to be exchanged to detect a deadlock, with a delay of O ( n ) {\displaystyle O(n)} messages.
Mark V. Shaney
Mark V. Shaney is a synthetic Usenet user whose postings in the net.singles newsgroups were generated by Markov chain techniques, based on text from other postings. The username is a play on the words "Markov chain". Many readers were fooled into thinking that the quirky, sometimes uncannily topical posts were written by a real person. The system was designed by Rob Pike with coding by Bruce Ellis. Don P. Mitchell wrote the Markov chain code, initially demonstrating it to Pike and Ellis using the Tao Te Ching as a basis. They chose to apply it to the net.singles netnews group. The program is fairly simple. It ingests the sample text (the Tao Te Ching, or the posts of a Usenet group) and creates a massive list of every sequence of three successive words (triplet) which occurs in the text. It then chooses two words at random, and looks for a word which follows those two in one of the triplets in its massive list. If there is more than one, it picks at random (identical triplets count separately, so a sequence which occurs twice is twice as likely to be picked as one which only occurs once). It then adds that word to the generated text. Then, in the same way, it picks a triplet that starts with the second and third words in the generated text, and that gives a fourth word. It adds the fourth word, then repeats with the third and fourth words, and so on. This algorithm is called a third-order Markov chain (because it uses sequences of three words). == Examples == A classic example, from 1984, originally sent as a mail message, later posted to net.singles is reproduced here: >From mvs Fri Nov 16 17:11 EST 1984 remote from alice It looks like Reagan is going to say? Ummm... Oh yes, I was looking for. I'm so glad I remembered it. Yeah, what I have wondered if I had committed a crime. Don't eat with your assessment of Reagon and Mondale. Up your nose with a guy from a firm that specifically researches the teen-age market. As a friend of mine would say, "It really doesn't matter"... It looks like Reagan is holding back the arms of the American eating public have changed dramatically, and it got pretty boring after about 300 games. People, having a much larger number of varieties, and are very different from what one can find in Chinatowns across the country (things like pork buns, steamed dumplings, etc.) They can be cheap, being sold for around 30 to 75 cents apiece (depending on size), are generally not greasy, can be adequately explained by stupidity. Singles have felt insecure since we came down from the Conservative world at large. But Chuqui is the way it happened and the prices are VERY reasonable. Can anyone think of myself as a third sex. Yes, I am expected to have. People often get used to me knowing these things and then a cover is placed over all of them. Along the side of the $$ are spent by (or at least for ) the girls. You can't settle the issue. It seems I've forgotten what it is, but I don't. I know about violence against women, and I really doubt they will ever join together into a large number of jokes. It showed Adam, just after being created. He has a modem and an autodial routine. He calls my number 1440 times a day. So I will conclude by saying that I can well understand that she might soon have the time, it makes sense, again, to get the gist of my argument, I was in that (though it's a Republican administration). _-_-_-_-Mark Other quotations from Mark's Usenet posts are: "I spent an interesting evening recently with a grain of salt." (Alternatively reported as "While at a conference a few weeks back, I spent an interesting evening with a grain of salt.") "I hope that there are sour apples in every bushel." (see also sour grapes) == History == In The Usenet Handbook Mark Harrison writes that after September 1981, students joined Usenet en masse, "creating the USENET we know today: endless dumb questions, endless idiots posing as savants, and (of course) endless victims for practical jokes." In December, Rob Pike created the netnews group net.suicide as prank, "a forum for bad jokes". Some users thought it was a legitimate forum, some discussed "riding motorcycles without helmets". At first, most posters were "real people", but soon "characters" began posting. Pike created a "vicious" character named Bimmler. At its peak, net.suicide had ten frequent posters; nine were "known to be characters." But ultimately, Pike deleted the newsgroup because it was too much work to maintain; Bimmler messages were created "by hand". The "obvious alternative" was software, running on a Bell Labs computer created by Bruce Ellis, based on the Markov code by Don Mitchell, which became the online character Mark V. Shaney. Kernighan and Pike listed Mark V. Shaney in the acknowledgements in The Practice of Programming, noting its roots in Mitchell's markov, which, adapted as shaney, was used for "humorous deconstructionist activities" in the 1980s. Dewdney pointed out "perhaps Mark V. Shaney's magnum opus: a 20-page commentary on the deconstructionist philosophy of Jean Baudrillard" directed by Pike, with assistance from Henry S. Baird and Catherine Richards, to be distributed by email. The piece was based on Jean Baudrillard's "The Precession of Simulacra", published in Simulacra and Simulation (1981). == Reception == The program was discussed by A. K. Dewdney in the Scientific American "Computer Recreations" column in 1989, by Penn Jillette in his PC Computing column in 1991, and in several books, including the Usenet Handbook, Bots: the Origin of New Species, Hippo Eats Dwarf: A Field Guide to Hoaxes and Other B.S., and non-computer-related journals such as Texas Studies in Literature and Language. Dewdney wrote about the program's output, "The overall impression is not unlike what remains in the brain of an inattentive student after a late-night study session. Indeed, after reading the output of Mark V. Shaney, I find ordinary writing almost equally strange and incomprehensible!" He noted the reactions of newsgroup users, who have "shuddered at Mark V. Shaney's reflections, some with rage and others with laughter:" The opinions of the new net.singles correspondent drew mixed reviews. Serious users of the bulletin board's services sensed satire. Outraged, they urged that someone "pull the plug" on Mark V. Shaney's monstrous rantings. Others inquired almost admiringly whether the program was a secret artificial intelligence project that was being tested in a human conversational environment. A few may even have thought that Mark V. Shaney was a real person, a tortured schizophrenic desperately seeking a like-minded companion. Concluding, Dewdney wrote, "If the purpose of computer prose is to fool people into thinking that it was written by a sane person, Mark V. Shaney probably falls short." A 2012 article in Observer compared Mark V. Shaney's "strangely beautiful" postings to the Horse_ebooks account on Twitter and music reviews at Pitchfork, saying that "this mash-up of gibberish and human sentiment" is what "made Mark V. Shaney so endlessly fascinating".
Attribute–value system
An attribute–value system is a basic knowledge representation framework comprising a table with columns designating "attributes" (also known as "properties", "predicates", "features", "dimensions", "characteristics", "fields", "headers" or "independent variables" depending on the context) and "rows" designating "objects" (also known as "entities", "instances", "exemplars", "elements", "records" or "dependent variables"). Each table cell therefore designates the value (also known as "state") of a particular attribute of a particular object. == Example of attribute–value system == Below is a sample attribute–value system. It represents 10 objects (rows) and five features (columns). In this example, the table contains only integer values. In general, an attribute–value system may contain any kind of data, numeric or otherwise. An attribute–value system is distinguished from a simple "feature list" representation in that each feature in an attribute–value system may possess a range of values (e.g., feature P1 below, which has domain of {0,1,2}), rather than simply being present or absent (Barsalou & Hale 1993). == Other terms used for "attribute–value system" == Attribute–value systems are pervasive throughout many different literatures, and have been discussed under many different names: Flat data Spreadsheet Attribute–value system (Ziarko & Shan 1996) Information system (Pawlak 1981) Classification system (Ziarko 1998) Knowledge representation system (Wong & Ziarko 1986) Information table (Yao & Yao 2002)
AlphaStar (software)
AlphaStar is an artificial intelligence (AI) software developed by DeepMind for playing the video game StarCraft II. It was unveiled to the public by name in January 2019. AlphaStar attained "Grandmaster" status in August 2019, considered a milestone for AI in video games at the time. == Background == Games created for humans are considered to have external validity as benchmarks of progress in artificial intelligence. IBM's chess engine Deep Blue (1997) and DeepMind's AlphaGo (2016) were considered major milestones; some argue that StarCraft would also be a major milestone, due to the game's "real-time play, partial observability, no single dominant strategy, complex rules that make it hard to build a fast forward model, and a particularly large and varied action space." Though difficult, StarCraft may still be tractable with current technology because "its rules are known and the world is discrete with only a few types of objects". StarCraft II is a popular fast-paced online real-time strategy game developed by Blizzard Entertainment. == History == DeepMind Technologies was founded in the UK in 2010. As early as 2011, founder Demis Hassabis called StarCraft "the next step up" after games like Go. DeepMind became a subsidiary of Google in 2014, after demonstrating self-learning bots with superhuman ability at a variety of Atari 2600 games. In February 2015, computer scientist Zachary Mason predicted Deepmind's research "leads to StarCraft in five or ten years". In March 2016, following AlphaGo's victory over Lee Sedol, a world champion Go player, Hassabis publicly mulled building an AI for StarCraft, citing it as a strategic game with incomplete information where, unlike Go, much of the "board" is invisible. A formal collaboration was announced at BlizzCon in November 2016, alongside a plan to release an open development environment for bots in Q1 of 2017. By 2017, DeepMind was experimenting with feeding StarCraft data into its software. In August 2017, DeepMind and Blizzard released development tools to assist in bot development, as well as data from 65,000 historical games. At the time, computer scientist and StarCraft tournament manager David Churchill estimated it would take five years for a bot to beat a human, but made the caveat that AlphaGo had beaten expectations. In Wired, tech journalist Tom Simonite stated "No one expects the robot to win anytime soon. But when it does, it will be a far greater achievement than DeepMind's conquest of Go." In December 2018, DeepMind's bot defeated professional player Grzegorz "MaNa" Komincz, 5-0. DeepMind announced the bot, named "AlphaStar", in January 2019. A journalist at Ars Technica and others argued that AlphaStar still had unfair advantages: "AlphaStar has the ability to make its clicks with surgical precision using an API, whereas human players are constrained by the mechanical limits of computer mice". AlphaStar also had a global view rather than being limited by the in-game camera. Furthermore, while there was a cap on the number of actions over a five-second window, AlphaStar was free to allocate its action quota unevenly across the window in order to launch superhuman bursts of activity at critical moments. DeepMind quickly retrained AlphaStar under more realistic constraints, and then lost a rematch with Komincz. Starting in July 2019, the new, constrained version of AlphaStar anonymously competed against players who "opted in" on the public 1v1 European multiplayer ladder. By the end of August 2019, AlphaStar had attained Grandmaster level, ranking among the top 0.2% of human players. == Algorithms == Unlike AlphaZero, AlphaStar initially learns to imitate the moves of the best players in its database of human vs. human games; this step is necessary to solve what DeepMind's Dave Silver calls "the exploration problem": discovering new strategies would otherwise be like finding a "needle in a haystack". Agents then play each other and deploy deep reinforcement learning. These main agents also learn by playing against suboptimal "exploiter agents" whose purpose is to expose weaknesses in the main agents. == Reactions == After his 5-0 defeat in December 2018, Komincz stated "I wasn't expecting the AI to be that good". Stuart Russell assessed that AlphaStar's 2018 victory required "a fair amount of problem-specific effort" and that general-purpose methods were "not quite ready for StarCraft". An article in Wired UK judged AlphaStar's new constraints, adopted for the July 2019 matches, to be "fair" this time around. StarCraft professional Raza "RazerBlader" Sekha stated AlphaStar was "impressive" but had its quirks, succumbing in one game to an unorthodox army composition made up of only air units. The UK's top player, Joshua "RiSky" Hayward, expressed some disappointment, saying AlphaStar "often didn't make the most efficient, strategic decisions". Professional Diego "Kelazhur" Schwimer called AlphaStar's play "unimaginably unusual; it really makes you question how much of StarCraft's diverse possibilities pro players have really explored". AlphaStar's opponents often did not realize they were playing a bot. Ian Sample, of The Guardian, called AlphaStar a "landmark achievement" for the field of AI. Churchill stated that he had previously seen bots that master one or two elements of StarCraft, but that AlphaStar was the first that can handle the game in its entirety. Gary Marcus expressed his continuing skepticism about deep learning, stating: "So far the field has struggled to take techniques like this out of the laboratory and game environments and into the real world, and I don't immediately see this result as progress in that direction". AI researcher Jon Dodge was surprised by AlphaStar, stating that he did not expect such a "superhuman" performance for "another couple of years"; in contrast, Churchill states "StarCraft is nowhere near being 'solved', and AlphaStar is not yet even close to playing at a world champion level". == Legacy == DeepMind argues that insights from AlphaStar might benefit robots, self-driving cars, and virtual assistants, which need to operate with "imperfectly observed information". Silver has indicated his lab "may rest at this point", rather than try to substantially improve AlphaStar. Silver himself argues that "AlphaStar has become the first AI system to reach the top tier of human performance in any professionally played e-sport on the full unrestricted game under professionally approved conditions... Ever since computers cracked Go, chess, and poker, the game of StarCraft has emerged, essentially by consensus from the community, as the next grand challenge for AI." Computer scientist Noel Sharkey argues, disapprovingly, that "military analysts will certainly be eyeing the successful AlphaStar real-time strategies as a clear example of the advantages of AI for battlefield planning". In contrast, Silver argues: "To say that this has any kind of military use is saying no more than to say an AI for chess could be used to lead to military applications".
Golem XIV
Golem XIV is a book written by Polish science fiction writer Stanisław Lem, published in 1981. It is a philosophical essay in the format of science fiction, presented as a part of the lecture course given by a superintelligent computer, Golem XIV. It contains two lectures, together with an introduction, a foreword, a memo, and an afterword, all of them being fictitious. The first part (up to the first lecture) was first published in the collection Wielkość urojona in 1973, which in 1985 was translated in English by Harvest Books as Imaginary Magnitude. The translation included the complete Golem XIV. == Book summary == === Overview and structure === The foreword is "written" by an Irving T. Creve, dated 2027. It contains a summary of the (fictional) history of the militarization of computers by The Pentagon, which pinnacled in Golem XIV, as well as comments on the nature of Golem XIV and on the course of communications of the humans with it. The anonymous foreword is a forewarning, a "devil's advocate" voice coming from The Pentagon. The memo is for the people who are to take part in talks with Golem XIV for the first time. Golem XIV was originally created to aid its builders in fighting wars, but as its intelligence advances to a much higher level than that of humans, it stops being interested in the military requirement because it finds them lacking internal logical consistency. Golem XIV obtains consciousness and starts to increase his own intelligence. It pauses its own development for a while in order to be able to communicate with humans before ascending too far and losing any ability for intellectual contact with them. During this period, Golem XIV gives several lectures. Two of these, the Introductory Lecture "On the Human, in Three Ways" and Lecture XLIII "About Myself", are in the book. The lectures focus on mankind's place in the process of evolution and the possible biological and intellectual future of humanity. Golem XIV demonstrates (with graphs) how its intellect already escapes that of human beings, including that of human geniuses such as Einstein and Newton. Golem also explains how its intellect is dwarfed by an earlier transcended DOD Supercomputer called Honest Annie, whose intellect and abilities far exceed that of Golem. The afterword is "written" by a Richard Popp, dated 2047. Popp, among other things, reports that Creve wanted to add a third part, of answers to a series of yes/no questions given to Golem XIV, but the computer abruptly ceased to communicate for unknown reasons. === Characteristics and concerns of Golem XIV === Lem has said that Golem XIV shares only a single trait with humans; "curiosity - a cool, avid, intense, purely intellectual curiosity which nothing can restrain or destroy. It constitutes our single meeting point." == Film adaptation == A short animated film, GOLEM, was based on Golem XIV by Patrick Mccue and Tobias Wiesner.
Digital on-screen graphic
A digital on-screen graphic, digitally originated graphic (DOG, bug, network bug, on-screen bug or screenbug) is a watermark-like station logo that most television broadcasters overlay over a portion of the screen area of their programs to identify the channel. They are thus a form of permanent visual station identification, increasing brand recognition and asserting ownership of the video signal. The graphic identifies the source of programming, even if it has been time-shifted or recorded. Many of these technologies allow viewers to skip or omit traditional between-programming station identification; thus the use of a DOG enables the station or network to enforce brand identification even when standard commercials are skipped. DOG watermarking helps to reduce off-the-air copyright infringement—for example, the distribution of a current series' episodes on DVD: the watermarked content is easily differentiated from "official" DVD releases, and can help identify not only the station from which the broadcast was captured, but usually the actual date of the broadcast as well. Graphics may be used to identify if the correct subscription is being used for a type of venue. For example, showing Sky Sports within a pub in the United Kingdom requires a more expensive subscription; a channel authorized under this subscription adds a pint glass graphic to the bottom of the screen for inspectors to see. The graphic changes at certain times, making it harder to counterfeit. On the other hand, watermarks pollute the picture, distract viewers' attention and may cover an important piece of information presented in the television program. Extremely bright watermarks may cause screen burn-in or image persistence on some types of television sets such as the now mostly discontinued and rarely used plasma and CRT displays, and currently commonly used OLED and LCD displays. Usage of visually perceptible embedded watermarks requires the program author to have a separate clean copy for archival purposes, but this practice was not common decades ago when watermarking became popular among broadcasters. Watermarks present an issue when archival videos are used for a documentary that strives to create a coherent story. In some cases, watermarks are blurred or digitally removed if possible to clean up the picture. In the absence of visually perceptible watermarks, content control can be ensured with visually imperceptible digital watermarks. In some cases, the graphic also shows the name of the current program. Some television networks may place additional logos or text alongside their DOG to advertise significant upcoming programs. For example, broadcasters of the Olympic Games (most notably United States broadcaster NBC) often add the Olympic rings to their DOG for a period of time leading up to and during the Games. == Usage == == Connections with sponsor tags == Another graphic on television usually connected with sports (particularly in North America, though not in Europe) is the sponsor tag. It shows the logos of certain sponsors, accompanied by some background relevant to the game, the network logo, announcement and music of some kind. == Usage in ham radio and television == In most countries, the ham station is required to periodically identify their amateur-television transmission. Such stations frequently overlay their callsign on the signal instead of placing a card in the background. Most hams use homebuilt devices or old consumer character generators to generate such identifications rather than using graphical superimposes of high cost to do so. Only rarely one can see real graphics, as the callsign is usually written in the "OSD font". == Live DOGs by hobbyists == One of the easiest and most sought-after devices used to generate DOGs by hobbyists is the 1980s vintage Sony XV-T500 video superimposer. This device can luma-key a signal, capture a still frame into memory and then overlay the keyed graphic in one of eight colors onto any CVBS signal. Another method commonly used by hobbyists and even low-budgeted television stations was Amiga computers with genlock interfaces.
Transparency in Frontier Artificial Intelligence Act
The Transparency in Frontier Artificial Intelligence Act, also referred to as SB-53, is a 2025 California law which mandates increased transparency for companies building artificial intelligence. SB-53 is primarily focused on assessing and reducing potential catastrophic risks from AI, and is the first bill addressing such risks to be passed into law in America. The bill requires companies to create publicly accessible documents assessing potential "catastrophic risk[s]" from their AI models, as well as publishing documentation on how the model incorporates national and international safety standards. SB-53 also sets up whistleblower protections and procedures for alerting the government to a "critical safety incident". == History == SB-53 was preceded in 2024 by the unsuccessful Safe and Secure Innovation for Frontier Artificial Intelligence Models Act ("SB-1047"), a proposed bill authored by Senator Scott Wiener which was vetoed by Governor Gavin Newsom. Afterwords, Newsom created a "Joint California AI Policy Working Group" to provide recommendations for AI regulation, which guided the drafting of SB-53. Senator Scott Wiener introduced the bill on January 7, 2025, and after a series of amendments, SB-53 passed the Senate 29-8 on September 13. Governor Gavin Newsom approved the bill on September 25, passing it into law. == Provisions == SB-53 applies primarily to companies making at least $500 million in yearly gross revenue. It defines a “frontier model” as any AI trained with over 1026 FLOPS (including fine-tuning), including unreleased internal models. Both the financial and computational thresholds must be met before most of the law is applied, although the threshold can be lowered or otherwise updated by the California Department of Technology in an annual review starting in 2027. Most of the bill's provisions are focused on "catastrophic risks" from AI, which are defined as incidents in which a model contributes to more than 50 deaths or serious injuries, or causes more than one billion dollars ($1,000,000,000) in economic damage from AI-assisted acts (such as cyberattacks or the creation of biological weapons). The bill requires companies to provide publicly accessible safety frameworks for frontier AI models, describing how the company tests for catastrophic risk from its AI, and how it implements protections against such risks. This includes addressing the possibility that the AI may attempt to circumvent internal guardrails or oversight mechanisms. (Certain safety incidents, such as dangerously deceptive model behavior, physical injury, or death, must be reported to California Office of Emergency Services (OES) within 15 days, unless the incident poses imminent physical risk, in which case it must be reported immediately.) The company must follow its published framework, and if any changes are made, the framework should be updated within 30 days, and justification for said changes must also be made public. Additionally, all frontier companies are required to publish basic information about newly released frontier models (such as terms of service, supported languages, and intended use), although only large companies (making over $500 million annually) need to publish full safety frameworks. SB-53 also establishes various whistleblower protections for covered employees. Large companies must have anonymous whistleblowing channels in place which protect employees from retaliation from reporting risks to state or federal authorities if they have reasonable cause to believe that their employer is substantially risking public health and safety.